DSA Pattern Cheat Sheet

Use two pointers that move toward each other or in the same direction to efficiently search or compare elements in a sorted array or string.

Maintain a window of elements that slides across the array, expanding or shrinking to find optimal subarrays or substrings.

Precompute cumulative sums to answer range sum queries in O(1) time after O(n) preprocessing.

Track the maximum subarray sum ending at each position, resetting when the running sum becomes negative.

Use a hash map to count frequencies or track seen elements for O(1) lookups.

Use a hash map to find pairs that satisfy a target condition in a single pass.

Place each number at its correct index (value i at index i) by swapping, to find missing or duplicate numbers in a range [0, n] or [1, n].

Repeatedly halve the search space to find a target or boundary in O(log n) time.

Sort intervals by start time, then merge overlapping ones by comparing end times.

Use a heap (priority queue) or bucket sort to efficiently find the K largest/smallest/most frequent elements.

Use a max-heap and a min-heap together to efficiently track the median or partition elements into two balanced groups.

Merge K sorted arrays or lists using a min-heap to always pick the globally smallest element across all lists.

Use two pointers moving at different speeds to detect cycles, find midpoints, or determine list properties.

Reverse a linked list (or sublist) by reassigning next pointers while traversing.

Explore all nodes at the current depth before moving to the next level, using a queue.

Explore as deep as possible along each branch before backtracking. Use pre-order, in-order, or post-order depending on when you process the node.

Build solutions incrementally, abandoning a path as soon as it cannot lead to a valid solution.

Order vertices of a directed acyclic graph (DAG) so every edge goes from earlier to later in the ordering.

Track disjoint sets using parent pointers with path compression and union by rank for near O(1) operations.

Choose items (take or skip each) to maximize value within a capacity constraint.

Like 0/1 Knapsack, but each item can be used unlimited times.

Each state depends on a fixed number of previous states, like Fibonacci numbers.

Compare two sequences and build a 2D DP table where each cell represents the optimal answer for prefixes of both sequences.

Apply dynamic programming on tree structures using post-order DFS, where each node's answer depends on its children's answers.

Maintain a stack or deque where elements are always in sorted order, enabling efficient next-greater/smaller element queries.

A tree-like data structure where each node represents a character and paths from root to nodes form prefixes. Tries enable O(m) insert, search, and prefix queries (m = word length), making them ideal for dictionaries, autocomplete, spell checking, and word search problems where multiple strings share common prefixes.

Make the locally optimal choice at each step, trusting that it leads to a globally optimal solution. Greedy works when two properties hold: (1) greedy choice property — a local optimum is part of a global optimum, and (2) optimal substructure — an optimal solution contains optimal solutions to subproblems. Common in scheduling, interval selection, and jump/reachability problems.

Use bitwise operations (AND, OR, XOR, shift) for efficient computation on integers.

Fill a 2D DP table where each cell represents the optimal answer for reaching that position in a grid, using values from adjacent cells.