Scribd
Importer
2 vues11 pages

DSA Patterns

Le 'DSA Patterns Handbook' présente des motifs éprouvés pour résoudre des problèmes d'algorithmes et de structures de données (DSA), facilitant l'identification et l'application de solutions efficaces. Il couvre divers motifs tels que les pointeurs rapides lents, la recherche binaire, et la fenêtre glissante, tout en fournissant des conseils sur la complexité temporelle et spatiale. L'ouvrage insiste sur l'importance de reconnaître les motifs plutôt que de mémoriser des solutions, encourageant une pratique répétée pour maîtriser ces concepts.

Transféré par

narendra
Copyright
© All Rights Reserved
Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.
Formats disponibles
Téléchargez aux formats PDF ou lisez en ligne sur Scribd
2 vues11 pages

DSA Patterns

Le 'DSA Patterns Handbook' présente des motifs éprouvés pour résoudre des problèmes d'algorithmes et de structures de données (DSA), facilitant l'identification et l'application de solutions efficaces. Il couvre divers motifs tels que les pointeurs rapides lents, la recherche binaire, et la fenêtre glissante, tout en fournissant des conseils sur la complexité temporelle et spatiale. L'ouvrage insiste sur l'importance de reconnaître les motifs plutôt que de mémoriser des solutions, encourageant une pratique répétée pour maîtriser ces concepts.

Transféré par

