Given an N×M binary grid, return a matrix where each cell stores the distance to the nearest cell having value 1.
Movement is allowed only in four directions: up, down, left, and right. Cells containing 1 have distance 0 from the nearest one-cell.
Example 1
Input: grid = [[0,0,0],[0,1,0],[0,0,0]]
Output: [[2,1,2],[1,0,1],[2,1,2]]
Explanation: The center cell is the only one-cell, so distances expand outward by one step per layer.
Example 2
Input: grid = [[1,0,1],[1,1,0],[1,0,0]]
Output: [[0,1,0],[0,0,1],[0,1,2]]
Explanation: Every zero-cell stores the shortest four-direction distance to any one-cell.
Brute Force Approach
The direct method stores the coordinates of every cell containing 1. For each grid cell, Manhattan distance is calculated against every stored 1-cell.
The smallest calculated distance becomes the answer for the current cell. Checking every possible source guarantees correctness but causes repeated comparisons.
Algorithm
Initialize a list to store the coordinates of all cells containing
1.Traverse the grid using an outer loop for rows and an inner loop for columns, ensuring that every cell is examined.
Add every
1-cell coordinate to the list, creating the complete collection of possible nearest sources.Initialize an
N×Mdistance matrix with large values to store minimum distances.For every grid cell, calculate
|row-sourceRow|+|col-sourceCol|for each stored source coordinate.Store the smallest calculated Manhattan distance in the corresponding matrix position.
Return the completed distance matrix after all cells have been processed.
Dry Run
nearest-1-cell-bruteforce-corrected
Solution
#include <bits/stdc++.h>using namespace std;class Solution {public: // Function to compute nearest-one distances using brute force. vector<vector<int>> nearest(vector<vector<int>>& grid) { int rows = grid.size(); int cols = grid[0].size(); vector<pair<int, int>> ones; // Store coordinates of every source cell. for (int row = 0; row < rows; row++) { for (int col = 0; col < cols; col++) { if (grid[row][col] == 1) { ones.push_back({row, col}); } } } vector<vector<int>> dist(rows, vector<int>(cols, 0)); // Compute nearest source distance for every grid cell. for (int row = 0; row < rows; row++) { for (int col = 0; col < cols; col++) { int best = rows + cols; // Compare current cell with every source cell. for (auto& source : ones) { int value = abs(row - source.first) + abs(col - source.second); best = min(best, value); } // Store the minimum Manhattan distance. dist[row][col] = best; } } // Return completed distance matrix. return dist; }};// Driver code.int main() { vector<vector<int>> grid = {{0,0,0},{0,1,0},{0,0,0}}; Solution sol; vector<vector<int>> ans = sol.nearest(grid); // Print resulting distance matrix. for (auto& row : ans) { for (int value : row) { cout << value << " "; } cout << "\n"; } return 0;}Complexity Analysis
Time Complexity: O(N×M×K), where N and M are the grid dimensions and K is the number of 1-cells; the worst case is O((N×M)²).
Space Complexity: O(N×M), where the answer matrix and the source list can each store a number of entries proportional to the total cell count.
Optimal Approach
Multi-source Breadth First Search treats every 1-cell as a source having distance 0. Adding all sources initially allows distances to spread simultaneously across the grid.
BFS processes cells in increasing distance order, so the first visit to a cell provides the shortest distance to any 1-cell. Marking cells before queue insertion prevents duplicate processing.
Algorithm
Initialize an
N×Mdistance matrix with-1and an empty queue, where-1represents an unvisited cell.Traverse the grid using nested row and column loops to locate every
1-cell.Assign distance
0to every1-cell and add the coordinates to the queue, creating the initial multi-source BFS level.Continue processing while the queue contains cells and remove the front coordinates.
Examine the four orthogonal neighbors and ignore positions outside the grid or cells having an assigned distance.
Assign
distance[current]+1to every valid unvisited neighbor before queue insertion, ensuring shortest-distance assignment and preventing duplicates.Return the completed distance matrix after the queue becomes empty.
Dry Run
Diagram 1
Solution
#include <bits/stdc++.h>using namespace std;class Solution {public: // Function to compute nearest-one distances using multi-source BFS. vector<vector<int>> nearest(vector<vector<int>>& grid) { int rows = grid.size(); int cols = grid[0].size(); queue<pair<int, int>> q; vector<vector<int>> dist(rows, vector<int>(cols, -1)); // Add every one-cell as a BFS source. for (int row = 0; row < rows; row++) { for (int col = 0; col < cols; col++) { if (grid[row][col] == 1) { dist[row][col] = 0; q.push({row, col}); } } } vector<int> dRow = {-1, 1, 0, 0}; vector<int> dCol = {0, 0, -1, 1}; // Expand BFS layers from all sources. while (!q.empty()) { auto [row, col] = q.front(); q.pop(); // Visit four neighboring cells. for (int dir = 0; dir < 4; dir++) { int nextRow = row + dRow[dir]; int nextCol = col + dCol[dir]; if (nextRow >= 0 && nextCol >= 0 && nextRow < rows && nextCol < cols && dist[nextRow][nextCol] == -1) { dist[nextRow][nextCol] = dist[row][col] + 1; q.push({nextRow, nextCol}); } } } // Return completed distance matrix. return dist; }};// Driver code.int main() { vector<vector<int>> grid = {{0,0,0},{0,1,0},{0,0,0}}; Solution sol; vector<vector<int>> ans = sol.nearest(grid); // Print resulting distance matrix. for (auto& row : ans) { for (int value : row) { cout << value << " "; } cout << "\n"; } return 0;}Complexity Analysis
Time Complexity: O(N×M), where N and M are the numbers of rows and columns; every grid cell enters the queue at most once.
Space Complexity: O(N×M), where the distance matrix and BFS queue can each store up to N×M cells.
Interview follow-up Questions
BFS expands in layers, so the first assigned value for a cell is the minimum four-direction distance.
Be the first to add a comment.