Quick Overview

Minimize the worst inconvenience in a binary grid by adding one colored source. Movement is allowed in eight directions, and the solution must handle grids that begin with no source at all.

Add One Source to Minimize Grid Inconvenience

Company: Amazon

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Online Assessment

# Add One Source to Minimize Grid Inconvenience Implement `min_max_inconvenience(grid)`. `grid` is a non-empty rectangular matrix containing `0` and `1`. A cell containing `1` is an existing colored source. You may choose any one cell, including an already colored cell, and add a colored source there. Movement is allowed in all eight directions: horizontal, vertical, and diagonal. Every move costs one. A cell's inconvenience is its shortest-path distance to the nearest colored source after your addition. Return the smallest possible value of the maximum inconvenience over all cells. ## Examples - For `[[0]]`, return `0`. - For `[[1, 0, 0]]`, return `1` by adding a source at the last cell. - For `[[1, 0], [0, 0]]`, return `1`; after adding one source, at least one uncolored cell remains one move from its nearest source. ## Constraints - `1 <= len(grid), len(grid[0]) <= 200` - Every row has the same length. - Every element is either `0` or `1`. - The grid may initially contain no colored source.

Overview: Minimize the worst inconvenience in a binary grid by adding one colored source. Movement is allowed in eight directions, and the solution must handle grids that begin with no source at all.

Implement min_max_inconvenience(grid). The non-empty rectangular grid contains 0 and 1; every 1 is an existing colored source. Add one source at any cell, including a source cell. Movement uses all eight neighboring directions at unit cost. A cell's inconvenience is its distance to the nearest source after the addition. Return the smallest possible maximum inconvenience. The grid may initially contain no source.

Constraints

  • 1 <= rows, columns <= 200
  • Every cell is 0 or 1 and all rows have equal length.
  • Movement uses all eight neighboring directions.
  • The grid may initially contain no colored source.
  • Exactly one source may be added, including on an existing source.

Examples

Input: ([[0]],)

Expected Output: 0

Explanation: The added source occupies the only cell.

Input: ([[1]],)

Expected Output: 0

Explanation: The existing source already covers the only cell.

Hints

  1. First compute every cell's distance to the existing sources with multi-source BFS.
  2. For a proposed answer d, only cells whose old distance exceeds d must be covered by the new source.
  3. An eight-direction distance-d ball is an axis-aligned square, so intersect row and column intervals.

Loading coding console...

Show the approach

Approach

Multi-source BFS yields existing-source distances under eight-direction movement. Binary-search the maximum allowed inconvenience d. Every cell already within d needs no help; each remaining cell requires the new source's row and column to lie within d of its own row and column. These requirements are independent interval intersections, so feasibility is constant extra work per cell. Feasibility is monotone in d.

Time complexity:
O(rows * columns * log(max(rows, columns))).
Space complexity:
O(rows * columns) for distances and the BFS queue.