narendra
Copyright
© All Rights Reserved
Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.
Formats disponibles
Téléchargez aux formats PDF ou lisez en ligne sur Scribd
DSA PATTERNS HANDBOOK ty + The Roadmap to Solving Any DSA Problem —= xx = Presented by @codewithZ = 1. What are DSA Patterns? 17 + DSA Patterns are tried and tested ways to a = solve a group of similar problems. AIG learn a few patterns and apply them again and again Real world. problems are repeitive in nabure. Palterns test your problem solving skills, Helps companies filter strong problem solvers. © Once you know patterns, you can solve + Instead of learning 1000s of solutions, 2. Why companies ask pattern-based questions? not your memory. new problems faster wo - How to Identify a Pattern? Read the problem carefully. dentify key words, constraints & dato. structure invelved Think: What am I trying to oplinize or find? Match with the pattern list (on this page). Apply the right approach + template 5. Most Important DSA Patterns @ Too Pointers © Backtracking Arrays, Strings > ALL Posies @ Sliding Window @ Dynamic Programing > Subarrays, Subtrings ~ Oplinization Problems @ Fast & Slow Pointers @® Greedy Linked. List, Cycle = Optimal, Choices @ Binary Search @ teap 1 Pierity Qusus > Search, Optimization ++ Tap K, Scheduling © Drs & BFS @ Intervals > Trees, Graphs > Overlap, Merge, Insert 4. Pattern Selection Flowchart Read the Problem Ts it asking for a search? Yes Does it valve Subarray / Substring Cycle or requires eat & dow ronment? Check other patterns DP, DFS/BFS, Bocktrockng Gree 6. Time & Space Complexity Cheat Sheet Complexity | Time Complexity Use When (1) Constant =! a ae, O(log n) Lagprthmic | Binary Search, Balanced BST O(n) oo sae Gos SS es oa SEO O(n?) Quadratic Nested loops 0(2") Expmential | Recursion, Backbracking O(n!) Factorial Permutation ofr. elements 2 | fy. Patterns re the balding Hocks of problem sshing Don't memorize solutions, recognize patterns Practice. Repeat. Master. ©) e i i eden e Be eaux @eoleith! = DSA PATTERNS HANDBOOK< @22® W Presented by @codewithZ + Solve Smarter, Not Harder! @ TWO POINTERS PATTERN | te te pate ts teas dla sate | ———————— _| from different directions to solve problems | t optimally in O(n) time. | A. When te Use? 2 owl Werks © You are working on a sorted array / list © The problem asks for a pair with a target sum Ce ae © You need lo remove duplicates in-place. t t © You need. to compare elements from both ends. : J + You need to maximize / minimize something Move pointers based on the condition. (if Panter} oti they mest Great Rte | 3. Generic Template (C++) eens A — lee ponenaanaa- Jariants ~----—~-----~ Lata aA te of ile ( a yt ‘ 1 # Some Direction Two Pointers (i++, j++) ! ie 7, f - cL | © Opposite Direction Two Pointers (i++, j--) ! your logic. hare 1 : ' ate hae ie Fast & Slow (Special case for linked. Uist) ' itty 1 rove (eft. polrter | TRE Ne a } else { i--~ Complexity jer A] move right pointer ait } i} © Space Complexity: O(4) { | PARENT es Contlenity: O(n) a) | ' | 4. Common Problems 1, Two Sum II ~ Input Array Is Sorted || 2. Remove Duplicates from Sorted Army || 3. Container With Most Water Problem: Find two numbers such that || Problem: Remove duplicates in-place || Problem: Given height array, find two fay odd up to large. From sorted array Uae’ thatl foun’ cotainer sh [etores Example: Example: the mast water arr = (2,4, 7, 11, 15], target = 9 || orr = [1,4,2,2,2,3,3,4] Example. Output: (1,2) + 2+7=9 Output: 4, arr = [1,2,3,4] height = [1,8,6,2,5,4,8,3,7] Approach: Appreoch Outpat: 49 Use tue pointers t= 0, j= nt || Use i te iterate, j to keep track of || APereech Fe i fe, Unite parks 10, i=in of Tf sum < target, move i++ ore i i a Hf arti] |= arrf], increment j and |] Area = min (hi), Lj) + Cj - 4) avee ra gett copy orr{i] to orf] at pointer pointing to smaller 2, returs pair or Complexity: O(n) time, O(1) space F Complexity: O(n) time, O(1) space Complexity: O(n) time, O(1) space 1jt{2]2]2)3[3]4 2]4 [7] [ss ? ; t t Afters [Ul 2 [SPR LS t a * * t i Two Pointers is all about smart movement. Don’t check every clement, skip the unnecessary ones! eet” = DSA PATTERNS HANDBOOK < W Presented by @codewithZ * Solve Smarter, Not Harder! wk @ SLIDING WINDOW PATTERN 41. When to Use ? You ore dealing with an array / string + You need to find a subarray / substring that satisfies given condition Brute foree is too slow (O(n2)) We can expand the window and shrink it smartly. 3. Generic Template (C++) Fe (A) Maxinam Sum Subarray of Size K int left = 0, right H1 Initialize window while (right < a) 1A. Expand the window add arr{right] to window right ++ 112. Shrink the window if condition breaks while uindou size / condition nat satisfied) { remove orr[ left] from window leftes; = 0; } H-3. Update ansier Update answer based on current window } return answers 6. Examples (B) Lingeat Substring, Without | Used to solve problems on subarrays / | substrings where we need a contiguous \ (A) Fixed Window Size + Window size is fixed + Move windon by 4. atop. (B) Variable Window Size Window size is not fixed. Expand. until condition. breaks. Shrink to make. it valid again. Example: Longest. Substring Without Repeating Characters + Example: Maximum Sum Subarray of size K k=3 4. Common Problems Maximum Sum Subarray of Size K (Fixed) i Longest Substring Without Repeating Characters (Variable) | Minimum Window Substring (Variable) t i 1 | ' Longest Ones After Replacing K Zeros (Variable) Common. Mistakes Forgetting 42 shrink the window Wrong conditions for expanding / shrinking Nok updating onsuer at the right time Off-by-ene errors. in window size Using extra data structures unnecessarily xx x xox [a (© Minimum Window Substring orr + [2,1,5,,3,2], ke 3 Repeating Characters = “ADOBECODEBANC™, t = “ABC” Fixed Window & = “abeabcbb” Variable Window Variable Window Answer: “BANC’ ey High Level Idea: we aa! ta especie) ta tetaasvall eral of a 2 | | © When slid, vik from left lo minimize 2 ¢ 3 || Kaap track of rinimum sind -~H[eitb 7 Sees “3 4 6 3 Index 8 9 10 11 12 Clee oF) E Gy 2 ren ed ees > DSA PATTERNS HANDBOOK < Wk Presented by @codewithZ © Solve Smarter, Not Harder! wr @® FAST & SLOW POINTERS PATTERN Also known as Floyd's Tortoise | and Hare Algorithm. Best for! cycle detection and finding middle. | 1. When to Use ? 2. How it Works? You are working with Linked List or Sequence © You need to detect a cycle t]-[2]-3]-J-[s]-[-]-- + You need to find the middle element. a af, + You need to selve problems like Happy Number (A step) (2 steps) © Slow pointer moves 1 step at a time © Fast pointer moves 2 steps at a time + Hf there is a cycle, fast will eventually mect slow. 3. Generic Template (C++) 4. Cycle Detect (Floyd's Algorithm) ©-@-@-O-O, K_\%o Tf there is a eyele, alow ond fast will meat cat some point inside the cycle struct ListNode { int val; ListNode* next; ‘ 1 Funchion. template using Fast & Slow Pointers void fastSlowPattern ListNode* head) { if Cthead I thead->next) return; M7 base case ListNode* slow = head; — // moves 1 step ListNode* fast = head; — // moves 2 steps while (fast 8& fast-onext) { slow = slow->nexts MA step fast = fast->next-onedt; —// 2 steps 5. Find Middle of Linked List f= [4 ]—[5 ]—-[¢]—-[7 1 Bad your condition hare f Glow == fost) ( H1 Meet point found. leycle datected) break: When fast reaches the end, slow will be a the middle + For odd length -> exact middle 1 For even length -> second middle (by this approach) 6. Common Problems Solved Using Fast & Slow Pointers (1) Dela Cle" Lad LS }((2) Find Middle of Lined Lit] (3) Fad Stating Node of Cycle (C4) Happy Number Raburn true f cya sists, || Relrn mide node Ratu node ware eye begins. || Ratu trun if umber is happy Approach Approach Steps aes Tf slow == fast ob any point When fast reaches end, 1. Detect cycle (slow == fast) || Use fast & slow on the sequence inside lep => eyda ents, || slow te ab middle 2. Move slow to head || of sam of squares of digs 3. Mowe both sow & fast L tep || If cycle reaches 4 > Te: O(n) Te: O(n) lim ssseytes athe ea [cae errs sc: 001) G)— sc: 0(4) ; | Te: OCtag a) © | 4. Tag tok dof te | TS OC Te: O(n) ‘ || } Q ||O-@-@-©-® Ween o | Le’ ' eas. G-f-B-BEO Middle Hope) slow fast tm) ot 2 steps FY Tip: Fast moves twice as fast as Slow If there is a loop, they will definitely meet. ©) @codevit\= > DSA PATTERNS HANDBOOK < Ye Presented by @codewithZ * Solve Smarter, Not Harder! gir Binary Search is used on sorted data structures to reduce time complexity to O(log n). & BINARY SEARCH PATTERN 4. When to Use ? The dala is sorte. + We need to search on element = We need to find the first/last occurrence. © We need to find a position (lower/upper bound) © We need to minimize /maximize something using “Binary Search on Answer” 3. Generic Template (C++) 4. Variations lat binarySearch(vector& are, int target) { Int lou = 0, high = areieiza() = @ Roe gg he (lau <0 high) £ @® Lower Bound (First position >= target) ink mid = low + (high - low) / 2; // bo evcid overflow @® Upper Bound (First position > target) of CoreLmid] == targel eet + ra @® Binary Search on Answer (Search in Answer Space) ele if (arr[mid] < target) © Search in Rotated Sorted Array low = mid + 45H coor in right half alse © Find Peak / Inflection Point high = mid - 4; Wf search in left half >. } i Complaxit bd \ ae “4; Hf nok found. | + Tine Conpnty = O(log 0) © \ 1 * Space Complexity : O(1) (Terative) ' ah Ee a oe ot ae 5. Important Variants with Exo iw OSS @® Lower Bound (>> target) (® Upper Bound (> target) 7 Find 7 in [4, 3,5, 7, 8, 44, 13] | Fd fat inden >= 6 iw [1,2,4,6,6,8,10)| | Rind fink index > 6 in [1,2,4,6,6,8, 10] Slaps drawer > index 3 Poser > index 5 Toe igh mid anti) Aig |e gh st) tin | th ld or] Ain 0 6 3 6 hema |] 0 § 3 6 lame ee ee) ok A El og og 6 Be (Found ab index 3) 202 2 4 twemdet]| & 4 6 lowemidot 3B 2 = = atep owes) | 5 = tap (le 5) 1[3]5 [2 [“[4] | — so SE | Ge ea Te Jo) || 2 Te Te a) Cm Rona PeCaT TG, ON al é {GJ finer search fa Avasen @® Search in Rotated Sorted Array | (@ Find Peak Element Search space: [max(board), sum(board)] || Steps: Compare mid with target and antfy which half te corked Than dade hare 6 serch | Pook = elament greatar than ‘ts neighbors Steps: Compare mid. with mid. If errLmid] < arrlmid 1] + go right Ele = go loft Prclon: Minimize the max Load in K paitars.|| Search O in [4, 5,6, 7,0, 1, 2] | Find peak tw [1, 3, 20, 4, 4] CCheck(rid) + Can we paint with max load = mid using K painters? lew high +[s[s[#]o[t @extesith” >DSA PATTERNS HANDBOOK = te Presented by @codewithZ * Solve Smarter, Not Harder! @ Fs & BFS PATTERN DFS ond BFS are the foundation of solving wms_on Trees ond Graphs “G@J- 1. When to Use ? 2. DFS vs BFS + You ore given a Tree or a Graph. Feature DFS (Depth First Search) | BFS (Breadth First Search) Dad el Strategy | Go Dea thn bactreck | Go Level by Lew FEN RS SO Penge |[ Bae Sette [Sec / Resi Cin a Ge oie ee ae ate) ‘Mors (Far wile graphs) © You need, level by level traversal (use BFS). Use Cases | Path, Cyel, Topological Sort, | Shortast Path (Unusightad), Ret eh ee AO) Connected. Component Level Order Traversal Time Conglenity OV +E) ow + £) Spece Company OCH) ~ (Vv) ov) 3._DFS (Depth First Search) 44, BFS (Breadth First Search) (A) Recursive Template (C++) (A) Template using Queue ‘wid, dfa int eda) vector eink? adj(])) vector “int vis) ( void bfs(ink start, vector adjf]) { vtafrede] = 45 1 mack lad ont (free leinhoe bem velar cink> vis adj see), 05 for (int th = adjfneda]) ( = erat tna {Vee i fslstart] = 15 aay cays fi capeee ee wile a ep) ) | sis = visited array | int node = [Link](); 4-pop()s d L 3 (pecs = a SW ee © cma for (ink > odie) { (B) erative Template using Stock f (vatay ¢ (Puke vid dfelterative(ink start, vector o@j(]) € isl) = 45 ee stackint> st gepusk(it) ete vector vis([Link](), 0) eee Hipuk(otert): | befor ng while 1st empty()) { | te the next ink node = tops shes yaya 1 F (Watrodel) continua; ! ' e x weelrmde) = 5 77 prem da | J2 DES, oe go | for Gok > adfantel) jw deep ae | if (lis [64]) ot. pao (ot); —o i | backtrack. ) Tree Traversals eet BES (Oe a 6. Level Order (BFS on Tree) (C) Postrdr (Loft = Right Rot) / QD Lenk 0: @ ©® tek 2 23 OG ® © (|G ® & uizisse (Gut 24536) a 7. Graph Representation 2 inceney Mac (was 2631)|| (Omns23456) ‘jean List 2 = 7 \ Q Fe) PFET] | © toner comet pnts @ Fa FL Mer fn | Ye [222 |FIEEEE|] | Onmtew ema Ocecem satus |[afipofolr ls] | | © Oka Guph s Btn —— @ Cove Sine Cpa Sw) | GY) | t723 afola|sfolo | @ open St (0) @ Word Ladder (BFS) ! 543 sfololtfolo {© Set Rh tid Cw 8) tan Diary Cred Se) Ih [We DFS gees deep. BFS goes wide i Think. Explore. Master both, conquer all! © hy | Sol @cotesith® = DSA PATTERNS HANDBOOK < te Presented by @codewithZ * Solve Smarter, Not Harder! yy @ BACKTRACKING PATTERN f eae aye Ee solutions by building candidates step by step and removing (backtracking) when Aa | we hit a dead. end. z 1. When to Use ? 2. How it Works? You ore asked to find all possible solutions You can make choices and backtrack, Yes + The problem has constraints Typical Problems: Permutations, Combinations, N-Queens, Sudoku Solver, Word Search nse al Try all options > keep valid ones > undo > try next 3. Generic Template (C++) 4. Example: Print All Subsets (Power Set) void baektrack(Parameters) { Given: nums = [1, 2, 31 W Base Case: check and add answer AU Subsets = [ [1], [1], (2), (31, (4,21, (4,33(2,31, [1,2,3]] if (isSolation()) { saveSolution(); oe 3 11 Try, all choices for Coach choice) { if (sValid(choice)) { mmakeChoice(choice); backtrack(updatedParameters); // explore undoChoice(cheice);, WT backtrack aN » ie w/\. y (2) (2) (2) [es] ft) fos} [2] [e233] ® Permutations of a String / Array Make a choice — explore — undo the choice Keep track of constraints to prune eorly Backtracking tree can be huge > prune as much os possible. Use proper data structures (set, mop, visited array) to avoid duplicates ® N-Queens Problem ® Sudoku Solver H | | | © Combinations (Choose k items) I \ | © Word Search (Backtracking on Grid) 7. Classic Example: N-Queens Problem (at Board) Fume AWqussalon! Fetflaarl¥ag a) oe Row 1 Row 2 Row 3 (Solution) Another Solution. ro two quesns attack each other. [@ Q] Q aly] q Bocktrocking Iden: q + Flac quten ru by ro EI | es [RPT [|| a © For each row, try all columns. © Tf safe, gp be next ro. + If not posable, backtrack, race Qin (0.0) Try (4,2) Try (2.1) Place (3,3) ¥ Another valid way 7 Try, Explore, Undo, Repeat Until Success! - Be patient, The solution is on the other cle of recursion, @ % E @colest®? DSA PATTERNS HANDBOOK < (2! W Presented by @codewithZ * Solve Smarter, Not Harder! we (Ue ae nee eee MERGE INTERVALS PATTERN cna ue nasd to marge then ilo | ses aie ee e e | I | nonceverlapping intervals 5 whe @ 1. When to Use ? 2._How it Works? + You are gin a list of intarvls wort tires [2] [tad] [os] [oem + Some intervals overlap. | © You wed) to merge, oll overlapping) tatervals, Sat by tot [ [1,3] (2,4 [s, 10) (15, 18] Return the list of non-overlapping intervals | Example: ¢ Owope [Ce] [fe 201 8, 18 Inyo + dens (C1 3).(2.6).(8201 05,18)) |" ea Ree tea] pt [Link]. 3. Generic Template (C++) 4. Dry Run vectercvectercint>> Intervals (vector>% intervals) { Sees Tput + ((1,3, (2,6), (8,209, (15,280) uf Getaret eee pe nly Sip Crt teat [cop thy | ain [at] sertlintereals begin), interalscad0))5 11 srt by start Tat | cart = (1.3) ] - - 0 vedorcin> curek = tte}; | for Gob b= 1h 6 « intra 1 | amet = [1.31] (26) | Yee | Merge || f Gotervale[sJlO] < current | Fe 2 | current = [1,6] (8, 10) No aed (4, 61), current{1] + max(current( 4], intervals{.J[2]); Leis | yates ret perth (an A 3 | erat + (2,10)| (15,18) | Ho xe con man} 3 | | } H wt!) | ea | ewe 5,0) = | ras sae | 41-0 | ‘result puch_back(current); (1s, 18)) ration ) 5. Variations af 6 Common Problems yy 7. Key Tips. ® Insert Interel fo ee cota \ Aluaye sort by stark time, @ Mecting Rooms (Check if any overlap) @ Insert Interval { Overlap condition: currentstark DSA PATTERNS HANDBOOK = W Presented by @codewithZ * Solve Smarter, Not Harder! @ DYNAMIC PROGRAMMING DP is cbout solving complex problems by breaking them into simpler Optimize Overlapping Problems the resulis to avoid recemputation i ‘overlapping subproblems and storing 1. MEMOIZATION (Top-Down) | 2. TABULATION (Bottom-Up) 3. STATE. TRANSITION les von 6 cng (om), | | = Ue kin + Defeat Jaret 5 bald laine fom onl 1 pe dae Paaftaeee oes 1 Wi nanan Stet ae oe ferent |p enuf energie |p cNge ea mec pow Coa woe ES eyes a aS f | dpletate) = max/min (transition fron @ — © fo \ all pests proous states) Transition : stale > next. state(s) Anawer + dpL goal tate] Time + O(N) with meme Space : O(N) + O(N) stack 4. CLASSIC DP PROBLEMS {@ FIBonacct NUMBER 0/4 KNAPSACK Find. nth Fibonacci number Given weights wl], woluae voll] and capeity W Recurrence : Fin) = Fla-1) + Fn-2) Macimise volue without ewceding capacity en iGaoeGthet | | State: dple]Cu] = mac salue using first ¢ tame and capacity Teblation ara , | ose aoe [pdb] © max vlfi-t] + dpli-10bw - Cit.) - | | apli-t1Ed ) | r©fe[+}2z12 [3/8 | Tne: O(N) Space = O(N) or O(1) { apCtel = dpti-a04 pans) i ) ime 0001 W) Space + O(N «WD coal |© LONGEST COMMON SUBSEQUENCE (LCS) | ® COIN CHANGE (Minimum Coins) Find Uangih of Langest subtuancs commen in tne cringe. | | Gian coinel] and amount A Lat st (ens mi), 42 (len=n) Find, ninimare exing to muha amsuh A State = apllly] = UES lngth of «2 [0.4-1] and <2(0.j-1] | | State = dpe] = minimum coins to make amourk x | oie | ronson (Egeo aoa > sag xe lhPaentto ) Sr ete keine [op = te ni detec) fr at an | Mig o§atacets ae i peak [Lf not possible => dpe] = INF ] [Tine | Ol e n) Space = Olm #2) Time = O(A +N) Space - O(A) 5. DP THINKING PROCESS == ~ = 4. UNDERSTAND 2. DEFINE STATE 3. FIND CHOICES 4, WRITE TRANSITION | | 5, BASE CASE |e What is asked? oF 1 Wha sll dp vepesant? rom curent sale, + How do T mom from When ts the anawer + Wha ore inputs UR Pee lhs Bhas ease meee Gao already noun? i Sindee Pea) Chee eat con Td ob the | | state)? «Dafa bate lal © Cin beak te (aaa Gupte?) stop? OE IS neato eee falar pets? | | + Enarla: indy um, | * Expl: take / sip, pve | opal pods aes) | pick nk pick, ee L J J — . 6. COMPUTE 7. GET ANSWER: 8. OPTIMIZE Golden Rules Nae eee eeeinl Pal ioetagea pelle (Pa) Recta || ae aaa! (Top-Down) or Tabulation ‘+ From which stale do we ica etomea tiny We dover ea rena + tk fo pe Bite] | de Optinal Substrucare \ t atom Up) fake he re? sInyimat” {OB o @ We Shore & Rouse Resulls | Wy Break it down. Solve it snark, Build up. That's withZ. @eodeni = DSA PATTERNS HANDBOOK = * es by @codewithZ * Solve Smarter, Not Harder! @ Greepy + HEAP Optimal Choices 4. GREEDY @® Activiy SELECTION Sel ma eciin Uhl dent eelap Detar (start, ond) 4) 2) 9 ©) 6. @9» —— — =< | Vt ii re Lan Greedy: Aluaye pick the activity that fishes cares Ole log n) Space 064) Tima JUMP GAME (11) Gh at), fd min jig Qo rach la inde Seeds) A eae le ee im lc rete Example: (2, 3, 4, 4, 4] DIS 2 Ea aes fsa] fen] * Aes: 2 jumps (0 = 1+ 4) Space: O(4) Time: O(n) (© cas starion Cleat of gps slalos. Pal lark inde to conlele ln Gready: If total gee < total cout > no sollion | agave art aoa ai hn tan <0 Gas: (4, 2, 3, 4 5) Cost: (3, 4, 5, 1, 2) ® [ines ot) spat: oc D—B Greedy makes the locally optimal choice at each step with the hope of finding global optimum. Heaps help us efficiently pick min / max elements 2. HEAP (Priority Ques @ ToP K FREQUENT ELEMENTS PaHaap (see K) Ratu K slanants with highest rope Use Min-Heap of sae K ) @ Time O(n ag k) Space: OK) ® MERGE K soRTED LisTs Marge K srt bad Ut Use MacHeap to anys pi smaleh sade Time: O(N log k) Space: Ok) L123 ease © K Closest POINTS To ORIGIN Find K pine aoa lo (0,0) Use MaxcHaap of size K (by distance) Tama: O(n log k) Space: O¢K) When to Use Gready? fr OA © If problem asks for masimum / minimum, ¢ Need to repeatedly get min or max slament, & Hf local ephinal leads to glbal optinal © Top K 7 kth largest / amelie, 1] If homing serial, anal, Largest haps Marge K sorted Ute © pron fas Tro besa” property + Ralntina Uatk echduling / rennin probleme 3. PRIORITY QUEUE TEMPLATE (C++) ‘4 MIN HEAP vs MAX HEAP 5. PRO TIP (aes =a as io Hop a ) wag cena is “ip Eonect_| Selle ine Oe et ea iis wie ais eure tia Parent = Child | Parent <= Child | Rarenk >= Child cag a gate mt, | PRBS | Ba ea yee ees, acne mag a ean NET, vk” ace | Cry | MGR ee protectant sy Dytstra, OST, | Top K Largedt, Heap operations (push/pop/'tap) ie tse Cote | Mog Xs, | Tone Sek lake Oleg 0) OE ate to Tip K Smale | Mein Fodog non aap heap sss anal (i K) antee pr0 . for butler fiery ‘ak ar = nin. sine 0 dat Eon Frateap ene) (24. Greedy chooses now Heap helps you choose smartly ond fast! : @codewithZ t) r codewithz ons = DSA PATTERNS HANDBOOK % Presented by @codewithZ * Solve Smarter, Not Harder! w& @ Pattern Recognition Guide If you see, all Sorted. Array Pair Sum Largt/Sll ed | Cyele Troe 1 Conbiaions Optimization Top K Intervals > 1l€ea>e0 De Dependencies — PATTERN SELECTION FLOWCHART ( Udectana the Prt, INTERVIEW CHEAT SHEET 25 MOST ASKED LEETCODE PROBLEMS (Grouped by Pattern) 41, Binary Search 2, Two Pointers 4. Binary Search 4, Tue Sum Il = Input ray Sere 2. Search in Roald Sorted Array || 5. 35am 3 Containar Vth Most Wor Fd Mia in Rll Sead Aray|| 6, 3. Sliding Wd 4 Fast & Slow (Cys) 7 At sng dng | 10. abl es <=} | 7 oe 40 tesed at ogee Sling Window Abate by ot fn st [as eo ea 5 pao eee fat iw | ob 5 Tree (OFS / BFS) 6 Badiredng DFS / BFS 13. Maximum Depth of Binary Tre | 16, Subsets === ===} | te sone re 3 Crain Sm Backracking 45. tary Te Len Our Pe || 18, tte tin Dypomi Progranming | [7. Dante Prgranning & Hap (Top K) ap (Perity una) | | 3 Sno Se 22. Kah Lega Baer an Any Bs ah | |e ace samen || eal eh ately aateal eas 21 Con Gene 2A, Mage Sead Lite Graph (Tepdagizal Sat) | [9 Taare / Groph 1) 25. Marge Intro (Intervals) 26. Course Sehadula (Graph) Naud ol porte [Yes | 1S ead a window) Bachtracking es cae Getic | eo a7 f va [ate PEE eng iene fee) pln U ~~ INTERVIEW TIPS 4. hrf = Ak gaint te edad poten lary 2. Thnk Out Loud = Expl your optroad step-by-aep 3. Start Bala Force ~ Than oping, 4 Handle Edge Cases ~ Empty ipa the sverk, dphenan, fle, 5, Wa Claan Coda ~ Reale ond snared 1, og Ran = Use small eromple to date ger spre, 7 fnalge Conplasity = Tine & Space 8 Tat Yur Coda = Us al lsh cane, a a a a a a a a a 9 Dan Rare ~ Toke 9 deep rath © Communication + Logic = Selection Wins sie Resognize the pattern or order alice? ~ineat Ne {COMPLEXITY CHEAT SHEET QUICK REFERENCE TIME COMPLEXITY Use HashMap / Sat for frequency, Conga aa lockup, duplicates Otis) + Use Stack for parentheses, history, 0) undo, monotonic problems On tog) . Use Queue for BFS, level order tlating window mes. Use Deque for sliding window in J ma Feo SPACE COMPLEXITY Use Prefis: Sum for range queries. Use Binary Search on Answer for optimization pretems Anagram th digger! So Choose the right tool. Solve with confidence! @codewithZ }

Vous aimerez peut-être aussi