8 patterns to solve 80% Leetcode problems（原声文稿）

I have solved 554 lead code problems but you don't have to.

It took me 500 plus problems to realize that there is an easier way to become.

better at coding problems and that is, just focus on the patterns that repeat. over and over again.

In this video, I'll show you 8 such patterns. Let's start with sliding window.

pattern. The sliding window pattern is used when you need to process a series of. data elements like a list or string.

In the sliding window pattern, you find specific things in a list by looking at a.

smaller part of the list at a time. The part of the list that you are looking at. is called your window.

This window then slides one step at a time until the entire list is scanned. When do. we use the sliding window pattern?

If a problem asks you to find a subset of elements that satisfies a given condition.

think about sliding window pattern. Your input would be a linear data structure. like an array string or a link list.

And you would have to find the longest or shortest substring or subarray that.

satisfies a particular condition. For example, look at this longest substring. with k unique characters problem.

Your input is a string and you need to find the longest substring that satisfies.

unique characters condition. It's a classic sliding window problem. Next we. have the subset pattern.

The subset pattern is used when you need to find all the possible combinations of.

elements from a given set. Repetitions may or may not be allowed depending on the. problem.

In the subset pattern, we need to explore all the possible arrangements of elements.

from the given set. Take for example this permutations problem from lead code.

To solve this problem, you can iteratively build all the subsets level by level. Start with an empty set.

At each level, consider all the ways to add the next element to the existing.

subset and create a new one. This approach is very similar to breadth -first search. or BFS.

Next we have the modified binary search pattern. The core idea of binary search is. to divide the search space in half again and again.

In the modified binary search pattern, the core idea remains the same, but we need to.

adjust the logic a little bit to solve the given problem. Let's take the example of. search in rotated sorted array problem.

Here the array is sorted but rotated at an unknown pivot point. You'll need to modify.

the standard binary search to figure out which half of the array to search in.

One thing that helped me a lot to solve modified binary search problems is. understanding the core binary search algorithm really well.

For the core binary search algorithm, you need to be able to visualize where left.

and right pointer end up if the array contains duplicates or if the array does. not contain the target.

Let me give you a good way to improve your visualization of binary search. BISEC.

module in Python contains two functions, BISEC left and BISEC right.

Implement these two functions in the language of your choice and your. understanding of binary search will improve a lot.

Before we talk about the next pattern, I want to make it very clear that you need.

to have a good understanding of data structures and algorithms to solve the. problems that we are discussing today.

If you want to know how to master DSA and how much DSA you need to learn before you.

can solve these problems, you can join my free 5 -day email crash course on. interviewmaster .io.

So, moving on, the next pattern we have is TopK Elements pattern. The TopK Elements.

pattern is used to select k elements from a larger dataset given a particular. condition.

Think about this pattern whenever the problem asks you to find top ranking.

elements from a dataset. The input would usually be a linear data structure like an. array or a list.

For example, given an array of numbers, you need to find the kth largest number. efficiently.

To solve this problem, you need to keep track of the k most important numbers that. you have seen so far.

Since you care about the kth largest element, the largest k elements you have.

seen so far are most important. So you would store them using a data structure. called heap.

We'll come back to why we use a heap in a moment. Anyway, the smallest number on the. heap would be the kth largest number we have seen so far.

If the new number is larger than the kth largest number so far, you will remove the. kth largest number so far and add the new number to the heap.

We use a heap here because it makes finding and removing the smallest number.

very Next, we have depth first search of a binary tree or binary tree DFS pattern.

Binary tree DFS helps you visit every node on the tree, focusing on one branch at a.

time. Generally, you would use recursion to do this. Here is how the flow looks. like.

You will start at the root node. After that, you apply DFS recursively to the. left node.

This process continues, going deeper and deeper into the left subtree until it.

reaches a node with no children. Once the DFS reaches a dead end on the left side. it backtracks.

Now, it focuses on the right node if it exists and applies DFS recursively again.

By doing this, you explore the entire right subtree.

For example, in this very popular problem called maximum depth of binary tree, you.

need to find the length of the longest path from the root node to a leaf node.

For this, you simply keep track of the depth as you do a binary tree DFS. And.

whenever you reach a dead end, you update the maximum depth if the current depth is. more than the maximum depth.

It's that simple. Next pattern we have on the list is topological sort. The.

topological sort is used to arrange elements in a specific order when they. have dependencies on each other.

It's particularly useful for directed acyclic graphs. Whenever the nodes of a.

graph have one way connection between them and there is no cycle, it's called a. directed acyclic graph.

Think of topological sort whenever you have a prerequisite chain. Let me explain.

what I mean by this. Imagine that you are building a complex program.

Some parts of the code might rely on some other modules being written and tested. and these modules can in turn depend on some other modules.

Topological sort can help you figure out the order in which you should write your. modules.

By analyzing the dependencies between different modules, it creates a sequence.

where each module is processed only after all its prerequisites have been completed.

Try this course schedule problem on lead code where instead of modules, we have. courses as prerequisites for other courses.

Next we have breadth -first search of binary tree or binary tree BFS pattern. So. we already covered binary tree DFS.

In binary DFS, we go deep into a branch and explore it completely. Then we move on.

to the other branches. In binary BFS, we take a different approach.

BFS explores all the nodes at the same level in different branches first. To do.

this, we need to use queue data structure. In the beginning, the queue would only. contain the root node.

After that, you are going to repeat the process I am going to show you again and.

again. You will remove a node from the front of the queue and do any operation. that you might want to do with it.

Then you add both its children on the queue. You keep doing this until the queue.

is empty. By doing this, the elements at the same level of the tree will always. remain next to each other on the queue.

This way, you can process them one after the other. A problem that is a direct.

application of this pattern is called level order traversal of a binary tree.

It's exactly the same what I just explained. Lastly, we have the two pointer.

pattern. The two pointer pattern is used to solve problems when you need to iterate. through a sorted array.

Taking a hint from the name itself, we'll be using two pointers in this pattern. Each pointer will keep track of an index in the array.

By moving these pointers smartly, we can often solve the problem in a single pass.

making the algorithm more efficient. Let's take the example of the two sum problem.

You are given a sorted array and you need to return the index of two numbers that.

add up to a target sum. To solve this problem, you can use two pointers.

The first pointer starts at the beginning and the second one starts at the end of. the array.

Depending on whether the sum of the numbers at the pointers is less than or.

greater than the target sum, you will either move the left pointer to the right. or the right pointer to the left.

This works because the input array is sorted. Another variation of the same.

problem is when you need to find triplets that add up to zero in a sorted array.

So far, we only covered some popular lead code patterns, but your job is not done.

yet. You need to find some problems that fall in each of these patterns and solve. them one by one.

But before you do that, learn how to master data structures and algorithms by.

signing up for my free email crash course on interviewmaster .io. My name is Sahil and I'll see you in the next one.