01 Matrix

Links

Go to my solution
Go to the question on LeetCode

What Went Well
I knew the algorithm which had to be used but forgot how to implement it.

What I Learned
I learned about the breadth-first search algorithm and the very special way to alter it so it can be applied to this problem.

How I Can Improve
Brushing up on my algorithms will help me with algorithm-focused problems.

Comments
The implementation of breadth-first search in this question is strange because instead of using a queue, we are using a deque, which is the complete opposite of a queue, the data structure typically used for breadth-first search.

Algorithm Description

Breadth-first search - A graph/matrix traversal algorithm that searches for elements with a given property. In this example, that property is a node with the value of -1. It creates a deque of elements yet to be visited and then iterates through each level (similar elements) until there are no more elements to iterate through. In this problem, these levels would be: 0 - our starting elements, 1 - the first non-visited elements found, 2 - the non-visited elements found while iterating through level 1, 3 - the non-visited… and so on.

The proper definition for breadth-first search when not being applied to this specific problem can be found here.

Visual Examples
Example of the algorithm on the matrix

[ [1,0,1]
  [1,1,1]
  [0,0,1] ]

Click to view

Yellow = The visited node
Green = Newly visited nodes

Note that the algorithm does not stop where the visual does. I did not want to pay for the software and could not add more matrices. The algorithm continues checking each pair in the deque even if there are no more nodes to change.

Solution Statistics

Time Complexity
O(n * m) - We must re-assign the value of each element in the matrix, causing O(n * m) and iterate through at most n * m - 1 elements. Since we ignore constants and multiples of the time/space complexities, the resulting time complexity is O(n * m).

Space Complexity
O(n * m) - The largest number of pairs added to the deque would be n * m -1 because the problem’s constraints require at least one 0 to be in the matrix. Since we ignore constants and multiples of the time/space complexities, the resulting space complexity is O(n * m).

Runtime Beats
81.17% of other submissions

Memory Beats
87.10% of other sumbissions

Solution

class Solution:
    def updateMatrix(self, matrix: List[List[int]]) -> List[List[int]]:
        # Initialize variables
        deq = deque()   # Time complexity to pop from the 0th index is O(1) compared to an array which is O(n)
        rowMax = len(matrix)
        colMax = len(matrix[0])

        # Append matrix elements that are 0 to the deque
        # If not equal to 0, then set the element to -1
        for n in range(rowMax):     # O(n)
            for m in range(colMax): # O(m)
                if matrix[n][m] == 0:
                    deq.append((n, m))
                else:
                    matrix[n][m] = -1

        # Loop until the deque is empty
        while deq:
            # Place current x and y into variables
            x, y = deq.popleft()    # O(1)

            # Iterate through each possible direction
            for r, c in [(1, 0), (-1, 0), (0, 1), (0, -1)]:

                # Add current direction to the current position
                newX, newY = x+r, y+c

                # Check if the new variables are within the matrix
                # &&
                # Check if the new element has not yet been visited (== -1)
                if 0 <= newX < rowMax and 0 <= newY < colMax and matrix[newX][newY] == -1:

                    # Since we begin at each of the 0's in the matrix, all the first elements visited are set to 1
                    # We now append every newly visited element, causing any element visited to be set to 2
                    # Continue this trend until all elements have been visited
                    matrix[newX][newY] = matrix[x][y] + 1
                    deq.append((newX, newY))

        return matrix