DSA Cheat sheet

When I revise data structures and algorithms, I do not try to memorise every problem. I first choose the structure that matches the data, then check the operation that matters most: lookup, insertion, deletion, or traversal. This page is my compact starting point for interview practice and day-to-day problem solving.

How to use this cheat sheet

Use the complexity table to narrow down a suitable structure.
Practise the listed pattern with one small problem before moving to harder variations.
State assumptions in an interview: sorted input, duplicate values, recursion depth, and memory limits can change the best approach.

Complexity at a glance

Structure or algorithm	Typical strength	Typical cost
Array	Read by index	Access O(1), search O(n), middle insert/delete O(n)
Hash map / set	Fast membership and lookup	Average lookup, insert, delete O(1)
Stack / queue	Process data in order	Push/pop or enqueue/dequeue O(1)
Balanced binary-search tree	Ordered keys and ranges	Search, insert, delete O(log n)
Heap	Repeated smallest/largest item	Peek O(1), insert/remove O(log n)
Binary search	Sorted, searchable data	O(log n)
Merge sort	Stable general-purpose sorting	O(n log n) time, O(n) extra space

Core data structures

Array

Choose an array when position matters or when you need to scan neighbouring values. Arrays are the usual base for two pointers, sliding windows, prefix sums, and sorting-based solutions.

Good for: indexed access, contiguous data, fixed-size buffers.
Watch for: expensive insertion or deletion in the middle because later elements must shift.
Common patterns: two pointers, sliding window, prefix sum, monotonic stack.

Linked list

A linked list trades fast indexing for cheap changes near a known node. In interviews, the important skill is usually careful pointer handling rather than choosing a linked list by default.

Good for: inserting or removing after a known node.
Watch for: access by position is O(n); always protect against null.
Common patterns: slow/fast pointers, reversal, dummy head, merge two lists.

Stack and queue

A stack is last-in, first-out. A queue is first-in, first-out. Their value comes from matching the order required by the problem.

Stack: matching brackets, undo history, expression parsing, next-greater-element problems.
Queue: breadth-first search, scheduling, streaming work.
Deque: add and remove at both ends; useful for sliding-window maximum.

Hash map and hash set

Use a hash map when the question asks whether you have seen a value before, needs a frequency count, or needs a lookup by key. Use a set when only membership matters.

// JavaScript: two-sum in one pass
function twoSum(numbers, target) {
  const seen = new Map();

  for (let index = 0; index < numbers.length; index += 1) {
    const needed = target - numbers[index];
    if (seen.has(needed)) return [seen.get(needed), index];
    seen.set(numbers[index], index);
  }

  return [];
}

The trade-off is memory: this solution is O(n) time and O(n) additional space.

Tree and binary-search tree

Trees describe parent-child relationships. A binary-search tree keeps smaller values on one side and larger values on the other. Its O(log n) operations depend on remaining reasonably balanced.

Traversals: preorder, inorder, postorder, and level order.
Interview habit: decide whether recursion is safe for the expected depth; otherwise use an explicit stack.
Common patterns: DFS, BFS, lowest common ancestor, validate BST.

Heap / priority queue

A heap is not fully sorted. It is optimised to reveal the smallest item (min-heap) or largest item (max-heap). Use it when you repeatedly need the next best candidate.

Good for: top K values, merging sorted streams, task scheduling, shortest-path algorithms.
Key rule: do not use a heap when you need arbitrary lookup; use a map or tree instead.

Graph

A graph models connections: users and friendships, services and dependencies, locations and routes. An adjacency list is usually the practical representation for sparse graphs.

const graph = {
  api: ["auth", "database"],
  auth: ["database"],
  database: []
};

BFS: shortest path in an unweighted graph.
DFS: reachability, connected components, cycle detection.
Visit set: essential when a graph can contain cycles.

High-value algorithm patterns

Two pointers

Use two pointers when values are arranged in an array or string and one pointer can move independently of the other. A sorted input often makes this pattern especially effective.

Sliding window

Use a sliding window for a contiguous range: longest substring, maximum sum of a fixed-size subarray, or a section meeting a condition. Expand the right side; shrink the left side only when the rule is violated.

Binary search

Binary search is broader than finding a value. It also works when an answer is monotonic: for example, “can this capacity finish all tasks in time?” If a candidate works, search for a smaller workable candidate; otherwise search higher.

Recursion and backtracking

Backtracking explores a choice, records it, and undoes it before trying the next choice. It fits permutations, combinations, subsets, and constraint problems such as placing queens on a board.

Dynamic programming

Use dynamic programming when a problem has overlapping subproblems and an optimal result can be built from smaller results. First define the state in one sentence, then write the transition, base case, and iteration order.

Before submitting a solution

Explain the brute-force approach and why it is too slow.
Name the chosen data structure and the reason for it.
Test an empty input, one item, duplicates, and the largest expected input.
State both time complexity and extra-space complexity.

Final note

A cheat sheet should help you choose a direction, not replace practice. For every pattern above, solve one small example without looking at the answer and then write down the mistake you made. That review process is what turns the reference into lasting skill.

SoftwareDebug

Search Suggest