leetcode algorithms

description, when to use, time complexity, template, visual aid - https://blog.algomaster.io/p/20-dsa-patterns

prefix sum

• preprocessing an array to create a new array where each element at index i represents the sum of all elements from the start up to i

• time complexity: allows for O(1) sum queries on any subarray

• when to use

  • multiple sum queries on subarrays

  • finding subarrays with a target sum

  • calculating cumulative totals

two pointers

• two pointers to traverse an array or list, typically from opposite ends or both moving in the same direction.

• time complexity: reduces from O(n²) to O(n) for many problems

• when to use

  • finding pairs in sorted arrays

  • comparing elements from both ends

  • partitioning arrays

  • palindrome checkschecks

sliding window

• maintains a window of elements and slides it across the array to find subarrays/substrings that satisfy a given condition. avoids recalculating overlapping parts of consecutive windows

• when to use

  • contiguous subarray/substring problems

  • max/min in window of size k

  • longest/shortest substring with certain properties

  • problems involving consecutive elements

fast & slow pointers

• two pointers moving at different speeds; when there is a cycle, the fast pointer will eventually meet the slow pointer

• when to use

  • detecting cycles in linked lists or arrays

  • finding the middle of a linked list

  • finding the start of a cycle

linkedlist in-place reversal

• reverses parts of a linked list without using extra space. manipulates pointers to reverse the direction of links

• when to use

  • reversing a linked list or a portion of it

  • reversing nodes in groups

  • checking for palindromes in linked list

frequency counting

• hashmaps or arrays to count occurrences of elements

• time complexity: transforms O(n²) to O(n) by trading space for time

• when to use

  • finding duplicates or unique elements

  • checking if two collections have the same elements

  • finding elements that appear k times

  • anagram problems

monotonic stack

• maintains elements in either increasing or decreasing order. as you iterate, you pop elements that violate the order, which reveals relationships between elements

• when to use

  • finding the next/previous greater/smaller element

  • problems involving spans or ranges

  • histogram problems

bit manipulation

• uses binary operations (AND, OR, XOP, NOT, shifts) to solve problems efficiently

• when to use

  • finding unique numbers (XOR)

  • checking power of 2

  • counting bits

  • generating subsets using bit masks

  • space optimization

top ‘K’ elements

• finds k largest or smallest elements using heaps (PQ). a min-heap of size k keeps track of k largest elements, and a max-heap keeps k smallest

• when to use

  • finding k largest/smallest elements

  • finding kth largest/smallest element

  • finding k most/least frequent elements

  • merging k sorted lists

overlapping intervals

• handles problems involving intervals that may overlap. key insight is that after sorting by start time, two intervals [a, b] and [c, d] overlap if b >= c

• when to use

  • merging overlapping intervals

  • finding interval intersections

  • scheduling problems (meeting rooms)

  • inserting into sorted intervals

modified binary search

• adaps binary search to handle rotated arrays, finding boundaries, or searching for conditions rather than exact values

• when to use

  • searching in rotated sorted arrays

  • finding first/last occurrence of element

  • finding minimum/maximum satisfying a condition

  • peak finding problems

binary tree traversal

• visits all notes in a specific order. preorder (root-left-right), inorder (left-root-right) and postorder (left-right-root)

• when to use

  • processing tree nodes in a specific order

  • building trees from traversals

  • bst operations (inorder gives sorted order)

  • tree serialization/deserialization)

depth-first search (DFS)

• explores as deep as possible along each branch before backtracking. uses a stack (or recursion) to remember which nodes to visit next)

• when to use

  • exploring all paths in a tree.graph

  • finding connected components

  • detecting cycles

  • topological sorting

  • path finding when all paths matter

breadth-first search (BFS)

• explores nodes level-by-level, visiting all neighbors before moving deeper. uses a queuue and guarantees the shortest path in unweighted graphs

• when to use

  • finding shortest path (unweighted)

  • level-order traversal

  • finding all notes at distance k

  • speaking problems (rotting oranges, walls, and gates)

shortest path

• minimam distance between nodes; dijstra’s for weighted graphs with non-negative weights, bellman-ford handles negative weights

• when to use

  • finding minimum cost/distance paths

  • network routing problems

  • weighted graph traversal

  • problems with varying edge costs

matrix traversal

• uses DFS or BFS to explore 2D grids. the key is handling 4-directional or 8-directional movement and boundary checks

• when to use

  • grid based problems (island, regions)

  • flood fill algorithms

  • finding connected components in 2D

  • path finding in mazes

backtracking

• explores all possible solutions by making choices and undoes (backtracks) when a path leads to an invalid solution

• when to use

  • generating all permutations/combinations.subsets

  • solving constraint satisfaction problems (N-queens, Sudoku)

  • finding all paths meeting certain criteries

  • string partitioning problems

prefix search (trie)

• stores strings character by character, allowing efficient prefix lookups. each node represents a character, and paths from root to nodes represent prefixes

• when to use

  • autocomplete and search suggestions

  • spell checking

  • IP routing (longes prefix match)

greedy

• locally optimal choices at each step, hoping to find a global optimum. work when optimal choices lead to global optimal solutions

• when to use

  • optimization problems with greedy choice propery

  • interval scheduling

  • huffman coding

  • activity selection

  • when proof by exchange argument works

dynamic programing patterns

• solves problems by breaking them into overlapping subproblems and stores results to avoid recomputation. works when problems have optimal substructure

• when to use

  • problems with overlapping subproblems

  • optimization (min/max) problems

  • counting problems (number of ways)

  • decision problems (can we achieve X?)

• common DP patterns

  • fibonacci

  • 0/1 knapsack

  • longest common subsequence

  • longest increasing subsequence