Real-omn-dp-dfsbfs-top-solutions-are-not-omn

It is amazing how many graph, tree and string problems simply boil down to a DFS [Depth-first search] / BFS [Breadth-first search]. Today we are going to explore this basic pattern in a novel way and apply the intuition gained to solve some medium problems on Leetcode.

Let us build on top of pattern 0. First of, a tree can be thought of as a connected acyclic graph with N nodes and N-1 edges. Any two vertices are connected by exactly one path. So naturally the question arises, what about a DFS or a BFS on binary trees ? well there are 6 possible DFS traversals for binary trees [ 3 rose to fame while the other 3 are just symmetric ]

1. left, right, root [ Postorder] ~ 4. right, left, root
2. left, root, right [ Inorder] ~ 5. right, root, left
3. root, left, right [ Preorder] ~ 6. root, right, left

And there is one BFS which is the level order traversal [ can be done using queue]. Let us analyze the DFS pattern using a stack which we are already familiar with.

DFS is all about diving as deep as possible before coming back to take a dive again. Below is the iterative DFS pattern using a stack that will allow us to solve a ton of problems. [ iterative introduced first so as to develop intuition]

DFS magic spell: 1]push to stack, 2] pop top , 3] retrieve unvisited neighbours of top, push them to stack 4] repeat 1,2,3 while stack not empty. Now form a rap !

144. Preorder Traversal

Let’s walk through the above spell using an example tree.

Two things to ponder on as we move further:

1] Why are we using stack for DFS , couldn’t we use a queue ? [ always remember : stack for DFS, imagine a vertical flow | queue for BFS, horizontal flow, more on this later]

2] How do we extend this DFS process to general graphs or graphs disguised as matrices [ as in most LC problems]. [ Include a mechanism to track visited]

323. Number of Connected Components in an Undirected Graph

The base problem upon which we will build other solutions is this one which directly states to find the number of connected components in the given graph. We could use DFS / BFS to solve this. Below is the DFS code using the stack spell.

200. Number of Islands

This falls under a general category of problems where in we just need to find the number of connected components but the details could be twisted.

The intuition here is that once we find a “1” we could initiate a new group, if we do a DFS from that cell in all 4 directions we can reach all 1’s connected to that cell and thus belonging to same group. We could mark these as visited and move on to count other groups. One optimization here is that we don’t need the matrix later so we could as well destroy the visited cells by placing a special character saving us extra memory for the visited array.

Even if we needed the matrix later one could always restore the original value after the dfs call. Below is a simple recursive DFS solution.

547. Friend Circles

Same concept, find connected components. The only twist is that the connected neighbors are presented in a different form. Here we don’t destroy the matrix, but use an array to keep track of visited [ friendZoned ]. Notice the stack pattern, it is exactly the same as in connected components problem. All that changes is the way neighbors are defined. If we were to write an iterative version for the islands problems, it would also be very similar.

I broke this post into 2 parts as it got too long, I will visit BFS in the next part. So let’s conclude this part by pondering on why we always use stack for dfs and queue for bfs. Have you ever wondered why we don’t use queue for dfs or stack for bfs? questions like these really give us some insights on the difference between stacks and queues.

So using a stack I could pop 2 and push it’s kids and keep doing so eventually exhausting 2’s subtrees, 3 stays calmly in the stack just below the part where the real push-pop action is going, we pop 3 when all subtrees of 2 are done. This feature of stack is essential for DFS.

While in a queue, I could dequeue 2 and enqueue it’s subtrees which go behind 3 as it was already sitting in the queue. So the next time I dequeue I get 3 and only after that do I move on to visiting 2’s subtrees, this is essentially a BFS !

For me this revelation was pure bliss. Take a moment to celebrate the history of Computer Science and the geniuses behind these simple yet powerful ideas.

//people.idsia.ch/~juergen/bauer.html

Do comment your views and feel free to connect with me on LI : //www.linkedin.com/in/sourabh-reddy

I think this problem is very classic with high frequency in tech interviews. It involves with DFS/BFS and Dynamic Programming [DP]. Let's get started with this problem!

1. Read the Problem

We are given an m x n binary matrix. We are to return the distance of the nearest 0 for each cell. The distance between two adjacent cells is 1.

For example, given mat = [[0,0,0],[0,1,0],[1,1,1]], we need to return [[0,0,0],[0,1,0],[1,2,1]]

