Find grid cell minimizing sum distances
Company: Applied Intuition
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
You are given an m x n 2D grid with k marked points. Movement is allowed in four directions (up, down, left, right) with unit cost per step. Find a grid cell whose sum of shortest-path distances to all marked points is minimized; if any marked point is unreachable from every cell, return -1. Implement a brute-force BFS-based solution that computes these distances, return both the minimum total distance and one optimal cell, and analyze time and space complexity. Discuss when multi-source BFS or using coordinate medians (if there are no obstacles) can reduce complexity.
Quick Answer: This question evaluates proficiency in grid-based graph traversal and shortest-path computation using BFS, reachability analysis from multiple marked points, and algorithmic time/space complexity reasoning.
You are given a rectangular grid where -1 represents a blocked cell, 0 represents an empty traversable cell, and 1 represents a marked point. You may move up, down, left, or right between non-blocked cells with cost 1 per step. For any traversable cell, define its cost as the sum of its shortest-path distances to all marked points. Return the minimum possible cost and one optimal cell as `(min_total_distance, (row, col))`. If multiple cells are optimal, return the lexicographically smallest `(row, col)`. If no traversable cell can reach every marked point, return `-1`. For this version, implement the brute-force approach: try every traversable cell as the meeting cell and run BFS from it to compute distances. As a follow-up, discuss why reversing the searches and running BFS from each marked point can reduce the work, why a simultaneous multi-source BFS is only enough for nearest-source-style objectives, and why in a grid with no obstacles the optimal row and column are given by the medians of the marked coordinates.
Constraints
- 1 <= m, n <= 30
- grid[i][j] is one of -1, 0, or 1
- There is at least one marked cell
- Movement is allowed only through cells whose value is not -1
Examples
Input: ([[1,0,0],[0,1,0],[0,0,1]],)
Expected Output: (4, (1, 1))
Explanation: Cell (1, 1) reaches the three marked cells in distances 2, 0, and 2, for a total of 4, which is minimal.
Input: ([[1,-1,0,0],[0,-1,0,1],[0,0,1,0]],)
Expected Output: (6, (2, 2))
Explanation: Obstacles force paths around the blocked cells; from (2, 2) the distances to the marks are 4, 2, and 0, summing to 6.
Hints
- Because every move has the same cost, shortest paths from one cell to all others in an unweighted grid are found with BFS.
- For the required brute-force solution, iterate over every non-blocked cell, run BFS, add distances when marked cells are first reached, and keep the best total. Scanning cells row by row naturally handles lexicographic tie-breaking.