01 Matrix 🔨

Problem

Given a matrix consists of 0 and 1, find the distance of the nearest 0 for each cell.
The distance between two adjacent cells is 1.

Example 1:
Input:

0 0 0
0 1 0
0 0 0

Output:

0 0 0
0 1 0
0 0 0

Example 2:
Input:

0 0 0
0 1 0
1 1 1

Output:

0 0 0
0 1 0
1 2 1

Note:

The number of elements of the given matrix will not exceed 10,000.
There are at least one 0 in the given matrix.
The cells are adjacent in only four directions: up, down, left and right.

Analysis

DFS ❓

Attempt

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
class Solution {
    unordered_set<int*> visited;
    int dfs(int i, int j, vector<vector<int>>& v) {
        if (visited.find(&v[i][j]) != visited.end()) return v[i][j];
        visited.insert(&v[i][j]);
        if (v[i][j] == 0) {
            return 0;
        }

        int res = INT_MAX;
        if (j > 0) {
          //left
          res = min(res, dfs(i, j - 1, v));
        }
        if (j < v[0].size() - 1) {
          //right
          res = min(res, dfs(i, j + 1, v));
        }

        if (i > 0) {
          //top
          res = min(res, dfs(i - 1, j, v));
        }
        if (i < v.size() - 1) {
          //bottom
          res = min(res, dfs(i + 1, j, v));
        }

        v[i][j] = res;
        return res;

    }
public:
    vector<vector<int>> updateMatrix(vector<vector<int>>& matrix) {
      for (int i = 0; i < matrix.size(); i++) {
        for (int j = 0; j < matrix[0].size(); j++) {
          dfs(i, j, matrix);
        }
      }
      return matrix;
    }
};

Whoops! We are supposed to add distances at each step!

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
class Solution {
    unordered_set<int*> visited;
    int dfs(int i, int j, vector<vector<int>>& v) {
        if (visited.find(&v[i][j]) != visited.end()) return v[i][j];
        visited.insert(&v[i][j]);
        if (v[i][j] == 0) {
            return 0;
        }

        int res = INT_MAX;
        if (j > 0) {
          //left
          res = min(res, 1 + dfs(i, j - 1, v));
        }
        if (j < v[0].size() - 1) {
          //right
          res = min(res, 1+ dfs(i, j + 1, v));
        }

        if (i > 0) {
          //top
          res = min(res, 1 + dfs(i - 1, j, v));
        }
        if (i < v.size() - 1) {
          //bottom
          res = min(res, 1 + dfs(i + 1, j, v));
        }

        v[i][j] = res;
        return res;

    }
public:
    vector<vector<int>> updateMatrix(vector<vector<int>>& matrix) {
      for (int i = 0; i < matrix.size(); i++) {
        for (int j = 0; j < matrix[0].size(); j++) {
          dfs(i, j, matrix);
        }
      }
      return matrix;
    }
};

This failed to work in this case:
[[1,1,1],[1,1,0],[1,1,1]]

A majr flaw here is that while nodes are being updated, we still count them as “visited” but that’s not correct.

BFS

