Hi there! It’s been so long since my last post and my life has undergone so many changes during these past few months :), it’s insane! The one constant that remains is people reading these blogs and reaching out to me on LinkedIn to provide feedback, it makes my day!

I graduated from university, started a new job, shifted all the way from Florida to Bay Area (finally woohoo!), moved into a new house, it was crazy!

So I wanted to pause for a moment and look back, provide some context on why I started the blog, what it means to me and some plans I have to extend the blog, now that I am all settled in.

Please provide feedback in the comments section of the video. If you’re in bay area and would like schedule a coffee chat send me a ping, Thanks!

-csgator

Leetcode Patterns : Checkpoint 0 was originally published in Leetcode Patterns on Medium, where people are continuing the conversation by highlighting and responding to this story.

Problem Solving Approach

Think about the problem for at least 30 minutes and put in your best efforts to solve the problem on your own. Think through the test cases, imagine how you would be writing code and write the code without IDE. Try to minimize the use of a compiler. It’s important to write bug-free code without using a compiler for big N companies. I’ll explain below why I mention these very specific points ( some of which might have freaked you out ).

Why the 30-minute mark?

The thinking part is really important, can’t emphasize this enough! I didn’t have a lot of patience early on and would just try to optimize the number of problems seen over learning. I would look up solutions after 10 minutes of sloppy efforts. After a few times of doing this, I wouldn’t think at all and would just reach out for the discuss tab.

There is a bit of learning that can happen through this process but there is a huge loss too. For example, I was asked the meeting rooms problem in an interview (it is a frequently asked problem in one of the FAANG’s! ) and instead of thinking about the problem at hand I would try to retrieve the solution from the buggy in-memory hashtable I built over time.

The more you struggle with a problem the more you’ll learn after seeing the solution and best case is if you look at the solution after solving it on your own. Try to improve your thinking abilities, because it’s very likely that when you face the same problem weeks later you’ll not remember the solution and you’ll most definitely think in a similar way you did the first time. So if you learned the paradigm required to solve that problem and solved a lot of other similar problems using that strategy you’ll actually be able to solve it later.

The worst part is it’s hard to realize if this is happening subconsciously, so as a litmus test I would say try resolving random problems from past practice after a set amount of time. Spaced repetition also helps consolidate your learnings ( firecode.io is popular because of this very fact )

In real life, there is always a time constraint, interviews coming up, limited time available in the day due to coursework, and so many patterns to learn which is why it’s a tradeoff and I suggested the 30-minute limit, you could play with it depending on how much time you have at hand. You need to realize that it’s not about the number of problems you solved before an interview but if you are able to apply your learnings to a new problem in an interview setting.

Don’t think that you need to solve all problems on leetcode that would be crazy and if you do it the correct way you won’t need to solve more than 300–400 problems to be confident for a full-time interview, 150 for internships with a good balance of mediums , few hards and fewer easy ( a realistic average case figure, not talking about outliers who only did 70 lc problems to land a big N offer ). Most problems are repetitive anyway, same logic applied with a 1–2 line change. Focus on learning core paradigms ( DP, graphs, backtracking, trees, etc )

It is fine if you’re not able to solve a problem but it is important that you’re able to solve a similar problem after absorbing the approach for the current problem.

Test your code

In a real interview you would tell your approach to the interviewer and if he/she is satisfied with your approach you’ll be writing code, then the interviewer would likely ask you the time and space complexities and finally many interviewers ask you to write test cases. It’s hard to do TDD ( test driven development) and only the people who train themselves to do so can replicate that in interviews. So in my case, I would write code then write/think about test cases later.

But the best programmers I’ve seen would go through the test cases first to arrive at an approach. The code they write will cover the corner cases too cause they thought through the test cases first and interviewers are generally impressed with that approach. It also helps us to make sure that we understood the problem correctly and I could go on and on, just write/think through test cases first if possible :), if not at least do so before submitting your code. Avoid doing this: click submit, get WA ( wrong answer) fix failing test case, repeat loop until an AC ( accepted ) that’s a really crappy thing to do and TDD would likely help you avoid it.

Why not use an IDE?

