Katkat
Back

Enumerate Right-and-Down Paths Through a Binary Matrix

OracleSoftware Engineer · Onsite
MediumSoftware EngineerOnsiteCoding & Algorithms

Last updated

This problem tests your ability to explore paths in a grid using depth-first search (DFS) with backtracking while maintaining lexicographical output constraints.

Problem Statement

Given a 2D grid of size m x n represented as a binary matrix where 0 represents an open path and 1 represents a blocked cell, write a function that returns a list of all possible paths from the top-left cell (0, 0) to the bottom-right cell (m-1, n-1). You can only move either Right (R) or Down (D).

If the start (0, 0) or the end (m-1, n-1) cells are 1, return an empty list. The output list must contain strings representing the sequence of moves, sorted in lexicographical order.

Function Signature

def find_all_paths(grid: List[List[int]]) -> List[str]:

Examples

Example 1: Input:

grid = [[0, 0],
        [0, 0]]

Output: ["DR", "RD"]

Example 2: Input:

grid = [[0, 1],
        [1, 0]]

Output: []

Constraints

  • 1 <= m, n <= 10
  • grid[i][j] is either 0 or 1
  • Since m and n are small, you are expected to return all paths, even if the number of paths is large.

Edge Cases

  • A single-cell grid [[0]] should return [""] (an empty string representing no moves needed to reach the end).
  • A grid where no path exists should return [].

Hints

Hint 1

Use recursion to explore the grid, prioritizing the 'D' (Down) move before the 'R' (Right) move to satisfy lexicographical ordering automatically.

Hint 2

At each cell `(r, c)`, stop recursion if the cell is out of bounds or contains a `1`.

Hint 3

Base case is reaching `(m-1, n-1)`; when reached, add the current path string to your results list.

Follow-up questions

  • How would the time complexity change if you were asked to only count the number of paths instead of listing them?
  • Can you optimize the space complexity if you only need to store the total count of paths rather than the paths themselves?
  • How would you modify your solution if the matrix included obstacles that were not just '1's but specific coordinate points provided in a separate list?