Skip to content

Latest commit

 

History

History
109 lines (73 loc) · 4.1 KB

keys-patterns.md

File metadata and controls

109 lines (73 loc) · 4.1 KB

Key Patterns in Data Structures and Algorithms

A. Sliding Window

  • When to Use: Subarray problems (e.g., maximum sum, longest substring).
  • Key Idea: Expand/shrink the window based on conditions.
  • Example: Longest Substring Without Repeating Characters

B. Two Pointers

  • When to Use: Sorted arrays or lists (e.g., finding pairs).
  • Key Idea: Use two pointers to narrow down the search space.
  • Example: Two Sum II - Input Array Is Sorted

C. Hash Maps

  • When to Use: Fast lookups (e.g., frequency count, duplicates).
  • Key Idea: Store data in key-value pairs to optimize searches.
  • Example: Two Sum

D. Binary Search

  • When to Use: Search problems in sorted arrays.
  • Key Idea: Divide and conquer to find the target efficiently.
  • Example: Binary Search

E. Backtracking

  • When to Use: Recursive exploration (e.g., permutations, combinations).
  • Key Idea: Explore all possibilities and backtrack when conditions fail.
  • Example: N-Queens

F. Dynamic Programming

  • When to Use: Optimization problems with overlapping subproblems.
  • Key Idea: Solve smaller subproblems, store results (memoization/tabulation).
  • Example: Climbing Stairs

G. Graphs

  • When to Use: Problems involving connections (e.g., shortest path).
  • Key Idea: Use BFS, DFS, or Dijkstra’s Algorithm.
  • Example: Clone Graph

H. Deque

  • When to Use: Problems requiring efficient insertions and deletions from both ends.
  • Key Idea: Use a double-ended queue to manage elements.
  • Example: Sliding Window Maximum

I. Greedy Algorithms

  • When to Use: Problems where a locally optimal choice leads to a globally optimal solution.
  • Key Idea: Make the best choice at each step and build a solution piece by piece.
  • Example: Activity Selection Problem

J. Union-Find (Disjoint Set)

  • When to Use: Problems involving dynamic connectivity and finding connected components.
  • Key Idea: Use a data structure to efficiently merge sets and find representatives.
  • Example: Kruskal's Algorithm for Minimum Spanning Tree

K. Trees and Traversals

  • When to Use: Hierarchical data structures (e.g., XML parsing, file systems).
  • Key Idea: Use different traversal methods (in-order, pre-order, post-order) to visit nodes.
  • Example: Binary Tree Inorder Traversal

L. Heaps and Priority Queues

  • When to Use: Problems requiring frequent access to the minimum/maximum element.
  • Key Idea: Use a binary heap to efficiently perform insertions and deletions.
  • Example: Merge K Sorted Lists

M. Bit Manipulation

  • When to Use: Problems involving binary operations or optimizations at the bit level.
  • Key Idea: Use bitwise operators to perform operations directly on bits for efficiency.
  • Example: Single Number (finding unique element in a list where every other element appears twice)

N. Segment Trees and Fenwick Trees

  • When to Use: Range query problems (e.g., sum, minimum) and updates.
  • Key Idea: Use trees to efficiently store and calculate range-based queries.
  • Example: Range Sum Query

O. Tries

  • When to Use: Problems involving prefix searches, autocomplete, and dictionaries.
  • Key Idea: Use a tree-like structure to store strings by character.
  • Example: Implement Trie (Prefix Tree)

P. Advanced Graph Algorithms

  • When to Use: More complex graph problems (e.g., network flow, strongly connected components).
  • Key Idea: Use specialized algorithms like Ford-Fulkerson, Kosaraju's, or Tarjan's.
  • Example: Maximum Flow in a Flow Network

Q. Mathematical Algorithms

  • When to Use: Problems involving mathematical computations, number theory, or combinatorics.
  • Key Idea: Use properties of numbers (e.g., primes, greatest common divisors) and combinatorial counting.
  • Example: Sieve of Eratosthenes for Prime Numbers

R. Randomized Algorithms

  • When to Use: Problems where a probabilistic solution is more efficient.
  • Key Idea: Use randomness to achieve good average-case performance.
  • Example: Quickselect for finding kth smallest element