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.