λDSA Learning Hubpart of DSA Atlas

Problem-solving pattern library

Most interview problems are variations on a small set of patterns. Learn to recognize which one a prompt is asking for, and you turn “I’ve never seen this” into “this is a sliding window.”Each card gives the recognition clues, a template, and an example problem.

Two Pointers

Two coordinated indexes replace a nested loop on sorted or partitionable data.

When to identify it

  • Sorted array + pair/triplet target
  • 'In place' / 'O(1) space' filtering
  • Comparing elements from both ends

Visual clues in the prompt

  • “A sorted input”
  • “'find two/three that sum to…'”
  • “'remove/move/partition in place'”

Template

left, right = 0, len(nums) - 1while left < right:    total = nums[left] + nums[right]    if total == target: return [left, right]    if total < target:  left += 1    else:               right -= 1

Common variations

  • Converging (pair sum)
  • Read/write (move zeroes)
  • Fast/slow (cycle detection)
O(n) time, O(1) spaceFull topic →

Sliding Window

Maintain a contiguous window with incrementally-updated state instead of recomputing each subarray.

When to identify it

  • 'Longest/shortest/count' + 'contiguous/substring/subarray'
  • Window-checkable constraint
  • Fixed size k given

Visual clues in the prompt

  • “'longest substring such that…'”
  • “'maximum sum of k consecutive'”
  • “'smallest window containing…'”

Template

left = 0for right in range(len(s)):    add(s[right])    while invalid():        remove(s[left]); left += 1    best = max(best, right - left + 1)

Common variations

  • Fixed size
  • Variable (expand/contract while broken)
  • Shrink while valid (minimum window)
O(n) time, O(k) stateFull topic →

Fast & Slow Pointers

Two pointers at different speeds detect cycles and find midpoints in one pass.

When to identify it

  • Linked list cycle questions
  • 'Find the middle'
  • 'kth from the end'

Visual clues in the prompt

  • “'does the list have a cycle?'”
  • “'find where the cycle begins'”
  • “'happy number'”

Template

slow = fast = headwhile fast and fast.next:    slow = slow.next    fast = fast.next.next    if slow is fast: return True   # cycle

Common variations

  • Cycle detection
  • Cycle entry (Floyd part 2)
  • Midpoint / kth-from-end
O(n) time, O(1) spaceTry: Linked List Cycle →

Prefix Sum

Precompute cumulative totals once; answer any range sum in O(1).

When to identify it

  • Many range-sum queries on static data
  • 'count subarrays with sum k'
  • Range updates then read

Visual clues in the prompt

  • “'sum of elements from i to j'”
  • “'subarray sums equal to…'”
  • “'immutable range query'”

Template

prefix = [0]for x in nums: prefix.append(prefix[-1] + x)# sum(l..r) = prefix[r+1] - prefix[l]

Common variations

  • Range-sum query
  • Prefix + hash map (sum = k)
  • Difference array
  • 2-D prefix
O(n) build, O(1) queryFull topic →

Binary Search

Halve a sorted (or monotonic) search space each probe.

When to identify it

  • Sorted array lookup
  • 'minimum/maximum value such that…'
  • Monotonic feasibility test

Visual clues in the prompt

  • “Sorted input”
  • “'find the first/last…'”
  • “'minimum capacity/speed/days to…'”

Template

lo, hi = 0, len(a)while lo < hi:    mid = (lo + hi) // 2    if feasible(mid): hi = mid    else:             lo = mid + 1return lo   # first feasible

Common variations

  • Classic lookup
  • Lower/upper bound
  • Rotated array
  • Binary search on the answer
O(log n) per searchTry: Binary Search →

Merge Intervals

Sort by start, then sweep, merging or comparing overlapping ranges.

When to identify it

  • Input is intervals [start, end]
  • 'merge/insert/count overlaps'
  • Scheduling/booking

Visual clues in the prompt

  • “'merge overlapping intervals'”
  • “'minimum meeting rooms'”
  • “'can attend all meetings'”

Template

intervals.sort(key=lambda iv: iv[0])for start, end in intervals:    if merged and start <= merged[-1][1]:        merged[-1][1] = max(merged[-1][1], end)    else:        merged.append([start, end])

