Shortest Manhattan Distance Between Any X and Any Y in a String or Grid

The interview had two parts. The first gave a string such as "XOXOXXOOYOXO" and asked for the shortest distance between any X and any Y (here 2). The second asked the same question on a 2D grid, with distance measured as Manhattan distance.

Solve the grid version. A grid with one row is the string version.

Function Signature

def min_xy_distance(grid: list[str]) -> int:

Rules

• Every cell is 'X', 'Y' or 'O'. 'O' cells are ordinary cells, and there are no obstacles.
• The distance between cells (r1, c1) and (r2, c2) is |r1 - r2| + |c1 - c2|.
• Return the minimum distance over all pairs of one 'X' cell and one 'Y' cell. If the grid has no 'X' or no 'Y', return -1.

Constraints

• 1 <= len(grid) <= 1000 and 1 <= len(grid[i]) <= 1000, all rows of equal length, and at most 10^6 cells in total
• Every character is 'X', 'Y' or 'O'.

Examples

Example 1

Input:  grid = ["XOXOXXOOYOXO"]
Output: 2

The only Y is at index 8. The nearest X is at index 10.

Example 2

Input:  grid = [
  "OXOOX",
  "OOOOO",
  "YOOOO"
]
Output: 3

The X at (0, 1) is at distance 2 + 1 = 3 from the Y at (2, 0). The other X is at distance 6.

Example 3

Input:  grid = ["XOX", "OOO"]
Output: -1

There is no Y.

Closest X and Y Cells by Manhattan Distance

You are given a rectangular grid as a list of strings grid, where grid[r][c] is the cell in row r and column c. Every cell is 'X', 'Y' or 'O'. 'O' cells are ordinary cells, and there are no obstacles.

The distance between cells (r1, c1) and (r2, c2) is the Manhattan distance |r1 - r2| + |c1 - c2|.

Return the minimum distance over all pairs of one 'X' cell and one 'Y' cell. If the grid has no 'X' or no 'Y', return -1.

A grid with one row is the string version of the problem: the shortest distance between any 'X' and any 'Y' in a string.

The answer never exceeds 1998, so it fits in a 32-bit signed integer in every language.

Example 1

Input:  grid = ["XOXOXXOOYOXO"]
Output: 2

The only 'Y' is at index 8. The nearest 'X' is at index 10.

Example 2

Input:  grid = ["OXOOX", "OOOOO", "YOOOO"]
Output: 3

The 'X' at (0, 1) is at distance 2 + 1 = 3 from the 'Y' at (2, 0). The other 'X', at (0, 4), is at distance 6.

Constraints

• 1 <= len(grid) <= 1000 and 1 <= len(grid[i]) <= 1000, all rows of equal length, and at most 10^6 cells in total
• Every character is 'X', 'Y' or 'O'.

Hints

1. Handle the -1 case first: if either letter is missing there is no pair. Otherwise the answer is at least 1, because an 'X' cell and a 'Y' cell are always different cells.
2. There are no obstacles, so the distance depends only on the row and column offsets. With up to 10^6 cells both letters can appear hundreds of thousands of times, so checking every X/Y pair can be far too slow.
3. Aim for work proportional to the number of cells: think about how far each cell is from its nearest 'X', and what that value tells you at the 'Y' cells.

Approach

Return -1 immediately if the grid contains no 'X' or no 'Y'. Otherwise run a multi-source breadth-first search that starts from every 'X' cell at distance 0 and moves between orthogonally adjacent cells. Because there are no obstacles, the shortest 4-directional path between two cells has length exactly |r1 - r2| + |c1 - c2|, so the BFS layer at which a cell is first reached equals its Manhattan distance to the nearest 'X'. BFS settles cells in nondecreasing layer order, so the first 'Y' it discovers lies at the minimum distance over all X/Y pairs, and that layer is returned at once. Invariant: every queued cell's recorded distance equals its true distance to the nearest 'X', and every cell at a smaller distance has already been discovered. Each cell is queued at most once, so the work is linear in the number of cells. Edge cases: a 1x1 grid can never hold both letters (-1); a single row is the string version and a single column works the same way; an 'X' cell and a 'Y' cell are always different cells, so any real answer is at least 1; the largest possible answer, 1998, fits in a 32-bit integer.

• Time complexity: O(R * C)
• Space complexity: O(R * C)