DSA Interview Cheat Sheet

1Two Pointers

Two indices, usually called left and right, walk through an array or string from different positions and move based on a simple rule.

When to use it

• The input is sorted, or sorting it is allowed
• You need a pair or triplet that meets a target
• You compare or swap elements from both ends

Common problems

Key idea: Each comparison lets you safely discard one end, so the O(n²) check of every pair collapses into a single O(n) pass.

How to spot it: "Sorted array" plus "find a pair / triplet / best pair" means two pointers first.

Go deeper: Two Pointers

2Sliding Window

A window over a contiguous part of an array or string that grows on the right and shrinks on the left while you keep a running summary of what is inside.

When to use it

• The question is about a subarray or substring
• You want the longest, shortest, maximum or a count of windows
• A brute force would recompute overlapping ranges

Common problems

Key idea: Add the element entering the window and remove the one leaving, instead of recomputing; every element is touched at most twice, giving O(n).

Types: Fixed window: the size k is given; slide one step at a time. · Variable window: expand until the rule breaks, then shrink until it holds again.

How to spot it: "Contiguous", "substring" or "subarray" together with "longest / shortest / at most K" points to a sliding window.

Go deeper: Sliding Window

3Binary Search

Repeatedly halve a search space that is ordered, either an array or a range of possible answers.

When to use it

• The data is sorted or rotated-sorted
• You need a position, boundary or first/last occurrence
• You want the minimum or maximum value that satisfies a yes/no check

Common problems

Key idea: Look at the middle and throw away the half that cannot contain the answer, turning O(n) into O(log n).

Types: On an array: find an index or boundary in sorted data. · On the answer: guess a value, check if it works, and narrow the range (Koko Eating Bananas).

How to spot it: "Sorted", "rotated", or "smallest speed / capacity / days such that" means binary search, often on the answer.

Go deeper: Binary Search

4Hashing

Use a hash map or set to remember what you have already seen, how often, or where.

When to use it

• You need O(1) "have I seen this?" lookups
• You are counting frequencies or grouping similar items
• You are matching pairs, such as a value and its complement

Common problems

Key idea: Trade a little memory for speed: a map turns a nested search into a single pass with constant-time lookups.

How to spot it: "Find two that add up", "duplicate", "anagram" or "group" on unsorted data means reach for a hash map.

Go deeper: Hashing & Counting · Prefix Sum

5Stack and Queue

A stack handles last-in-first-out work such as matching and undoing; a monotonic stack or deque keeps elements in sorted order to answer "next bigger" or "window max" questions.

When to use it

• Matching brackets or cancelling adjacent pairs
• Next greater or smaller element, spans, histogram areas
• Evaluating expressions or maximum of a sliding window

Common problems

Key idea: Each element is pushed and popped at most once. In a monotonic stack, popping smaller items is exactly the moment they find their answer, so the whole scan is O(n).

How to spot it: "Valid / balanced / nested" means stack; "next greater / warmer / span" means monotonic stack.

Go deeper: Stack · Monotonic Stack · Queue & Monotonic Deque

6Linked List Patterns

Rewire next pointers in place, often with a dummy head, and use fast and slow pointers to find the middle or detect cycles.

When to use it

• The input is a linked list
• You must reverse, merge, reorder or remove nodes in place
• You need the middle, the nth node from the end, or cycle detection in O(1) space

Common problems

Key idea: Save next before you change a pointer, and let a dummy node absorb the edge cases. Two pointers at different speeds find middles and cycles without extra memory.

How to spot it: "Linked list" plus "in place", "middle", "cycle" or "k-th from the end" means pointer rewiring or fast and slow pointers.

Go deeper: Linked List Techniques · Fast & Slow Pointers

7Trees (BFS and DFS)

Depth-first recursion builds a node's answer from its children; breadth-first traversal with a queue processes the tree level by level.

When to use it

• Heights, path sums, diameters or ancestors (DFS)
• Anything per level, a side view or minimum depth (BFS)
• A binary search tree, where in-order traversal gives sorted values

Common problems

Key idea: Trust the recursion: solve for the left and right subtrees, then combine. Every node is visited once, so traversals are O(n).

