LeetCode was HARD until I Learned these 15 Patterns

having solved more than 1500 lead code problems if there is one thing I have learned is this lead code 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 lead code Journey lot less painful and the best part is these patterns actually

came up in most ofle interviews including at companies like Amazon and Google for each pattern I will explain when to use it walk through an example and list lead quotee problems you can practice to learn them better first of we have 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 sumar 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 twoo pointers pattern in the two-pointer approach weiz two variables and move them towards each other or away from each other based on 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 L Square to order of n so make sure practice

it well there are few lead quod problems to get better at this pattern let's slide into our next pattern sliding window this pattern helps us find subarrays or sub stings that meet a specific criteria let's understand it with an example suppose you 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 arays of size three using a nested for Loop and pick the one with the maximum sum but since the adjust 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 weit 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 * K to order of n since we are only using a single for Loop to iterate through the array there are some lead code 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 link list and arrays which involves finding Cycles it works by moving two pointers at different speeds let's understand this with a real word example imagine a circular track with two Runners A and B Runner a moves faster than runner V since the track is circular Runner a will eventually pass Runner V this is the idea behind fast and slow pointers using this approach you can check if a link list contains a cycle start by placing both slow

and fast pointers at the head of the link list move the slow pointer one node at a time and the fast pointer two notes at a time if there is a cycle they will eventually meet this pattern can also find the middle note of a link list in one pass when the fast pointer reaches the end the slow pointer will be at the middle of the link list to get better at this pattern you can practice these lead code problems next pattern on the list is link list in place reversal many link list problems ask

you to change its notes and pointers in some way the trick is to do it in 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 link list a simple approach is to copy the link list values into an array and then update the link 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 link 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 y 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 nodes pointer to point to previous move previous to current and current to next at the end of the loop previous F point to the new head of the reverse link list you can use this technique for any problem that ask you

to rearrange the links between nodes of a link place here are some lead quod 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 br 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 1es 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 quote 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 and time can we avoid sorting the array yes by using a mean Hep by

using a mean Hep 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 to O of n log K we start by putting the first three elements into a Minh after that for every element We compare it with the top heave element if the current area 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 ask you to find K largest element use a Minh but for K smallest problems use a Max hip there is another algorithm called quick select that can solve top K elements problems with an average time complexity of O ofn 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 set 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 MZ to store the M intervals it read through the intervals and check if it overlaps with the last interval in the MZ list if it overlaps mge the intervals by updating the end time of the last interval in M if it doesn't overlap at the current interval to the m list to get better at this pattern try solving these lead code 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 salted like searching in a nearly salted array searching in a rotated salted 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 salted 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 salted within check if the target is within the range of the sorted half if it is we sech 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 stag 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 Nevers continue until all required nodes are visited here are some lead quod 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 sest path between two nodes in an unweighted graph printing

all notes of a tree level by level finding all connected components in an graph finding the sorted 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 note to the queue set up a visited set or array to track process noes continue while the Que is not empty DQ a node and process it andq unvisited numers add process nodes to the visited set continue until the queue is empty here are some lead code 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 notes and edges in a matrix which is usually a 2d array your notes are the cells from where you can reach to adjacent cells horizontally vertically or dially 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 itate 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 vised increment our Island count continue until we have checked all cells here are the lead quid 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 Sudoko or en Queen problem find all possible paths from a start point to an end point in a graph or a mage generate all valid parenthesis 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 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 sub problems and restoring their Solutions to

avoid repetitive work it is particularly useful for problems with overlapping sub problems and optimal subst structure 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 lot easier here are some of the common DP patterns you should know about t noi numbers Z1 napsack longest common subsequence longest increasing subsequence subet sum and Matrix chain multiplication and these are the

lead quote 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 lead code problems for each pattern links are in the description you can also find links to other patterns and Lead code questions that I mentioned in this video in the description you can subscribe my blog at blog. algom master. 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 see you there