That’s totally up to you but I suggested so because many people are so IDE dependent that they are practically crippled if someday they had to write code using notepad. Google interviews take place in google docs and I understand the principles behind this weird decision. If you are really good at the language you code in and have used it to for a while, you tend to internalize the language. If you let go of the over usage of IDEs and language references you’ll most likely become a better programmer but that’s debatable so I’ll leave it at that.

Definitely reduce compiler usage!!

Why? because when you restrict yourself to not use the compiler, you read through your code and try to mentally compile it, spotting logic and syntax errors on your own. With enough practice, you don’t even make those errors and you tend to code faster. That to me is a sign of a good programmer and interviews are all about getting signals if you are good enough for the job :). This is not a strict requirement but I would say it’s good to set high standards for yourself and get out of your comfort zone.

Facebook interviewers look for this skill ( conclusion based on limited data points ) and most interviewers are sharp enough to look at your code and tell you where your bugs are. Can you spot and fix those bugs without compiling?

General tips

Do look at solutions posted in discuss after solving the problem or if you’re stuck. You’ll learn a lot by going through a few solutions, probably learn different styles of writing the same thing or learn different approaches all together. Leetcode discuss is gold and I attribute most of my learnings to discuss. Maintain a github repo where you could keep adding your solutions, an active github chart looks good to whoever visits your profile!

Don’t look at problem tags until you are stuck! that’s part of the problem-solving process to figure out what category the problem falls into. Alternatively to get good at a specific paradigm pick problems from that tag and keep solving until you get comfortable. It’s a mix of these two opposite approaches being applied alternatively that’ll set you up for success in your big N interview.

Maintain a google doc / excel sheet or use leetcode notes feature where you record why you couldn’t solve it, what you learned through that problem, time to get AC including time to write code, time spent to think, number of times you clicked run code, number of submissions to get AC, etc. Such statistical analysis will definitely improve your skills over time.

Leetcode contests for the win!

I highly recommend doing contests every Saturday, because you’ll be trying to code faster as it is timed and there is a ranking system based on how quickly you get AC and penalties for buggy submissions. After doing enough contests you’ll rise in ranks, improve your rating and it’ll give you an adrenaline rush to keep going. They also post official solutions after a few hours which are nicely written. Most leetcode contest problems were popular interview questions in the time period the contest was conducted so definitely do contests regularly :)

Lesser known fact, if you do well in leetcode contests some companies will directly contact you for an interview. If you get a rank within 200 ( possible with enough practice on leetcode) that’s definitely worth mentioning on your resume as well.

Applying

At one point you’ll realize that you’re comfortable with solving problems but if you don’t get interviews you won’t land your big N job. This topic deserves its own article but here’s the gist:

1. Resume format doesn’t matter much but the content is what matters. Keep it simple and readable, no colors or logos. Use careercup’s simple template and worship this article, IT WORKS!
2. Always apply through referrals and don’t think that your network is limited, use LinkedIn the right way and make connections. Most people will refer you if you’re good enough cause it feels good to help a person out and also that referral bonuses are huge. It’s a win-win situation for the company avoiding high recruiting agency costs, you and the person who refers you, think about it!
3. Follow point 1 and shoot your resumes to recruiters on LinkedIn or email. Many recruiters are actively looking for candidates on LinkedIn. I got my Uber interview after I contacted a recruiter directly.
4. Brands definitely matter, so once you get that big N internship/work experience it’s really easy to get interviews, otherwise highlight your personal projects, course projects, open source experience, hackathon wins, whatever convinces a person in one glance that you are worth giving an interview/referral at least.

Point 4 is all about getting signals if you are good enough as a developer so whatever you can do to prove to the world that you’re good enough. In my case, I didn’t have any work experience so I wrote articles about solving algorithm problems and shared them on Linkedin :). I had GSoC on my resume which was an important factor and I put my personal projects on top. Keep experimenting with your resume format until it works and you get interviews.

People complain that they applied for 400+ jobs online and got no callbacks. It doesn’t matter how many jobs you applied to, a more realistic statistic is to consider how many interviews you had ( through whatever, cold emails, referrals, online apps ). Applying online is like brute force, you can’t say you brute forced enough but are still getting a TLE, come up with smarter approaches to beat the crowd.

