Shortest Manhattan Distance Between Any X and Any Y in a String or Grid
Company: Glean
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
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
```python
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**
```text
Input: grid = ["XOXOXXOOYOXO"]
Output: 2
```
The only `Y` is at index 8. The nearest `X` is at index 10.
**Example 2**
```text
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**
```text
Input: grid = ["XOX", "OOO"]
Output: -1
```
There is no `Y`.
Overview: Find the shortest distance between any X and any Y, first in a string and then in a 2D grid using Manhattan distance, returning -1 when one letter is missing. Tests moving from a linear scan to multi-source breadth-first search and reasoning about efficiency on large grids.
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
```text
Input: grid = ["XOXOXXOOYOXO"]
Output: 2
```
The only `'Y'` is at index 8. The nearest `'X'` is at index 10.
### Example 2
```text
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'`.
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
Input: (['X'],)
Expected Output: -1
Explanation: 1x1 grid holding only an X has no Y, so the answer is -1.
Input: (['Y'],)
Expected Output: -1
Explanation: 1x1 grid holding only a Y has no X, so the answer is -1.
Hints
- 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.
- 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.
- 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.