01 Matrix Problem & Solution

#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx,avx2,fma")

static const int _=[](){ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);return 0;}();

class Solution {
public:
  vector<vector<int>> updateMatrix(vector<vector<int>>& mat) {
    vector<vector<int>> dp(mat.size(), vector<int>(mat[0].size()));

    int infinity = mat.size() + mat[0].size();

    // traverses forward from top left to bottom right
    for (int i = 0; i < dp.size(); ++i) { // O(n)
      for (int j = 0; j < dp[0].size(); ++j) { // O(m)
        if (mat[i][j] == 0) { continue; }

        int top = infinity, left = infinity;
        if (i > 0) { top = dp[i - 1][j]; }
        if (j > 0) { left = dp[i][j - 1]; }

        dp[i][j] = min(top, left) + 1;
      }
    }

    // traverses backwards from bottom right to top left
    for (int i = dp.size() - 1; i >= 0; --i) { // O(n)
      for (int j = dp[0].size() - 1; j >= 0; --j) { // O(m)
        if (mat[i][j] == 0) { continue; }

        int bottom = infinity, right = infinity;
        if (i < dp.size() - 1) { bottom = dp[i + 1][j]; }
        if (j < dp[0].size() - 1) { right = dp[i][j + 1]; }

        dp[i][j] = min(dp[i][j], min(bottom, right) + 1);
      }
    }

    return dp;
  }
};