Thanks for reading so far, you’re awesome! That’s it for this article and I’ll end it with something that I had on my mind for a long time.

Youtube Channel

I’ve always wanted to make algorithm tutorials. Over time I’ve come to like algorithms and leetcoding is no longer an activity I pursue to get a good job. It is something I do out of my own interest, which I consider to be the best reason to do something, allows you to get really good at that thing with lower effort. Now that I have a job lined up and lighter course load I have a lot of time on my hands to actually work on this project.

More specifically I want a low effort thing where I can help people get good at leetcode style problems and understand core algorithms. I am a big fan of youtube, it is the primary activity of my day and I realize the kind of effort that goes into recording and editing videos. I plan to stick with simple screencasts and a whiteboard where I could explain an algorithm and solve a few leetcode problems using that algorithm.

Why low effort ? because I would be able to keep doing it in a sustained manner, meaning more content produced overall and more topics covered. In the past, I’ve received a lot of positive feedback for this series and I would love to continue this but it’s a lot of effort to write articles and it’s easier to convey information in the form of video. I am trying to measure interest in this project so please do leave a comment or send me a message on LinkedIn to let me know what you think about this :)

Fun facts :

1. I never had taken a formal algorithms course until this semester and my undergrad was in Electronics.
2. Leetcode’s founder Winston Tang had developed the website for his own use while he was prepping for interviews.
3. Never gets old -> https://www.youtube.com/watch?v=wZR6QFE2m6o

Leetcode Pattern 4 | Meta Stuff was originally published in Leetcode Patterns on Medium, where people are continuing the conversation by highlighting and responding to this story.

Backtracking can be seen as an optimized way to brute force. Brute force approaches evaluate every possibility. In backtracking you stop evaluating a possibility as soon it breaks some constraint provided in the problem, take a step back and keep trying other possible cases, see if those lead to a valid solution.

So in fact, it’s kinda like a depth-first search(DFS) with an added constraint that we stop exploring the subtree as soon as we know for sure that it won’t lead to valid solution. The problems that can be solved using this tool generally satisfy the following criteria :

1. You are explicitly asked to return a collection of all answers.
2. You are concerned with what the actual solutions are rather than say the most optimum value of some parameter. (if it were the latter it’s most likely DP or greedy).

78. Subsets

We’ll use this problem to get familiar with the recursive backtracking pattern.

The problem is to find the powerset of a given set, so we simply need to collect all possible subsets of a set. This could be done in a variety of ways and backtracking is one way to go, also since there are no constraints provided we simply explore all cases (all subsets).

A subset can either have an element or leave it out giving rise to 2^n subsets.

Take a moment to absorb the magic happening in the loop and that’s everything you’ll ever need to solve a backtracking problem. It was confusing to me at first but it’s an amazing pattern. Drawing the flow of the recursive function helped me wrap my head around what is going on.

Also here is my alternative solution to the same problem which uses the partially formed output to generate the full output incrementally. It’s basically deriving the complete solution from solutions of smaller problems, does it ring a bell?

90. Subsets II

Same problem with the added constraint that the set may contain duplicates but the output power set should not contain duplicate subsets.

Approach: Sort the given array beforehand and skip over duplicates while backtracking, essentially a simple 2 line change in the previous solution.

39. Combination Sum

Notice that we’ll have to explore many cases and there is no “smart” way to avoid that, the only smart thing we could do is to stop exploring a case as soon as we know it won’t lead to the solution and so this is a backtracking problem.

The solution is entirely same as subsets solution, only with a slight modification that we have a constraint included: the sum of the final collected combination should equal target.

40. Combination Sum II

This problem bears the same relation to the previous problem as subsets-2 had with subsets, as such it should be no surprise that the same strategy works!

Honestly, visualizing the flow of the recursive function above is kinda trippy. Once you get comfortable writing this back and forth flow, backtracking problems are really easy. Also as I was writing this article I had an idea to make it simpler, so here is a simpler version of the subsets solution.(could be extended for other solutions in this post as well)

Time for one final problem without which our discussion on backtracking would be considered incomplete, one of the classic computer science problems which gave birth to this paradigm.

51. N-Queens