Common variations

  • Merge
  • Insert interval
  • Non-overlapping (greedy by end)
  • Meeting rooms (heap of ends)
O(n log n) timeTry: Merge Intervals →

Monotonic Stack

A stack kept sorted by evicting violators answers next-greater/smaller in one pass.

When to identify it

  • 'next/previous greater/smaller element'
  • Histogram / rectangle area
  • Span / temperature-to-warmer

Visual clues in the prompt

  • “'days until warmer temperature'”
  • “'largest rectangle'”
  • “'next greater element'”

Template

stack = []              # indexes, decreasing valuesfor i, x in enumerate(nums):    while stack and nums[stack[-1]] < x:        ans[stack.pop()] = x    stack.append(i)

Common variations

  • Next greater/smaller
  • Largest rectangle
  • Trapping rain water
  • Remove k digits
O(n) amortizedFull topic →

Top-K Elements (Heap)

A size-k heap keeps the best k seen so far in O(n log k).

When to identify it

  • 'k largest/smallest/most frequent'
  • 'kth largest'
  • Streaming best-of

Visual clues in the prompt

  • “'top k frequent'”
  • “'kth largest element'”
  • “'k closest points'”

Template

import heapqheap = []for x in nums:    heapq.heappush(heap, x)    if len(heap) > k: heapq.heappop(heap)return heap   # the k largest

Common variations

  • Kth largest
  • Top-k frequent
  • K closest points
  • Merge k sorted lists
O(n log k) time, O(k) spaceTry: Kth Largest Element in an Array →

K-Way Merge

A heap of the current front of each sorted source merges them in O(N log k).

When to identify it

  • Merging k sorted lists/arrays
  • 'smallest range covering all lists'
  • Matrix with sorted rows

Visual clues in the prompt

  • “'merge k sorted…'”
  • “'kth smallest in sorted matrix'”
  • “'smallest range'”

Template

heap = [(lst[0], i, 0) for i, lst in enumerate(lists) if lst]heapq.heapify(heap)while heap:    val, i, j = heapq.heappop(heap)    out.append(val)    if j + 1 < len(lists[i]):        heapq.heappush(heap, (lists[i][j+1], i, j+1))

Common variations

  • Merge k lists
  • Kth smallest in sorted matrix
  • Smallest range
O(N log k)Try: Merge k Sorted Lists →

Breadth-First Search

A queue explores by distance layers — shortest paths in unweighted graphs.

When to identify it

  • 'shortest/minimum steps'
  • Level-order tree traversal
  • Grid/maze reachability

Visual clues in the prompt

  • “'fewest moves to…'”
  • “'level order'”
  • “'rotting oranges' / 'walls and gates'”

Template

queue = deque([start]); seen = {start}while queue:    node = queue.popleft()    for nb in neighbors(node):        if nb not in seen:            seen.add(nb); queue.append(nb)

Common variations

  • Tree level order
  • Grid/multi-source BFS
  • Word ladder (implicit graph)
  • 0-1 BFS (deque)
O(V + E)Try: Binary Tree Level Order Traversal →

Depth-First Search

Dive deep then backtrack — components, cycles, and orderings.

When to identify it

  • Connected components / islands
  • Cycle detection
  • Path enumeration / tree recursion

Visual clues in the prompt

  • “'number of islands'”
  • “'all paths from source to target'”
  • “'detect a cycle'”

Template

def dfs(node):    visited.add(node)    for nb in neighbors(node):        if nb not in visited:            dfs(nb)

Common variations

  • Recursive/iterative
  • Grid flood fill
  • Cycle detection (3-color)
  • Path sum
O(V + E)Try: Number of Islands →

Topological Sort

Order a DAG so every edge points forward — peel zero-indegree nodes.

When to identify it

  • Dependencies / prerequisites / build order
  • 'can you finish all…'
  • Directed acyclic ordering

Visual clues in the prompt

  • “'course schedule'”
  • “'build order'”
  • “'alien dictionary'”

Template

queue = deque(n for n in graph if indeg[n] == 0)while queue:    node = queue.popleft(); order.append(node)    for nb in graph[node]:        indeg[nb] -= 1        if indeg[nb] == 0: queue.append(nb)# len(order) < V  ⇒  cycle