Types: DFS: pre-order, in-order or post-order recursion; post-order when parents need their children's answers. · BFS: a queue, processing exactly queue.size() nodes per level.

How to spot it: "Level" or "row" means BFS; "path", "height", "subtree" or "ancestor" means DFS; "BST" means use the in-order order.

Go deeper: Tree DFS · Tree BFS (Level Order) · Binary Search Tree & In-order

8Graph Traversal

Explore nodes and edges, including grids treated as graphs, with DFS or BFS while marking what you have visited.

When to use it

• Counting islands, regions or connected components
• Fewest steps or moves when every step costs the same (BFS)
• Ordering tasks with prerequisites (topological sort) or merging groups (union-find)

Common problems

Key idea: Mark a node visited the moment you reach it so nothing is processed twice: O(V + E). BFS reaches nodes in order of distance, which is why it finds shortest paths in unweighted graphs.

How to spot it: "Grid of 1s and 0s", "connected", "minimum moves" or "prerequisites" means graph traversal.

Go deeper: Graph DFS · Graph BFS · Topological Sort · Union-Find

9Recursion and Backtracking

Build a candidate one choice at a time, explore deeper, and undo the choice to try the next option, pruning branches that cannot work.

When to use it

• The problem asks for all subsets, permutations or combinations
• Placing items under constraints (N-Queens, Sudoku)
• Searching a board or tree of choices for a valid path

Common problems

Key idea: Choose, explore, un-choose. The work is still exponential because the output is, but pruning cuts dead branches early.

How to spot it: "Return all possible", "every combination" or "place N items with no conflicts" means backtracking.

Go deeper: Backtracking · Recursion & Divide and Conquer

10Dynamic Programming

Break a problem into overlapping subproblems, solve each once, and store the answers in a table or memo.

When to use it

• Counting ways, or finding a minimum or maximum over choices
• The same subproblem repeats in a recursive solution
• A choice at each step (take or skip, which coin, which character)

Common problems

Key idea: Define the state, write how it depends on smaller states, set the base cases, then fill in order. This turns exponential recursion into polynomial time.

Types: 1-D: climbing stairs, house robber. · Knapsack: coin change, subset sums. · Subsequences: LIS. · Grid: unique paths, minimum path sum. · Two strings: LCS, edit distance.

How to spot it: "Number of ways", "minimum cost", "longest" or "can you reach" with choices that overlap means DP.

Go deeper: 1-D Dynamic Programming · Knapsack DP · Longest Increasing Subsequence · Grid DP · String DP

11Greedy

Make the locally best choice at each step and never revisit it, when you can argue that this choice is always safe.

When to use it

• Scheduling or picking non-overlapping intervals
• Reachability or jump problems
• Sorting first reveals an obvious best next pick

Common problems

Key idea: One pass, often after a sort, with no backtracking. Usually O(n) or O(n log n). Always test the rule against a counterexample before trusting it.

How to spot it: "Minimum number of jumps / arrows / rooms" or "maximum non-overlapping" means try greedy, usually after sorting.

Go deeper: Greedy · Intervals & Line Sweep

12Heap / Priority Queue

A heap always gives you the smallest or largest item quickly. Use it for top-K selection, merging sorted sources and processing things in priority order.

When to use it

• K largest, smallest, closest or most frequent
• Merging several sorted lists
• A running median, or always taking the next best task

Common problems

Key idea: Keep a heap of size k so each insert costs O(log k), giving O(n log k) instead of sorting everything in O(n log n).

How to spot it: "K-th", "top K", "closest K" or "median of a stream" means a heap.

Go deeper: Heap & Top-K · Two Heaps · K-Way Merge

13Bit Manipulation

Work directly on binary representations with XOR, AND, OR and shifts.

When to use it

• Every value appears twice except one
• Counting set bits or checking powers of two
• Arithmetic without + or -, or subsets as bitmasks

Common problems

Key idea: x ^ x = 0 cancels pairs, and n & (n - 1) clears the lowest set bit. Both give O(n) time with O(1) extra space.

How to spot it: "Appears twice except one", "no extra space" or "without using + or -" means bit tricks.

Go deeper: Bit Manipulation