Katkat
Back

Replace Dashes With Nearest Letters

UberBackend Engineer · Technical Screen
MediumBackend EngineerTechnical ScreenCoding & Algorithms

Last updated

This problem tests your ability to perform a multi-source shortest path search on a grid to determine the influence of characters on empty spaces, using Manhattan distance and lexicographical tie-breaking.

Problem Statement

You are given a 2D grid of size m x n containing lowercase English letters and dashes (-). Your task is to replace every dash with the "nearest" letter present in the grid.

Define the distance between a cell (r, c) and a letter at (fr, fc) as the Manhattan distance: abs(r - fr) + abs(c - fc).

Rules:

  1. A dash should be replaced by the letter that has the minimum Manhattan distance to it.
  2. If multiple letters are at the same minimum distance, choose the one that is lexicographically smallest (e.g., 'a' beats 'b').
  3. If multiple letters have the same minimum distance and are the same character, the tie-breaking doesn't apply (they result in the same character).

Function Signature

def replace_dashes(grid: List[List[str]]) -> List[List[str]]:

Examples

Example 1: Input: [['-', 'b'], ['a', '-']] Output: [['a', 'b'], ['a', 'b']] Explanation: Top-left dash is distance 1 from both 'a' and 'b'. 'a' is smaller.

Constraints

  • m, n are between 1 and 200.
  • The grid will contain at least one letter.
  • Time limit: 1 second.

Hints

Hint 1

Think of this as a multi-source shortest path problem where all letters are starting nodes in a Breadth-First Search (BFS).

Hint 2

Store the state in your BFS queue as `(distance, character, row, column)` and use a secondary grid to keep track of the closest character and distance found so far for every cell.

Hint 3

Since you need to prioritize lexicographical order, ensure your initial BFS queue is sorted by character value, or process the grid systematically.

Follow-up questions

  • How would you optimize the memory usage if the grid were extremely sparse (very few letters)?
  • What if we add a constraint that a dash can only be filled by a letter within a maximum distance `K`?
  • How would the solution change if we replaced Manhattan distance with Euclidean distance?