Attempt

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
class Solution {
    void push_n(vector<vector<int>>& q, unordered_set<int*>& s, int i , int j) {
      // push neightbor if not in set (and if value <= 1? optimize for later? we may wanto avoid any values already resolved)
      // we want to make sure we don't check any nodes
      int m = v[0].size() - 1;
      int n = v.size() - 1;

      // left
      if (j > 0) {
        if (s.find(&v[i][j-1]) == s.end()) {
          v.push_back([i,j-1]);
        }
      }

      // right
      if (j < m) {
        if (s.find(&v[i][j+1]) == s.end()) {
          v.push_back([i,j+1]);
        }
      }

      // up
      if (i > 0) {
         if (s.find(&v[i-1][j]) == s.end()) {
          v.push_back([i-1,j]);
        }
      }

      // down
      if (i < n) {
         if (s.find(&v[i+1][j]) == s.end()) {
          v.push_back([i+1,j]);
        }
      }
    }
public:
    vector<vector<int>> u pdateMatrix(vector<vector<int>>& v) {
        for (int i = 0; i < v.size(); i++) {
            for (int j = 0; j < v[0].size(); j++) {
                int dist = INT_MAX;
                if (j > 0)
                    dist = min(dist, v[i][j-1]);
                if (i > 0) dist = min(dist, v[i-1][j]);
                if (dist == 1) continue;
                int level = 0;
                vector<vector<int>> q;
                unordered_set<int*> vis;
                q.push_back([i,j]);
                vis.insert(&v[i][j]);
                while(!q.empty()) {
                    if (level >= dist) break;
                    bool done = false;
                    for(int len = q.size();len>0; len--) {
                        auto t = q.front();
                        q.pop();
                        int x = t[0];
                        int y = t[1];
                        if (v[x][y] == 0) {
                            done = true;
                            break;
                        }
                        vis.insert(&v[x][y]);
                        push_n(q, vis, x, y);
                    }
                    if (done) break;
                    level++;
                }
                dist = min(dist, level);
                v[i][j] = dist;
            }
        }
        return v;
  }
};

Accepted - very slow 😧

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
#include <vector>
#include <unordered_set>
using namespace std;

class Solution {
    void push_n(vector<vector<int>>& v, vector<vector<int>>& q, unordered_set<int*>& s, int i , int j) {
      // push neightbor if not in set (and if value <= 1? optimize for later? we may wanto avoid any values already resolved)
      // we want to make sure we don't check any nodes
      int m = v[0].size() - 1;
      int n = v.size() - 1;

      // left
      if (j > 0) {
        if (s.find(&v[i][j-1]) == s.end()) {
           vector<int> a = {i, j-1};
          q.push_back(a);
          //printf("pushed left %d %d\n", i, j-1);
        }
      }

      // right
      if (j < m) {
        if (s.find(&v[i][j+1]) == s.end()) {
            vector<int> a = {i, j+1};
          q.push_back(a);
        }
      }

      // up
      if (i > 0) {
         if (s.find(&v[i-1][j]) == s.end()) {
             vector<int> a = {i-1, j};
          q.push_back(a);
        }
      }

      // down
      if (i < n) {
         if (s.find(&v[i+1][j]) == s.end()) {
             vector<int> a = {i+1, j};
          q.push_back(a);
        }
      }

    }

public:
    vector<vector<int>> updateMatrix(vector<vector<int>>& v) {
        for (int i = 0; i < v.size(); i++) {
            for (int j = 0; j < v[0].size(); j++) {
                int dist = INT_MAX;
                if (j > 0)
                    dist = min(dist, v[i][j-1]+1);
                if (i > 0) dist = min(dist, v[i-1][j]+1);
                if (dist == 1) continue;
                int level = 0;
                vector<vector<int>> q;
                unordered_set<int*> vis;
                vector<int> a = {i,j};
                q.push_back(a);
                vis.insert(&v[i][j]);
                while(!q.empty()) {
                    //cout << "level = " << level << endl;
                    if (level >= dist) break;
                    bool done = false;
                    for(int len = q.size();len>0; len--) {

                        vector<int> t = q.front();
                        q.erase(q.begin());
                        int x = t[0];
                        int y = t[1];
                        //cout << "got elem =" << v[x][y] << endl;
                        if (v[x][y] == 0) {
                            done = true;
                            break;
                        }

                        vis.insert(&v[x][y]);
                        push_n(v, q, vis, x, y);
                    }
                    if (done) break;
                    level++;
                }
                dist = min(dist, level);
                //cout << "dist = " << dist << endl;
                v[i][j] = dist;
            }
        }
        return v;
  }
};

I’m most likely checking too many nodes on every iteration. Need to come up with a better solution.