Nearest Bomb in Grid

TCS NQT Coding Easy Go Ad-Free - ₹20/mo

Given a 2D grid of size N x N where each cell contains either 0 (empty) or 1 (bomb), and a starting coordinate (startX, startY), find the Manhattan distance to the nearest bomb from the starting position. If no bomb exists, return -1.

Examples:

Input: grid = [[0,0,0],[0,1,0],[0,0,0]], start = (0,0)

Output: 2

Explanation: The bomb at (1,1) is nearest with Manhattan distance |0-1| + |0-1| = 2.

Input: grid = [[1,0],[0,0]], start = (1,1)

Output: 2

Input: grid = [[0,0],[0,0]], start = (0,0)

Output: -1

Constraints

1 ≤ N < 1000
0 ≤ startX, startY < N
grid[i][j] ∈ {0,1}

Editorial

Intuition:

The Manhattan distance between two points (x1, y1) and (x2, y2) is |x1 - x2| + |y1 - y2|, which depends only on coordinates and not on grid contents. Thus, we can compute the distance to every bomb cell and take the minimum.

Approach:

Initialize minDist to a large value (e.g., INT_MAX in C++, Integer.MAX_VALUE in Java, float('inf') in Python, Number.MAX_SAFE_INTEGER in JavaScript).
Iterate over each cell (i, j) in the grid.
If grid[i][j] == 1, compute the Manhattan distance d = |i - startX| + |j - startY| and update minDist if d is smaller.
After the loop, return -1 if minDist remains unchanged; otherwise return minDist.

#include <vector>
#include <climits>
#include <cstdlib>
using namespace std;
class Solution {
public:
    int nearestBomb(vector<vector<int>>& grid, int startX, int startY) {
        int n = grid.size(), minDist = INT_MAX;
        for (int i = 0; i < n; ++i)
            for (int j = 0; j < n; ++j)
                if (grid[i][j] == 1) {
                    int d = abs(i - startX) + abs(j - startY);
                    if (d < minDist) minDist = d;
                }
        return minDist == INT_MAX ? -1 : minDist;
    }
};
class Solution {
    public int nearestBomb(int[][] grid, int startX, int startY) {
        int n = grid.length, minDist = Integer.MAX_VALUE;
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                if (grid[i][j] == 1) {
                    int d = Math.abs(i - startX) + Math.abs(j - startY);
                    if (d < minDist) minDist = d;
                }
        return minDist == Integer.MAX_VALUE ? -1 : minDist;
    }
}
class Solution:
    def nearestBomb(self, grid, startX, startY):
        n = len(grid)
        minDist = float('inf')
        for i in range(n):
            for j in range(n):
                if grid[i][j] == 1:
                    d = abs(i - startX) + abs(j - startY)
                    if d < minDist:
                        minDist = d
        return -1 if minDist == float('inf') else minDist
function nearestBomb(grid, startX, startY) {
    const n = grid.length;
    let minDist = Number.MAX_SAFE_INTEGER;
    for (let i = 0; i < n; i++)
        for (let j = 0; j < n; j++)
            if (grid[i][j] === 1) {
                const d = Math.abs(i - startX) + Math.abs(j - startY);
                if (d < minDist) minDist = d;
            }
    return minDist === Number.MAX_SAFE_INTEGER ? -1 : minDist;
}

Complexity Analysis:

Time Complexity: O(N²), as we traverse the entire grid once to check each cell.

Space Complexity: O(1), as we only use a constant amount of extra space.

Notes

Your notes are automatically saved in your browser's local storage and will persist across sessions on this device.

Problem Categories