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