• For the middle cell, result[1][1], it is still 1 because the nearest 0 for this cell is on its left, right OR top, so the shortest distance is 1.
• For result[2][1], the nearest 0 is either going:

- top > top

- left > top

- right > top

The distances for all these paths are 2. Therefore at result[2][1], we'll have a 2.

2. Figure Out the Target [ What do we really want?]

Our goal is to find all 1s. If we find a 1, then we should check all four directions [top, left, right &bottom] to see if we find any 0s. If we do, we immediately know the answer is 1 because we've found the nearest 0.

🤔 But what happens if all four directions of a particular cell are all non-zeroes? In that case, we will need to go visit all cells from all four directions and repeat the same process again, which is to check the cells in all four directions for a value of zero! ....

Now, what is the first thing comes into your mind? It seems like we can use Depth First Search [DFS], doesn't it?

Hold on a second! Even though DFS [brute force way😅] might solve this problem, it will not be the optimal solution because

• we are not trying to explore all possible paths. Once we find a zero, we can just return the distance from it. In that case, we are not interested in the rest of the directions.
• it's very time inefficient - O[N^2] where N = m x n

Imagine if your interviewer asks you to improve the efficiency, what would you do? 😅

Let's think about our target again 💪

Our goal was to find all 1s, right? How about finding all 0s instead? But why?

If we were to find all 1s and then to search for any zeroes from all directions [like what we originally did above], we could only find the distance for that cell only.

BUT, if we find all 0s and go outward finding the 1s, we can find at most FOUR distances at a time!

3. What Data structure & Algorithms?

We are going to find all zeroes. Then we will ask each of the zero -Do you have 1s in your neighbors [four directions]? If so, please tell your neighbors to update their numbers to be [your number + 1] which is 1.

As our goal is not to find all possible paths or outcomes, instead of using a DFS, a Breadth-First Search [BFS] would be a better choice here.

And we know to implement a BFS, we often use a queue. It's like pizza and cheese. 🤡

And we definitely need to keep track of all visited cells. You don't want to search over and over again to the same cell which might ruin our solution here.

But instead of using a Set, I will be changing all 1s to a specific value. When we later search for the 1s, instead we will search for that specific value.

* You could use a set. It's going to the same. I'm just trying to be special here 😛

* Please ask interviewer if you are allowed to mutate the input array because I'm going to mutate it anyway 🫢

Algorithms:

1. Define a queue array.
2. Loop over the matrix, if the cell is a zero, add the coordinates [i, j] to the end of the queue. If it is a one, change the value to be "#". [ It could be anything. You'll see why we do that].
3. Loop over the queue, pop off the first element of the queue and check its neighbors [top, left, right, bottom] for the value "#". If we find it, then re-assign that neighbor's value to be the the popped element's number + 1. Then add the coordinates of the neighbors to the queue

Walk-Through:

- Step 1

We will add the coordinates of all zeroes to our queue. And change all ones to "#" in one pass. Our matrix &queue will become:

- Step 2

We will pop the first element in the queue and search for "#" in four directions.

Assume we are at "here" now. We will check its right and bottom. We do not find a "#", so we do nothing. Let's fast-forward a bit.

Now we are at [1,0], again we will check its right and bottom. We see a "#" on the right. That's exciting! Let's re-assign this value to be the value at [1,0] + 1 = 1. Now it becomes

We'll do the same on its bottom cell. Same logic and result and it becomes

We'll then add both coordinates [1,1] and [2,0] to the end of our queue.

queue was = [ [0,0], [0,1], [0,2], [1,0], [1,2] ]

Queue now is = [ [1,2] , [1,1], [2,0] ]

- Step 3 [keep looping]

...

...

At all three locations in the queue, we do not find "#" so we stop and return the result.

Complexity

We basically search the whole matrix for all zeroes and add them to the queue. And we also perform a BFS with the elements in queue.

Time Complexity: O[m x n] , where m = number of the rows and n = number of the columns.

Space Complexity: O[m x n] due to the queue we used.

Actual Code in Python:

class Solution: def updateMatrix[self, mat: List[List[int]]] -> List[List[int]]:

queue = deque[]
row = len[mat]
col = len[mat[0]]
for i in range[row]:
  for j in range[col]:
    if mat[i][j]==0:
      queue.append[[i,j]]
    else:
      mat[i][j]="#"
while queue:
  i,j = queue.popleft[]
  for dx,dy in [1,0],[-1,0],[0,1],[0,-1]:
    newX = dx+i
    newY = dy+j
    if newX>=0 and newX=0 and newY