01 Matrix – LeetCode Solution Java , Python 3, Python 2 , C , C++, Best and Optimal Solutions , All you need.
Given an m x n binary matrix mat, return the distance of the nearest 0 for each cell.
The distance between two adjacent cells is 1.
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]]
Constraints:
m == mat.lengthn == mat[i].length1 <= m, n <= 1041 <= m * n <= 104mat[i][j]is either0or1.- There is at least one
0inmat.
C++ 01 Matrix LeetCode Solution
class Solution { // 48 ms, faster than 99.64%
public:
vector<vector<int>> updateMatrix(vector<vector<int>> &mat) {
int m = mat.size(), n = mat[0].size(), INF = m + n; // The distance of cells is up to (M+N)
for (int r = 0; r < m; r++) {
for (int c = 0; c < n; c++) {
if (mat[r][c] == 0) continue;
int top = INF, left = INF;
if (r – 1 >= 0) top = mat[r – 1][c];
if (c – 1 >= 0) left = mat[r][c – 1];
mat[r][c] = min(top, left) + 1;
}
}
for (int r = m – 1; r >= 0; r–) {
for (int c = n – 1; c >= 0; c–) {
if (mat[r][c] == 0) continue;
int bottom = INF, right = INF;
if (r + 1 < m) bottom = mat[r + 1][c];
if (c + 1 < n) right = mat[r][c + 1];
mat[r][c] = min(mat[r][c], min(bottom, right) + 1);
}
}
return mat;
}
};
Java 01 Matrix LeetCode Solution
class Solution { // 5 ms, faster than 99.66%
public int[][] updateMatrix(int[][] mat) {
int m = mat.length, n = mat[0].length, INF = m + n; // The distance of cells is up to (M+N)
for (int r = 0; r < m; r++) {
for (int c = 0; c < n; c++) {
if (mat[r][c] == 0) continue;
int top = INF, left = INF;
if (r – 1 >= 0) top = mat[r – 1][c];
if (c – 1 >= 0) left = mat[r][c – 1];
mat[r][c] = Math.min(top, left) + 1;
}
}
for (int r = m – 1; r >= 0; r–) {
for (int c = n – 1; c >= 0; c–) {
if (mat[r][c] == 0) continue;
int bottom = INF, right = INF;
if (r + 1 < m) bottom = mat[r + 1][c];
if (c + 1 < n) right = mat[r][c + 1];
mat[r][c] = Math.min(mat[r][c], Math.min(bottom, right) + 1);
}
}
return mat;
}
}
Python 3 01 Matrix LeetCode Solution
class Solution: # 520 ms, faster than 96.50%
def updateMatrix(self, mat: List[List[int]]) -> List[List[int]]:
m, n = len(mat), len(mat[0])
for r in range(m):
for c in range(n):
if mat[r][c] > 0:
top = mat[r – 1][c] if r > 0 else math.inf
left = mat[r][c – 1] if c > 0 else math.inf
mat[r][c] = min(top, left) + 1
for r in range(m – 1, -1, -1):
for c in range(n – 1, -1, -1):
if mat[r][c] > 0:
bottom = mat[r + 1][c] if r < m – 1 else math.inf
right = mat[r][c + 1] if c < n – 1 else math.inf
mat[r][c] = min(mat[r][c], bottom + 1, right + 1)
return mat
Array-1180
String-562
Hash Table-412
Dynamic Programming-390
Math-368
Sorting-264
Greedy-257
Depth-First Search-256
Database-215
Breadth-First Search-200
Tree-195
Binary Search-191
Matrix-176
Binary Tree-160
Two Pointers-151
Bit Manipulation-140
Stack-133
Heap (Priority Queue)-117
Design-116
Graph-108
Simulation-103
Prefix Sum-96
Backtracking-92
Counting-86
Sliding Window-73
Linked List-69
Union Find-66
Ordered Set-48
Monotonic Stack-47
Recursion-43
Trie-41
Binary Search Tree-40
Divide and Conquer-40
Enumeration-39
Bitmask-37
Queue-33
Memoization-32
Topological Sort-31
Geometry-30
Segment Tree-27
Game Theory-24
Hash Function-24
Binary Indexed Tree-21
Interactive-18
Data Stream-17
String Matching-17
Rolling Hash-17
Shortest Path-16
Number Theory-16
Combinatorics-15
Randomized-12
Monotonic Queue-9
Iterator-9
Merge Sort-9
Concurrency-9
Doubly-Linked List-8
Brainteaser-8
Probability and Statistics-7
Quickselect-7
Bucket Sort-6
Suffix Array-6
Minimum Spanning Tree-5
Counting Sort-5
Shell-4
Line Sweep-4
Reservoir Sampling-4
Eulerian Circuit-3
Radix Sort-3
Strongly Connected Componen-t2
Rejection Sampling-2
Biconnected Component-1
