How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a medium difficulty Coding & Algorithms question, commonly asked during Take-home Project rounds at Amazon.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Amazon during technical interviews.

Add One Source to Minimize Grid Inconvenience

Q: Add One Source to Minimize Grid Inconvenience

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.

Company: Amazon

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Take-home Project

# 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.

Quick Answer: 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

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

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.