We try placing queens column by column. Place a queen, go to next column and try placing another queen such that it doesn’t face a queen in the same row or diagonals ( which is checked in validateSpot method ), and keep going. If we encounter an invalid spot we backtrack and keep trying other spots in that column vertically.

The validateSpot method can be made more efficient by using arrays to store the diagonals and rows already occupied. If you are interested, do check out this solution

Finally the point I mentioned earlier, when does a backtracking problem convert to a DP one? Let’s take an example:

• Return all ways to climb stairs, jumps allowed in steps 1 -> k

Technical Interview Coding Practice - CodeFights

• Count ways to climb stairs, jumps allowed in steps 1-> k

Climb n-th stair with all jumps from 1 to n allowed (Three Different Approaches) - GeeksforGeeks

The first would require backtracking as we actually need all the ways, while the 2nd one could be done using DP optimally and is similar to how we optimize calculating Fibonacci numbers with memoization.

In the next post we’ll see solutions to these problems as well as explore other such cases (the standard rod cutting problem vs the subsets problem above). Understanding when to use DP is in itself a major issue. At this point I would like to point out the strong bond between recursion, backtracking, depth first search, and dynamic programming. (mega pattern if you will! )

The next few posts will be on solely focused on decoding DP patterns as many of you have requested the same. Stay tuned for upcoming posts!

References:

• discuss thread on backtracking
• backtracking vs dfs
• geeksforgeeks backtracking

Leetcode Pattern 3 | Backtracking was originally published in Leetcode Patterns on Medium, where people are continuing the conversation by highlighting and responding to this story.

I strongly believe in learning by doing, so let’s walk through a super simple example to understand how sliding windows work and then come back to leetcode problems. A sliding window approach generally helps us reduce the time complexity for brute force approaches.

Given an array of integers of size ‘n’.
Our aim is to calculate the maximum sum possible for ‘k’ consecutive elements in the array.

Input  : arr[] = {100, 200, 300, 400}
         k = 2
Output : 700

To solve it using brute force means to explore all possible cases. We really don’t care about efficiency at this point but do want correct results. So we could run a nested loop exploring all windows of length k in the given array and pick the max sum.

// BRUTE FORCE : iterate through all windows of size k

for(int i = 0; i < n-k+1; i++){    
    int current_sum = 0;
     
    for(int j = 0; j < k; j++){        
        current_sum = current_sum + arr[i+j];         
    }

    max_sum = max(current_sum, max_sum);    // pick maximum sum 
}

Now notice that having computed the sum of 1st window (size k), in order to get the sum of the next overlapping window we just need to leave out the leftmost item value and add the new (rightmost) item’s value, so we are essentially saving the re-computation of the sum for the non-changing part of the window.

int max_sum = 0, window_sum = 0; 

/* calculate sum of 1st window */
for (int i = 0; i < k; i++)  window_sum += arr[i]; 

/* slide window from start to end in array. */
 
for (int i = k; i < n; i++){ 
    window_sum += arr[i] - arr[i-k];    // saving re-computation
    max_sum = max(max_sum, window_sum);
}

Voila ! we used memory to save time, a very classic trade-off in algorithms and sliding windows are all about this as we’ll see. Time complexity reduced from O(n²) to O(n). Now let’s get to actual leetcode problems.

76. Minimum Window Substring

note : this first problem has been brutally analyzed as this is a tricky concept and forms the basis to solve the next 5. Master this one and try the rest on your own, that would be the best way to learn.

In the previous example the window was of a fixed size, but here we use a window of variable size determined by begin and end markers. A brute force approach would be to iterate through all possible substrings and determine the minimum window which contains all characters of T. How do you see if a substring has all characters of T ? You could use the frequency table of T which stores character to number of occurrences as follows :

# initialize frequency table
for char c in T do 
    table[c]++;
end

counter = table.size()                 # unique chars in T

for char c in string B do
    if(char c in table){ 
        table[c]--;                    # decrement count for c
        if(table[c] == 0) counter--;
    }
end

