Search⌘ K
AI Features
Home
Courses
Grokking the Coding Interview Patterns

Solution: 01 Matrix

Explore how to solve the 01 Matrix problem using dynamic programming by calculating the minimum distance from each cell to the nearest zero. Understand the recursive problem setup, overlapping subproblems, and optimal substructure. Learn to implement an efficient two-pass algorithm with O(m×n) time complexity and O(1) extra space.

We'll cover the following...

Statement

Given an m×nm \times n binary matrix, mat, find the distance from each cell to the nearest 00. The distance between two adjacent cells is 11. Cells to the left, right, above, and below the current cell will be considered adjacent.

Constraints:

  • 1≤1 \leq mat.row , mat.col≤50\leq 50

  • 1≤1 \leq mat.row * mat.col ≤2500\leq 2500

  • mat[i][j] ...