# How to Approach a DSA Interview Problem — From Brute Force to Optimal

Source: https://skills101.in/learn/dsa/dsa-approach-interview-problems — Skills101 free tutorial (Data Structures & Algorithms). Updated 2026-11-21.

You have learnt many data structures and algorithms. In a coding round the hard part is often not the algorithm itself but **choosing** it, under time pressure, while explaining your thinking. This lesson gives a method you can repeat for any problem, and works through one problem from a slow answer to a fast one. Patterns of interview rounds differ between companies and change over time, so treat this as a general method, not a description of any one company's process.

## 1. The method in seven steps

| Step | What you do | What you say aloud |
|---|---|---|
| 1. Understand | Restate the problem; work one small example by hand | "So for input …, the answer should be …" |
| 2. Clarify | Ask about input size, value range, duplicates, negatives, empty input, ties | "Can the array be empty? Are values whole numbers?" |
| 3. Constraints | Use `n` to guess the complexity you need | "n is 10⁵, so O(n²) is too slow; I need O(n log n)." |
| 4. Brute force | State the simplest correct idea and its cost | "Checking every pair works, but it is O(n²)." |
| 5. Optimise | Find the repeated work; match a pattern | "We re-sum the same range; prefix sums avoid that." |
| 6. Code | Write clean code with clear names | Explain each block briefly as you write |
| 7. Test | Dry-run a small example, then edge cases; state time and space | "For an empty list this returns 0, which is right." |

Do not skip steps 1 and 2. Solving the wrong problem quickly is the most common way to fail a round that you could have passed.

## 2. Let the constraints guide you

Online judges commonly allow around 1–2 seconds, and a typical machine does roughly 10⁸ simple steps per second (it varies with the language and the judge). So the size of `n` tells you which complexities can fit:

