Having solved more than 1500 LeetCode problems, if there is one thing I have learned, it's this: LeetCode is less about the number of problems you have solved and more about how many patterns you know, because learning patterns allows you to solve a wide variety of problems in less time and helps you quickly identify the right approach to a problem you have never seen before.

In this video, I will walk you through 15 most important patterns I learned that made my LeetCode journey a lot less painful, and the best part is, these patterns actually came up in most of the interviews, including at companies like Amazon and Google.

For each pattern, I will explain when to use it, walk through an example, and list LeetCode problems you can practice to learn them better.

First off, we have the prefix sum pattern. This pattern is commonly used for problems where you need to query the sum of elements in a sub array.

Imagine you are given an array and you need to find the sum of all elements between indexes I and J. If you have just one query, you can simply loop through the array in linear time to find the sum.

But if you have multiple such queries, it can take up to order of n * m time complexity, where m is the number of queries and N is the length of the array.

To make such queries faster, you can create a prefix sum array where value at index I is the sum of all elements from start up to index I in the given array.

Now you can arrange some queries in O of one time using the formula: sum from I to J is equal to P of J minus P of i - 1.

This is the main idea behind the prefix sum pattern.

One thing to remember is that you don't always need a new array for prefix sums. Sometimes you can use the input array itself and avoid using extra space here are some lead code problems you can practice using this pattern.

Next one is two pointers pattern. In the two-pointer approach, we use two variables and move them towards each other or away from each other based on the problem.

For example, let's say you are given a string and you need to check whether it's a palindrome.

A string is a palindrome if it's the same when the order of characters is reversed. To solve this problem using two pointers approach, use one pointer to iterate from the beginning and the other from the end.

At each step, compare the values at both pointers.

If they don't match, the string is not a pend, return false. If they match, move the pointers closer. Keep doing this until the pointers meet.

The two pointers pattern can reduce the time complexity for many problems from order of n square to order of n, so make sure practice it well.

There are few lead code problems to get better at this pattern. Let's slide into our next pattern, sliding window. This pattern helps us find subarrays or substrings that meet a specific criteria.

Let's understand it with an example. Suppose you're given an array and you need to find the subarray of size K with the maximum sum.

Let's say K is three. A Brute Force approach is to consider all the sub arrays of size three using a nested for loop and pick the one with the maximum sum.

But since the adjacent server is overlap, there is lot of repetitive calculation leading to a time complexity of order of n * K.

Because optimize this using sliding window approach, we start by initializing a window containing the sum of first three elements, and as we it through the array, we subtract the leftmost item, add new items value to the window, and update the result.

This reduces time complexity from order of n.

O(k) to order of n since we are only using a single for loop to iterate through the array. There are some LeetCode problems to practice this approach.

Next pattern is a variant of the two pointers pattern called fast and slow pointers. This pattern helps solve problems related to linked lists and arrays which involves finding cycles.

It works by moving two pointers at different speeds. Let's understand this with a real-world example. Imagine a circular track with two runners, A and B.

Runner A moves faster than runner B. Since the track is circular, runner A will eventually pass runner B.

This is the idea behind fast and slow pointers. Using this approach, you can check if a linked list contains a cycle. Start by placing both slow and fast pointers at the head of the linked list.

Move the slow pointer one node at a time, and the fast pointer two nodes at a time.

If there is a cycle, they will eventually meet. This pattern can also find the middle node of a linked list in one pass. When the fast pointer reaches the end, the slow pointer will be at the middle of the linked list.

To get better at this pattern, you can practice these LeetCode code problems.

Next pattern on the list is linked list in-place reversal. Many linked list problems ask you to change its nodes and pointers in some way. The trick is to do it in-place without using extra space.

That's where this pattern can help. Let's look at an example where you need to reverse a linked list.

A simple approach is to copy the linked list values into an array and then update the linked list by traversing the array in reverse, but this isn't the most optimal approach since it needs extra space equal to the size of the linked list and requires multiple passes through the link list, can we do it in one pass and without extra space?

Yes, we can use three pointers: previous, current, and next. Set previous to none and current to the head of the link list.

Use a while loop to go through the list until current is none.

In each loop, set next to the next node of the current, reverse the current node's pointer to point to previous, move previous to current and current to next.