Common variations

  • Kahn's (BFS indegree)
  • DFS post-order
  • Cycle detection
  • Lexicographically smallest
O(V + E)Try: Course Schedule →

Union-Find

Merge groups and query connectivity in near-O(1) as edges arrive.

When to identify it

  • Dynamic connectivity (streamed edges)
  • 'number of groups/provinces'
  • Redundant connection / cycle

Visual clues in the prompt

  • “'accounts merge'”
  • “'number of connected components'”
  • “'redundant edge'”

Template

def find(x):    while parent[x] != x:        parent[x] = parent[parent[x]]; x = parent[x]    return xdef union(a, b):    parent[find(a)] = find(b)

Common variations

  • Path compression + rank
  • Cycle detection
  • Component counting
  • Kruskal's MST
O(α(n)) ≈ O(1) amortizedFull topic →

Backtracking

Choose, explore, un-choose — systematic search of a decision tree with pruning.

When to identify it

  • 'all subsets/permutations/combinations'
  • Constraint puzzles (N-Queens, Sudoku)
  • 'generate all valid…'

Visual clues in the prompt

  • “'find all…'”
  • “'generate parentheses'”
  • “'word search' / 'partition'”

Template

def bt(state):    if complete(state): record(state); return    for choice in choices(state):        make(choice); bt(state); undo(choice)

Common variations

  • Subsets/permutations/combinations
  • Constraint pruning (N-Queens)
  • Grid search
Exponential (output-bound)Full topic →

Dynamic Programming

Reuse overlapping-subproblem answers; define state, write transition.

When to identify it

  • 'count the ways' / 'min/max cost'
  • Overlapping subproblems in recursion
  • Choices with optimal substructure

Visual clues in the prompt

  • “'how many ways to…'”
  • “'minimum cost to…'”
  • “'longest/edit/knapsack'”

Template

dp = [base] * (n + 1)for i in range(1, n + 1):    dp[i] = transition(dp[i-1], dp[i-2], ...)return dp[n]

Common variations

  • 1-D (stairs, robber)
  • Knapsack
  • String DP (LCS, edit)
  • Grid DP
  • Bitmask DP
states × work per transitionFull topic →

Greedy

Commit to the locally optimal choice when it provably stays globally optimal.

When to identify it

  • 'maximum/minimum number of…'
  • Interval scheduling
  • Provable greedy-choice property

Visual clues in the prompt

  • “'maximum meetings'”
  • “'minimum arrows/platforms'”
  • “'jump game'”

Template

items.sort(key=chosen_key)for item in items:    if compatible(item, state):        take(item); update(state)

Common variations

  • Interval scheduling
  • Jump/reachability
  • Huffman
  • Fractional knapsack
usually O(n log n) after sortFull topic →

Cyclic Sort

When values are 1..n, place each at its home index to find missing/duplicate in O(n)/O(1).

When to identify it

  • Array of n values in range 1..n
  • 'find the missing/duplicate number'
  • 'first missing positive'

Visual clues in the prompt

  • “'numbers 1 to n'”
  • “'find all disappeared numbers'”
  • “'find the duplicate'”

Template

i = 0while i < n:    home = nums[i] - 1    if nums[i] != nums[home]:        nums[i], nums[home] = nums[home], nums[i]    else:        i += 1

Common variations

  • Missing number
  • All disappeared numbers
  • Find duplicate
  • First missing positive
O(n) time, O(1) spaceTry: Missing Number →

Bit Manipulation

Treat integers as bit arrays — XOR to cancel, masks to test/set, bitmasks as sets.

When to identify it

  • 'appears twice except one'
  • 'without extra space'
  • Subsets of ≤ 20 items

Visual clues in the prompt

  • “'single number'”
  • “'count bits'”
  • “'power of two'”

Template

result = 0for x in nums:    result ^= x   # pairs cancel, single survivesreturn result

Common variations

  • XOR (single/missing)
  • n & (n-1) tricks
  • Bitmask sets
  • Bitmask DP
O(n) time, O(1) spaceFull topic →