if(counter == 0){ # B has every character in T }

So we are basically assuring that every unique character in T exists in B as many times as it exists in T by maintaining a counter. It is fine if there are 4 ‘K’s in T and B has 7 ‘K’s , the table count for ‘K’ would simply go negative, but it goes to 0 at some point before that, proving string B has at least 4 'K’s in it, satisfying the need with respect to “K”, extending the logic to other chars in T if counter = 0, B has all chars in T.

Okay so coming to the sliding window part here, we keep sliding end to the right examining each new character and updating the count in table. As soon as we hit counter = 0, it means we have a valid answer so we try to trim it down removing the unessential characters from the start by sliding begin right. We constantly keep trying to validate / invalidate the string by manipulating counter and table counts.

Take a moment, understand this code. Walk through it on paper for this example : [ S : ADOBECODEBANC | T :"ABC" ] . Do not worry, the code is just heavily annotated, it is actually very concise.

Intuition : the best substring for the answer would simply be a permutation of T if such a substring exists in S, but otherwise we could have wasteful characters sitting in between the essential characters that make the substring valid as an answer. Our attempt here is to remove such chars without losing the necessary ones. After trimming down as much as possible we resume with sliding end right and repeating the whole process.

Whenever counter = 0 we have a valid candidate for our ans, but we update ans only if it is shorter than previously recorded minimum length ans.

438. Find All Anagrams in a String

Exactly the same as above with the added condition that the substring should be of length equal to p and that we have to return indexes of all such occurrences.

30. Substring with Concatenation of All Words

Here comes my proof that not all Leetcode “hard” are exactly hard, this one is simply a slight modification of the above problem which is tagged “easy”. Instead of chars in above question now we have words so it got a bit messier.

3. Longest Substring Without Repeating Characters

Here we build the frequency table out of the substring we explored so far as the aim is to find longest susbstring without any repetitions. So similar to above case we slide end and keep building the table and as soon as we hit a repetition, meaning the end char is already in table, we start sliding begin. We record the max before sliding begin for the ans.

159. Longest Substring with At Most Two Distinct Characters

567. Permutation in String

Other problems that can be solved similarly:

340. Longest Substring with At Most K Distinct Characters which is literally the same as the one with K = 2.

424. Longest Repeating Character Replacement

A good exercise at this point would be to think why the sliding window approach actually works, draw out all the cases possible for the minimum window substring problem and you’ll have a deeper intuition into this technique.

Some interesting facts :

1. It took me less time to actually solve these problems than what it took me to figure out how to explain it in writing.
2. I solved a problem tagged hard first and the corresponding easy problem later as I use an extension to hide the difficulty levels on leetcode loll.
3. I strongly believe understanding how a programmer wrote code is more important than the code itself and so I am working on codeback , a code playback tool allowing users to stop, edit and play the code line by line as well as execute the code to see output.

Stay tuned and feel free to connect with me on LI : https://www.linkedin.com/in/csgator/

Leetcode Pattern 2 | Sliding Windows for Strings was originally published in Leetcode Patterns on Medium, where people are continuing the conversation by highlighting and responding to this story.

Hola again ! Thanks for all the positive feedback. It really motivates me to keep writing daily. Many people actually asked me to write on DP patterns next as that is the most dreaded topic in interview prep. I would dedicate the next few posts to the same, building intuition on some non-trivial DP problems but for today let’s complete BFS. Some useful tips for DP to help you out till then:

1. Solve 3 DP problems each day for 2 weeks and you’ll start getting a hang of the underlying patterns. Struggle a bit, think hard, lookup the solution after an hour or two, understand the intuition deeply, repeat.
2. Think hard on the classic DP problems ( which are only a handful ), discuss / explain the intuition to a peer, draw it out on paper ( very important ) and you would then be able to solve most DP problems.
3. Read solutions to DP problems from geeksforgeeks or watch Tushar Roy’s playlist on DP, the whole point is to accustom yourself with solutions to standard problems and then apply that intuition elsewhere.

Honestly DP is overrated, it is totally doable. Just break out of the ‘DP is wicked hard’ phase and start solving problems. Over the next few days I am going to follow the above outlined techniques and share some insights every day.

BFS:

Again let’s start with a tree, cause we are so obsessed with trees! level order traversal is simply a BFS and a rather simple one at that !

102. Binary Tree Level Order Traversal

The leetcode problem on level order traversal is a bit more involved than the above mentioned simple traversal. They require you to store each level result in an array and return final result as array of arrays. Just imagine somebody told you to put a line break after printing each level, that would essentially be the same problem.

1st approach

Using the above simple code it is not possible to know when a new level starts. I originally solved this problem using 2 queues, but I found this amazing approach in discuss and I have adopted it since then. (discuss is where the true learning happens ;) ). We use a dummy node as marker to mark level ends. Try visualizing the horizontal queue push- pop action going on in BFS and figure out how you could use an extra dummy node to mark level ends, then go through below code. This approach simply blew my mind !

