01 Matrix (LeetCode 542) – Dynamic Programming Solution with Java, C++, and Python Implementations

A netizen was asked why they left their previous company; they replied that the promised salary increase was never delivered and they dislike companies that overpromise, illustrating a blunt but honest answer.

Typical reasons for leaving a job include low pay, excessive overtime, and burnout, but interviewees often feel pressured to give lofty responses such as seeking new challenges, wanting to grow on a better platform, or aligning with long‑term career plans.

Problem Description: Given a binary matrix mat, output a matrix of the same size where each cell contains the distance to the nearest 0. Adjacent cells have a distance of 1.

Constraints:

m == mat.length

n == mat[i].length

1 <= m, n <= 10^4

1 <= m * n <= 10^4

mat[i][j] is either 0 or 1.

There is at least one 0 in the matrix.

Example 1: Input: mat = [[0,0,0],[0,1,0],[0,0,0]] Output: [[0,0,0],[0,1,0],[0,0,0]] Example 2: Input: mat = [[0,0,0],[0,1,0],[1,1,1]] Output: [[0,0,0],[0,1,0],[1,2,1]] Problem Analysis: The shortest distance to a zero can be found using BFS, but a two‑pass dynamic programming (DP) approach is also efficient. Define dp[i][j] as the distance from cell (i, j) to the nearest zero. The recurrence is:

dp[i][j] = min(dp[i-1][j], dp[i+1][j], dp[i][j-1], dp[i][j+1]) + 1;

Because some neighboring values may be unknown during a single scan, we perform two passes: first from top‑left to bottom‑right considering the top and left neighbors, then from bottom‑right to top‑left considering the bottom and right neighbors.

Java implementation:

public int[][] updateMatrix(int[][] mat) {
    int m = mat.length, n = mat[0].length;
    int[][] dp = new int[m][n];
    int max = m + n;
    // First pass: top and left
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (mat[i][j] != 0) {
                int up = i > 0 ? dp[i - 1][j] : max;
                int left = j > 0 ? dp[i][j - 1] : max;
                dp[i][j] = Math.min(up, left) + 1;
            }
        }
    }
    // Second pass: bottom and right
    for (int i = m - 1; i >= 0; i--) {
        for (int j = n - 1; j >= 0; j--) {
            if (mat[i][j] != 0) {
                int down = (i < m - 1) ? dp[i + 1][j] : max;
                int right = (j < n - 1) ? dp[i][j + 1] : max;
                dp[i][j] = Math.min(Math.min(down, right) + 1, dp[i][j]);
            }
        }
    }
    return dp;
}

C++ implementation:

vector<vector<int>> updateMatrix(vector<vector<int>>& mat) {
    int m = mat.size(), n = mat[0].size();
    vector<vector<int>> dp(m, vector<int>(n));
    int max = m + n;
    // First pass: top and left
    for (int i = 0; i < m; ++i) {
        for (int j = 0; j < n; ++j) {
            if (mat[i][j] != 0) {
                int up = i > 0 ? dp[i - 1][j] : max;
                int left = j > 0 ? dp[i][j - 1] : max;
                dp[i][j] = min(up, left) + 1;
            }
        }
    }
    // Second pass: bottom and right
    for (int i = m - 1; i >= 0; --i) {
        for (int j = n - 1; j >= 0; --j) {
            if (mat[i][j] != 0) {
                int down = (i < m - 1) ? dp[i + 1][j] : max;
                int right = (j < n - 1) ? dp[i][j + 1] : max;
                dp[i][j] = min(min(down, right) + 1, dp[i][j]);
            }
        }
    }
    return dp;
}

Python implementation:

def updateMatrix(self, mat: List[List[int]]) -> List[List[int]]:
    m, n = len(mat), len(mat[0])
    dp = [[0] * n for _ in range(m)]
    max_dist = m + n
    # First pass: top and left
    for i in range(m):
        for j in range(n):
            if mat[i][j] != 0:
                up = dp[i-1][j] if i > 0 else max_dist
                left = dp[i][j-1] if j > 0 else max_dist
                dp[i][j] = min(up, left) + 1
    # Second pass: bottom and right
    for i in range(m-1, -1, -1):
        for j in range(n-1, -1, -1):
            if mat[i][j] != 0:
                down = dp[i+1][j] if i < m-1 else max_dist
                right = dp[i][j+1] if j < n-1 else max_dist
                dp[i][j] = min(min(down, right) + 1, dp[i][j])
    return dp