Python Recursion Issue (Leetcode 542)

Question

I think I misunderstand some important concepts in Python and it is not specific to the Leetcode problem. I greatly appreciate for any help from who knows Python deeply.

The Leetcode 542 is that given a 2D array consisting of 0 and 1 only, and for each 1, find the shortest distance to reach 0. I have a dummy DFS solution:

  class Solution:
    def updateMatrix(self, matrix):
     
      dists = []
      for _ in range(len(matrix)):
          dists.append([0]*len(matrix[0]))
    
      for y in range(len(matrix)):
          for x in range(len(matrix[0])):
              if matrix[y][x] == 1:
                  self.min_dist = len(matrix)+len(matrix[0])
                  self.DFS(x, y, matrix, 0, set({}))
                  dists[y][x] = self.min_dist
                
      return dists

    def DFS(self, x, y, matrix, distance, visited):
    
      if (x, y) in visited or (matrix[y][x] == 1 and distance > self.min_dist): return
    
      if matrix[y][x] == 0:
          print (x, y, "d:", distance)
          print ('------')
          self.min_dist = min(self.min_dist, distance)
          return 
    
      print (x, y, distance)
    
      visited.add((x, y))
    
      if x > 0 and (x-1, y) not in visited: 
          self.DFS(x-1, y, matrix, distance+1, visited)
        
      if y > 0 and (x, y-1) not in visited: 
          self.DFS(x, y-1, matrix, distance+1, visited)
   
      if x < len(matrix[0])-1 and (x+1, y) not in visited: 
          self.DFS(x+1, y, matrix, distance+1, visited)
   
      if y < len(matrix)-1 and (x, y+1) not in visited: 
          self.DFS(x, y+1, matrix, distance+1, visited)
   

Simply DFS until reaching 0. Every time we call DFS, distance + 1. It looks good to me. But a test case input = [[1,0,0],[0,1,1],[1,1,1]] gives me dist = [[1,0,0],[0,1,1],[1,2,3]].

If change matrix[y][x] == 1 to matrix[y][x] == 1 and x==2 and y==2 and run the above code, the output is

 2 2 0
 1 2 1
 0 2 2
 0 1 d: 3
 ------
 1 1 2
 0 1 d: 3
 ------
 1 0 d: 3
 ------
 2 1 3
 2 0 d: 4
 ------

At (x,y)= (2,1) the initial distance is changed to 3. but the initial distance at (2,1) should be 1. My question is why it changes? Can anyone help me point out where I did wrong? Thanks!

Answer 1

First of all I want to point out that DFS, as well as BFS, is mainly used for searching in trees; indeed, you can think your matrix as a particular tree, but I wouldn't go that path for this task because you don't need to search but rather to keep track of some distance with respect to all of your neighbors, parents and children.
Moreover, with DFS you will need to traverse your matrix many times to find the minimum for every 1s and that's very inefficient.

Regarding your question, if you keep track of stack you're creating, you will get:

 2 2 0
 1 2 1
 0 2 2
 0 1 d: 3
 ------
 back to (0, 2), with distance = 2
 (1, 2) already visited
 back to (1, 2) with distance = 1
 1 1 2
 0 1 d: 3
 ------
 back to (1, 1) with distance = 2
 1 0 d: 3
 ------
 back to (1, 1) with distance = 2
 2 1 3
 2 0 d: 4

Back to your task, since you're using python I would tackle this task by using numpy, and look for 1s and 0s using np.where(matrix == 0). Then it's just a matter of doing some calculus:

import numpy as np


class Solution:

    def update_matrix(self, matrix):
        matrix = np.array(matrix)

        x_ones, y_ones = np.where(matrix == 1)
        x_zeros, y_zeros = np.where(matrix == 0)

        for i in range(len(x_ones)):
            temp = []

            for j in range(len(x_zeros)):
                temp.append(abs(x_ones[i] - x_zeros[j]) + abs(y_ones[i] - y_zeros[j]))

            matrix[x_ones[i], y_ones[i]] = min(temp)

        return matrix.tolist()

If you must not use external libraries, just proceed as follows:

class Solution:

    def update_matrix(self, matrix):
        x_ones, y_ones = [], []
        x_zeros, y_zeros = [], []

        # First scan to save coordinates
        for i in range(len(matrix)):
            for j in range(len(matrix[0])):
                if matrix[i][j] == 1:
                    x_ones.append(i)
                    y_ones.append(j)
                else:
                    x_zeros.append(i)
                    y_zeros.append(j)

        for i in range(len(x_ones)):
            temp = []

            for j in range(len(x_zeros)):
                temp.append(abs(x_ones[i] - x_zeros[j]) + abs(y_ones[i] - y_zeros[j]))

            matrix[x_ones[i]][y_ones[i]] = min(temp)

        return matrix

Answer 2

Been taking a look at this. It seems the problem is the way the visited set is modified. I think it's being passed by reference which means by the time it tries to go (2,2) -> (2,1) the set already contains the point (2,1), i.e the preceding DFS paths have added all their points to it.

I found this article explains "Pass By Reference in Python" well - https://realpython.com/python-pass-by-reference/.

I got your test case to pass by always passing down visited.copy(), i.e self.DFS(x-1, y, matrix, distance+1, visited.copy()). I'm not a Python expert and imagine there are cleaner ways to handle this though.

Answer 3

You don't really need recursion for this. You can simply queue positions that need to update their neighbours and keep updating/queuing positions until no more updates are made:

def getDistances(matrix):
    rows,cols = len(matrix),len(matrix[0])
    maxDist   = rows*cols+1 # start 1's at maximum distance
    result    = [[maxDist*bit for bit in row] for row in matrix]
    more      = { (r,c) for r,row in enumerate(matrix)
                        for c,bit in enumerate(row) if bit == 0}
    while more: # process queue starting with zero positions
        r,c     = more.pop()
        newDist = result[r][c]+1 # neighbours are at distance+1 from here
        for nr,nc in [(r,c+1),(r,c-1),(r+1,c),(r-1,c)]: # 4 directions
            if nr not in range(rows): continue
            if nc not in range(cols): continue            
            if newDist >= result[nr][nc]: continue 
            result[nr][nc] = newDist  # reduce neighbour's distance
            more.add((nr,nc))         # queue neighbour to cascade updates
    return result

output:

m = [[0,0,0,0,0,1],
     [0,1,1,0,0,0],
     [1,1,1,1,0,1],
     [1,1,1,1,1,0]]

for r in getDistances(m): print(r)
                  
[0, 0, 0, 0, 0, 1]
[0, 1, 1, 0, 0, 0]
[1, 2, 2, 1, 0, 1]
[2, 3, 3, 2, 1, 0]