Katkat
Back

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

GleanSoftware Engineer · Onsite
MediumSoftware EngineerOnsiteCoding & Algorithms

Last updated

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.

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.