I'm working on LeetCode 1582. Special Positions in a Binary Matrix. How could I make a function that uses recursion and DFS to return the count of how many special positions are in a m x n binary matrix. A position (i, j) is called special if matrix[i][j] == 1 and all other elements in row i and column j are 0 (rows and columns are 0-indexed).
Example 1
Input: mat = [[1,0,0],[0,0,1],[1,0,0]]
Output: 1
Explanation: (1, 2) is a special position because mat[1][2] == 1 and all other elements in row 1 and column 2 are 0.
Example 2
Input: mat = [[1,0,0],[0,1,0],[0,0,1]]
Output: 3
Explanation: (0, 0), (1, 1) and (2, 2) are special positions.
This is what I have so far, but I am stumped on how to correctly execute the DFS recursion given this problem.
class Solution:
def numSpecial(self, mat: List[List[int]]) -> int:
count = 0
for ir, rval in enumerate(mat):
for ic, cval in enumerate(rval):
if cval == 1:
if self.dfs([ir, ic], mat):
count += 1
return count
def dfs(self, idx, mat):
if self.isvalid(idx, mat):
if mat[idx[0]][idx[1]] != 0:
return False
else:
north = [idx[0]-1, idx[1]]
self.dfs(north)
south = [idx[0]+1, idx[1]]
self.dfs(south)
east = [idx[0], idx[1]+1]
self.dfs(east)
west = [idx[0], idx[1]-1]
self.dfs(west)
return True # dont know if and where I should put this return True
def isvalid(self, idx, mat):
if idx[0] in range(0,len(mat)):
if idx[1] in range(0,len(mat[0])):
return True
return False
Also, I understand that there are many simpler ways to solve this problem, but I just want to be able to solve it using DFS recursion like how I was attempting to above
Ok, so this code works. I had to add a bit of stuff. A couple of global variables which are a bit naughty, but I don't know how to do it without them.
One is simply the number of ones we have come across in our DFS search so far. We want this to be exactly 1 after our DFS has finished. That being the cell we start the DFS from.
And I use a 2D array of booleans to keep track of where the search has already been otherwise it would go on forever.
Note that I also added a check to the isvalid routine to make sure we're only considering the values in the same row or column as the cell we're checking.
# Evil global variables
numOnesFound = 0
visited = []
class Solution:
def numSpecial(self, mat: List[List[int]]) -> int:
global numOnesFound
global visited
count = 0
for rowIndex, row in enumerate(mat):
for colIndex, colValue in enumerate(row):
if colValue == 1:
numOnesFound = 0
visited = [[False for x in range(len(mat[0]))] for y in range(len(mat))]
self.dfs([rowIndex, colIndex], [rowIndex, colIndex], mat)
if numOnesFound == 1:
count += 1
return count
def dfs(self, startingPosition, idx, mat):
global numOnesFound
global visited
if numOnesFound >= 2:
return
if self.isvalid(startingPosition, idx, mat):
if visited[idx[0]][idx[1]]:
return
visited[idx[0]][idx[1]] = True
if mat[idx[0]][idx[1]] != 0:
numOnesFound += 1
north = [idx[0]-1, idx[1]]
self.dfs(startingPosition, north, mat)
south = [idx[0]+1, idx[1]]
self.dfs(startingPosition, south, mat)
east = [idx[0], idx[1]+1]
self.dfs(startingPosition, east, mat)
west = [idx[0], idx[1]-1]
self.dfs(startingPosition, west, mat)
return
def isvalid(self, startingPosition, idx, mat):
# Check to see if we're in the same column or same row as the startingPosition
if idx[0] == startingPosition[0] or idx[1] == startingPosition[1]:
# Check to see the indexes are within 0->height 0->width
if idx[0] in range(0,len(mat)):
if idx[1] in range(0,len(mat[0])):
return True
return False