At the end of the loop, previous will point to the new head of the reversed link list. You can use this technique for any problem that asks you to rearrange the links between nodes of a link list.

Here are some LeetCode problems to practice this pattern. Next pattern is monotonic stack.

This pattern uses a stack to find the next greater or next smaller element in an array. Let's look at an example. Given an array, find the next greater element for each item.

If there isn't one, output minus one. A brute force approach is to use a nested for loop to check all the elements to the right of each item until you find a bigger one, but this can take up to order of n square time.

We can solve it in O of n time by using a stack.

Here is what the algorithm looks like: use a stack to track indices of elements for which we haven't found the next greater element yet.

Initialize the result array with minus ones for each element. Check if it's greater than the element at the top of the stack.

If it is, pop from the stack and set the result for that index to the current element.

Push the current element onto the stack. During the whole process, we keep the stack elements in the decreasing order, but for finding the next smaller element keep them in increasing order.

Here are some lead code problems to practice this pattern. Next is top K elements pattern. This pattern helps you find the K largest, smallest, or most frequent elements in a data set.

Imagine you have an array and you need to find three largest elements. A simple approach is to sort this array in descending order and take the first three elements, but sorting takes O of n log n time.

Can we avoid sorting the array? Yes, by using a min heap.

By using a min heap, we can keep track of the three largest element as we loop through this array. Since inserting and popping elements in a heap takes logarithmic time, it reduces the time complexity from O of n log n to O of n log K.

We start by putting the first three elements into a min heap.

After that, for every element, we compare it with the top heap element. If the current array element is greater, pop the top element from the heap and push the new element.

At the end, the heap will contain three largest elements. If the problem asks you to find K largest element, use a min heap, but for K smallest problems, use a max heap.

There is another algorithm called quick select that can solve top K elements problems with an average time complexity of O of n, but it's more complex.

I will cover it in a future video. If you'd like me to make detailed videos on each of these patterns and cover multiple examples, let me know in the comments and make sure to subscribe so that you don't miss my new videos.

Here are some problems to practice the top key elements pattern.

Next is the overlapping intervals pattern. This pattern is useful for problems involving intervals or ranges that may overlap. Here are few problem types where you can apply this pattern: merging intervals.

Given a collection of intervals, merge all overlapping intervals into one interval intersection, find the intersection between two sets of intervals, insert interval, add a new interval to a list of non-overlapping intervals, and problems like finding the minimum number of meeting rooms needed for overlapping meeting times.

Let's understand one of the examples where you are given a list of intervals and you need to merge all overlapping intervals.

Here is an approach to solve this problem: start by sorting the intervals by the start time. Create an empty list called 'merged' to store the merged intervals.

Iterate through the intervals and check if it overlaps with the last interval in the merged list. If it overlaps, merge the intervals by updating the end time of the last interval in merged.

If it doesn't overlap, add the current interval to the merged list.

To get better at this pattern, try solving these LeetCode problems. Next is modifies binary search pattern. Modifies binary search pattern is a variant of the standard binary search algorithm used to solve problems where the array isn't perfectly sorted, like searching in a nearly sorted array, searching in a rotated sorted array, searching in a list with unknown length, searching in array with duplicates, finding the first or last occurrence of an element, finding the square root of a number, or finding a peak element.

For example, if we are given a rotated sorted array and we need to search for an element, we can perform binary search with an additional check to determine which half of the array is sorted.

Then check if the target is within the range of the sorted half.

If it is, we search that half; otherwise, we search the other half. Here are some problems to practice this approach.

Next pattern is binary tree traversal. Binary trees are all about traversing it in a specific order. The four popular ways to traverse the binary tree are pre-order, in order, post order, and level order.

Implementing pre-order, in order, and post order TRS algorithms in code is pretty easy if you use recursion, but the iterative version is a bit more complex and requires using a stack data structure.

Level order traversal is useful when you want to explore the nodes level by level starting from the root node.

It is usually implemented using a Q data structure. Whenever you are given a tree problem, think about which traversal order fits the best.

For example, to retrieve the values of a binary surain sorted order, use in order traversal. To create a copy of the tree and the problems involving tree serialization, use pre-order traversal.

