> For the complete documentation index, see [llms.txt](https://joshualbarb.gitbook.io/leetcode-problems/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://joshualbarb.gitbook.io/leetcode-problems/graphs/01-matrix.md).

# 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.

![](/files/-MRLLz7V6aK1Dy4t5g5i)

### Thought Process

* BFS
* Store 0's in the queue so we can look at their neighbors

## Solution

{% tabs %}
{% tab title="Using visited set" %}

```
from collections import deque
class Solution:
    def updateMatrix(self, matrix: List[List[int]]) -> List[List[int]]:
        
        q = deque()
        visited = set()
        
        for i in range(len(matrix)):
            for j in range(len(matrix[0])):
                if matrix[i][j] == 0:
                    q.append([i,j])
                    visited.add((i,j))
                    
        d = [[1,0], [-1, 0], [0,1], [0,-1]]     
        while q: 
            node = q.popleft()
            x = node[0]
            y = node[1]
            for i in d:
                newX = x+i[0]
                newY = y+i[1]
                
                    
                if newX < 0 or newX >= len(matrix) or newY >= len(matrix[0]) or newY < 0 or (newX, newY) in visited:
                    continue
                
                matrix[newX][newY] = matrix[x][y]+1 
               
                q.append([newX, newY])
                visited.add((newX, newY))
                
                        
        return matrix
                
            
```

{% endtab %}

{% tab title="Not using visited set" %}

```
from collections import deque
class Solution:
    def updateMatrix(self, matrix: List[List[int]]) -> List[List[int]]:
        
        q = deque()
        
        for i in range(len(matrix)):
            for j in range(len(matrix[0])):
                if matrix[i][j] == 0:
                    q.append([i,j])
                else:
                    matrix[i][j] = float('inf')
                    
        d = [[1,0], [-1, 0], [0,1], [0,-1]]     
        while q: 
            node = q.popleft()
            x = node[0]
            y = node[1]
            for i in d:
                newX = x+i[0]
                newY = y+i[1]
                
                    
                if newX < 0 or newX >= len(matrix) or newY >= len(matrix[0]) or newY < 0 or matrix[newX][newY] <= matrix[x][y]+1:
                    continue
                
                matrix[newX][newY] = matrix[x][y]+1 
               
                q.append([newX, newY])
                
                        
        return matrix
                
            
```

{% endtab %}
{% endtabs %}

* Notice here we don't care about the "deepest level" or using levels in anyways (like in Rotting Oranges or As Far Land As Possible). This is why we don't utilize the levels in this BFS problem

## Time Complexity

* **Time:** O(n\*n)
* **Space:** O(n\*n) since we are storing all the 0's and 1's in the queue