EDIT: As Shad Khan suggested on LI, we could eliminate the dummy node using the size of queue to keep track of level. Here is his Python code:

2nd approach

Let’s play a game of 2 queues. We keep 2 queues for even and odd levels of the tree. So starting with 0th level i.e root, initialize even queue with root. Now imagine holding the even queue in your right hand and the odd queue in your left ( just 2 boxes which allow entry from only one side and exit from the opposite side).

1. Tilt your right hand so all the contents of even queue start falling out. Whenever a node falls out of a queue push it’s children into the other queue.
2. Now tilt your left hand emptying contents of odd queue and adding kids of falling out nodes into even queue.
3. Repeat until both queues are empty.

101. Symmetric Tree problem also can be solved using 2 queue method in a slightly different way, but enough with trees already! Let’s see an actual graph (matrix) problem using BFS.

542. 01 Matrix

How does one know that we need BFS here and not DFS, which is a very true dilemma is many problems, well the first thought that crosses my mind seeing this problem is if somehow I could iterate through all 0's in matrix and start a recursive action at these cells updating distances of neighboring cells by 1, keep doing so and stop only if the cell under consideration is already closer to another 0.

For this to be successful we need all those actions to execute only 1 round at a time ( visit 4 neighbors ) and then wait for all others to execute their 1 rounds so recursion doesn’t work ( DFS failed only 1 option left BFS). See how this is so similar to the tree case when we needed the kids of the current node only after we have visited nodes at same level, it’s a BFS , bingo! The reason we need this here is if we don’t wait for other actions to execute a round how would we know if the current cell is already closer to another 0 in which case we need to stop BFS operation for that cell.

Concluding thoughts on BFS :

1. Problems in which you have to find shortest path are most likely calling for a BFS.
2. For graphs having unit edge distances, shortest paths from any point is just a BFS starting at that point, no need for Dijkstra’s algorithm.
3. Maze solving problems are mostly shortest path problems and every maze is just a fancy graph so you get the flow.

Enjoy and stay tuned !

Leetcode Pattern 1 | DFS + BFS == 25% of the problems — part 2 was originally published in Leetcode Patterns on Medium, where people are continuing the conversation by highlighting and responding to this story.

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.

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

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

Leetcode Pattern 1 | BFS + DFS == 25% of the problems — part 1 was originally published in Leetcode Patterns on Medium, where people are continuing the conversation by highlighting and responding to this story.

Here I present one such powerful pattern related to trees and present 3 different problems that can be solved using this pattern. Whenever you solve a tree problem using recursion, always follow it up writing an iterative solution and vice-versa.

Iterative solutions help us really understand what is going on while recursion is concise and beautiful, we need to be able to write both in order to become good programmers.

An iterative in-order traversal using stack to solve multiple tree problems:

Inorder Traversal of Binary Tree

Validate if Tree is a BST

For a binary tree to be a BST, the inorder has to be in sorted (ascending) order.

Kth Smallest element in BST

Inorder traversal of a BST gives us a sorted order of the items in it. So a simple inorder breaking off at the kth item would give us our answer !

Try doing this for preorder and postorder too and see how many new problems you would have unlocked ! ( Share your solutions in the comments )

I am also going to translate the solutions into Java and Python as I progress, feel free to contribute back by sharing your own patterns or translating code into your favorite language of choice.

Also feel free to connect with me on LI : https://www.linkedin.com/in/sourabh-reddy/

Leetcode Pattern 0 | Iterative traversals on Trees was originally published in Leetcode Patterns on Medium, where people are continuing the conversation by highlighting and responding to this story.