When you want to process child notes before the parent, like when deleting a tree, use post order traversal, and when you need to explore all notes at the current level before moving on to the next, use level order traversal.

Here are the problems you can solve to learn these traversal algorithms.

Next one is depth first search or DFS. It is used to explore all paths or branches in graphs or trees to solve problems like finding a path between two nodes, checking if a graph contains a cycle, finding the topological order in a directed as graph, and counting the number of connected components in a graph.

DFS can be implemented recursively or iteratively using a stack. Here is a generic approach to solve DFS related problems: choose a starting point, keep track of visited nodes to avoid cycles, perform the required operation on the current node, explore unvisited neighbors, continue until all required nodes are visited.

Here are some lead code problems you can practice to learn this pattern. Next pattern is a related one called breath first search or BFS.

BFS is a traversal technique that explore notes level by level in a tree or graph. It is very useful for problems like finding the shortest path between two nodes in an unweighted graph, printing all nodes of a tree level by level, finding all connected components in an graph, finding the shortest transformation sequence from one word to another.

To implement BFS, we can use a queue. Here is a generic approach to solve BFS problems: add the starting node to the queue, set up a visited set or array to track processed nodes, continue while the queue is not empty, DQ a node and process it, and enqueue unvisited neighbors, add processed nodes to the visited set, continue until the queue is empty.

Here are some LeetCode problems you can practice using this approach.

Next up is the Matrix traversal pattern. Most Matrix traversal problems can be seen as graph problems. In a graph, you have nodes and edges. In a matrix, which is usually a 2D array, your nodes are the cells from where you can reach to adjacent cells horizontally, vertically, or diagonally, depending on the problem.

The best part is you can use most of the graph algorithms like DFS and BFS to solve Matrix related problems like finding the shortest path in a grid.

Let's understand this pattern using the island count problem. You're given a 2D binary grid where one is land and zero is water.

You need to return the number of islands. An island is formed by connecting adjacent lands horizontally or vertically. You can either use DFS or BFS to solve this problem.

Let's do DFS for this one. Here is the general idea: iterate through each cell in the grid. If you find a land cell, we have found a new island.

Explore this island using DFS, marking all connected land cells as visited, increment our island count, continue until we have checked all cells.

Here are the LeetCode problems you can practice using this approach. Next pattern is backtracking. Backtracking is a powerful technique used to solve problems that involve exploring all potential solution paths and backtracking the paths that do not lead to a valid solution.

Some of the problems you can solve using this approach are generate all possible permutations or combinations of a given set of elements, solve puzzles like Sudoku or N Queen problem, find all possible paths from a start point to an end point in a graph or a maze, generate all valid parentheses of a given length.

Let's say you are given an array of integers and you need to generate all possible subsets.

We can use a backtracking approach to solve this problem. We start with an empty subset and index zero.

For each element, we have two choices: include it or not. After making a choice, we recurse to the next element. Once we have considered all elements being backtracked to explore other possibilities.

To get better at backtracking, you can practice these problems. And lastly, dynamic programming, also called DP. DP is a powerful technique used for solving optimization problems by breaking them down into smaller subproblems and restoring their solutions to avoid repetitive work.

It is particularly useful for problems with overlapping subproblems and optimal substructure properties, like problems where you need to maximize or minimize a certain value and counting problems where you need to count the number of ways to achieve a certain goal.

Dynamic programming is a big and challenging topic for coding interviews, but learning common patterns can make it a lot easier.

Here are some of the common DP patterns you should know about: Fibonacci numbers, 01 napsack, longest common subsequence, longest increasing subsequence, subset sum, and matrix chain multiplication.

And these are the LeetCode problems you can solve to learn these patterns. If you want to learn more about DP patterns, check out my recent blog article where I talk about 20 dynamic programming patterns and include links to LeetCode.

problems for each pattern. Links are in the description. You can also find links to other patterns and LeetCode questions that I mentioned in this video.

in the description. You can subscribe to my blog at blog.algomaster, where I post twice a week about topics related to coding, DSA, system design, and interviews.

If you want to know what else is required to master DSA apart from learning patterns, do check out this video.

LeetCode was HARD until I Learned these 15 Patterns

LeetCode was HARD until I Learned these 15 Patterns

스크립트