![Table matching input size to complexity: n up to 10 allows O(n factorial), 20 allows O(2 to the n times n), 500 allows O(n cubed), 5,000 allows O(n squared), 10 to the 5 or 10 to the 6 needs O(n log n) or O(n), and 10 to the 9 needs O(log n) or O(1)](https://skills101.in/learn-img/dsa/constraint-guide.svg)

This is a guide, not a law. But if a problem says `n ≤ 20`, it is a strong hint that trying all subsets is intended; if it says `n ≤ 10⁵`, a nested loop over all pairs will almost certainly time out.

## 3. Worked example: students in a marks range

**Problem:** `n` students have marks from 0 to 100 (whole numbers). Then `q` questions follow, each asking: "how many students scored between `L` and `R`, inclusive?" Both `n` and `q` can be up to 10⁵.

**Step 1–2.** Example: marks `[45, 72, 88, 45, 91, 60]`, question `(45, 72)` → 45, 72, 45, 60 → **4**. Ask: are `L ≤ R` always? Can marks repeat? (Yes, here.)

**Step 4 — brute force.** For each question, scan all marks: O(n) per question, **O(n · q)** total, up to 10¹⁰ steps. Correct but too slow.

**Step 5 — find the repeated work.** Every question scans the same unchanged list. Two ways to avoid that:

- **Sort once**, then each question is two binary searches: the first position with mark ≥ L and the first with mark > R. O((n + q) log n).
- Marks are small whole numbers (0..100), so **count** how many students got each mark, build **prefix sums** of the counts, and answer each question in O(1): `P[R + 1] − P[L]`. O(n + q + 100).

![Comparison of three approaches for n = q = 10 to the 5: scanning all marks per query takes about 10 times 10 to the 9 steps, sort plus two binary searches about 3.3 million, and a count array with prefix sums about 200 thousand](https://skills101.in/learn-img/dsa/brute-to-optimal.svg)

All three give the same answers — check that before trusting the fast ones:

```python
from bisect import bisect_left, bisect_right

def brute(marks, queries):
    return [sum(1 for m in marks if L <= m <= R) for L, R in queries]

def with_sort(marks, queries):
    s = sorted(marks)
    return [bisect_right(s, R) - bisect_left(s, L) for L, R in queries]

def with_counts(marks, queries, M=100):
    cnt = [0] * (M + 1)
    for m in marks:
        cnt[m] += 1
    P = [0] * (M + 2)                     # P[i] = students with mark < i
    for i in range(M + 1):
        P[i + 1] = P[i] + cnt[i]
    return [P[R + 1] - P[L] for L, R in queries]

marks = [45, 72, 88, 45, 91, 60]
queries = [(45, 72), (0, 100), (73, 87), (90, 100)]
print(brute(marks, queries))
print(with_sort(marks, queries))
print(with_counts(marks, queries))
```

```text
[4, 6, 0, 1]
[4, 6, 0, 1]
[4, 6, 0, 1]
```

**Step 7 — test edge cases.** The questions above already include a range with nobody (`73..87` → 0) and the full range (`0..100` → everyone); also try `L = R` (one exact mark). Then state the cost: "O(n + q) time and O(M) extra space, where M = 101 possible marks."

Notice that the **constraint on the values** (0..100), not just on `n`, unlocked the fastest idea. Always read every constraint.

## 4. Clues that point to a pattern

| If the problem says… | Try… |
|---|---|
| sorted array, find a pair or a position | two pointers, binary search |
| "subarray" with a sum or a count | prefix sums + hash map, sliding window |
| "k largest / smallest", "top k" | heap |
| next greater / smaller element | monotonic stack |
| fewest steps in an unweighted grid or graph | BFS |
| weighted shortest path | Dijkstra |
| dependencies, order of tasks | topological sort |
| "are these connected?" with merges | union-find |
| all combinations, permutations, subsets | backtracking (small n) |
| count ways, min cost, max value with choices | dynamic programming |
| meetings, bookings, time ranges | sort the intervals, sweep |
| prefix search over many words | trie |

When no clue fits, go back to the brute force and ask: **what is computed again and again?** Storing it (hashing, prefix sums, DP) or ordering the data (sorting, heaps) is the usual fix.

## 5. Testing like an interviewer

Before saying "done", dry-run your code on the example line by line, then try these inputs aloud:

- empty input, and a single element;
- all elements equal, and many duplicates;
- negative numbers and zero;
- already sorted and reverse sorted input;
- the largest values — can a sum overflow `int` in Java? Use `long`.

A short check like this often finds an off-by-one error before the interviewer does.

```python
def max_pair_sum(nums):
    if len(nums) < 2:                # edge case found while testing
        return None
    a, b = sorted(nums)[-2:]
    return a + b

for case in [[3, 9, 4], [5], [], [-2, -7, -1], [4, 4, 4]]:
    print(case, "->", max_pair_sum(case))
```

```text
[3, 9, 4] -> 13
[5] -> None
[] -> None
[-2, -7, -1] -> -3
[4, 4, 4] -> 8
```

## Common mistakes

- Starting to code before confirming the problem with an example.
- Ignoring the constraints and writing an O(n²) solution for n = 10⁵.
- Staying silent; the interviewer cannot give credit for thinking they cannot hear.
- Jumping to a "clever" idea without first stating a correct brute force.
- Not testing edge cases, or forgetting to state the time and space complexity.
- Learning solutions by heart instead of the pattern behind them; a small change in the question then breaks the memorised answer.

## Quick recap

- Understand → clarify → constraints → brute force → optimise → code → test.
- About 10⁸ simple steps per second is a rough guide: n = 10⁵ needs O(n log n) or better.
- Optimise by finding repeated work; match clues to patterns.
- Small value ranges allow counting arrays and prefix sums.
- Dry-run, test edge cases, and say the complexity out loud.


Practice quiz and free certificate: https://skills101.in/learn/dsa/dsa-approach-interview-problems