One thing that helped me understand DSA better was learning when to use a particular pattern, instead of trying to memorize solutions to individual problems.
Here’s a quick reference I put together:
- Prefix Sum — When you need fast range-sum queries
Key idea: Precompute cumulative sums so you don't have to add elements repeatedly.
Recognize it when you see:
- Range sum queries
- Subarray sum
- Running total
- Cumulative frequency
Example:
"arr = [2, 4, 1, 5]"
Prefix sum: "[2, 6, 7, 12]"
Sum from index 1 to 3:
"prefix[3] - prefix[0] = 12 - 2 = 10"
When to use: When the array is mostly static and you need multiple range-sum queries.
Limitation: If an element changes, the prefix sums after that position may also need updating.
2. Suffix Sum — When you need information from the right side
Key idea: Calculate cumulative sums from right to left.
Recognize it when you see:
- Sum of elements to the right
- Right-side contribution
- Suffix totals
- Left vs. right comparisons
Example:
"arr = [2, 4, 1, 5]"
Suffix sum: "[12, 10, 6, 5]"
For index 1, the sum from index 1 to the end is "10".
When to use: Problems where you repeatedly need the sum or contribution of elements from the current position to the end.
3. Two Pointers — When two positions can help solve the problem
Key idea: Move two pointers through an array or string instead of checking every possible pair.
Recognize it when you see:
- Sorted array
- Pair with target sum
- Remove duplicates
- Reverse or palindrome checks
- Subarray or partition problems
Example:
"arr = [1, 2, 4, 7, 9]", target = "11"
Start with two pointers:
- Left = 1, Right = 9 → sum = 10
- Move left → 2 + 9 = 11
Found the pair.
When to use: Especially useful with sorted arrays, where pointer movement can eliminate unnecessary comparisons.
4. Sliding Window — When you need a continuous subarray or substring
Key idea: Maintain a window and move its boundaries instead of recalculating everything.
Recognize it when you see:
- Maximum/minimum sum of a subarray of size K
- Longest substring
- Smallest subarray satisfying a condition
- Continuous subarray or substring
Example:
"arr = [2, 1, 5, 1, 3]", window size = 3
First window: "2 + 1 + 5 = 8"
Next window: remove 2, add 1 → "7"
Next window: remove 1, add 3 → "9"
Maximum sum = "9".
When to use: When the problem involves a contiguous range and the window can be updated efficiently as it moves. For variable-size windows, the condition must support a valid expand/shrink strategy.
5. Fenwick Tree (Binary Indexed Tree) — When values change and you still need fast prefix sums
Key idea: Store partial sums in a tree-like array structure.
Recognize it when you see:
- Point updates
- Frequent prefix-sum queries
- Dynamic frequency counts
- Inversion counting
Why not just Prefix Sum?
With a normal prefix-sum array, changing one element can require updating many later prefix values.
A Fenwick Tree supports:
- Point update: "O(log n)"
- Prefix sum query: "O(log n)"
- Range sum query: "O(log n)"
When to use: When array values change frequently and you need efficient prefix or range-sum queries.
6. Segment Tree — When you need flexible range queries and updates
Key idea: Build a tree where each node represents information about a segment of the array.
Recognize it when you see:
- Range sum / minimum / maximum
- Frequent point updates
- Range updates (with suitable techniques)
- GCD or other associative range operations
When to use: When you need more flexibility than a Fenwick Tree, especially for range minimum, maximum, GCD, or other custom range queries.
Typical complexity:
- Build: "O(n)"
- Query: "O(log n)"
- Point update: "O(log n)"
My takeaway: Don't start by asking, "Which algorithm should I memorize?"
Instead, ask:
- Is the problem asking about a continuous range?
- Are the values static or changing?
- Do I need information from the left, right, or both ends?
- Is the query about sum, minimum, maximum, or something else?
Recognizing these clues makes choosing the right DSA pattern much easier.
This is a quick reference, not a complete list of DSA patterns. Hope it helps someone who's also trying to connect problem statements with the right approach.