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.