# From Brute Force to Efficient Solutions — Time & Space Complexity (Big-O)

Source: https://www.skillbyai.com/en/big-o/p-optimise

> Improve solutions with hashing, sorting with two pointers and sliding windows.

## Common optimisation moves

Most interview and real-world optimisations follow a few patterns. **Replace a search with a lookup**: if a nested loop searches for a partner element, store seen elements in a **hash map**, turning O(n²) into O(n) time with O(n) space (the classic two-sum problem). **Sort first, then sweep**: sorting costs O(n log n) and enables **two pointers** or binary search, which helps when you need pairs, closest values or duplicates without extra memory. **Sliding window**: for problems about contiguous subarrays or substrings, maintain a window and update it incrementally instead of recomputing each window, often reducing O(n²) or O(n·k) to O(n). **Precompute**: prefix sums, frequency counts and sorted copies answer many queries cheaply. **Avoid repeated work**: memoisation or dynamic programming for overlapping subproblems. Always start by stating the brute force and its complexity, then identify the repeated work it does; the optimisation usually removes exactly that repetition.

## From brute force to linear time

Each optimisation removes a repeated search or recomputation.

![A staircase descending from left to right, each step lower than the previous, from a tall block to a short block.](assets/figures/big-o/section-8-map.svg) — Figure 8.1 — Lowering complexity step by step.

## Two-sum: three solutions

Brute force, sort with two pointers, and a hash map.

```python
def two_sum_brute(nums, target):                 # O(n^2) time, O(1) space
    for i in range(len(nums)):
        for j in range(i + 1, len(nums)):
            if nums[i] + nums[j] == target:
                return i, j

def two_sum_sorted(nums, target):                # O(n log n) time, O(n) for index pairs
    pairs = sorted((x, i) for i, x in enumerate(nums))
    lo, hi = 0, len(pairs) - 1
    while lo < hi:
        s = pairs[lo][0] + pairs[hi][0]
        if s == target:
            return pairs[lo][1], pairs[hi][1]
        if s < target:
            lo += 1
        else:
            hi -= 1

def two_sum_hash(nums, target):                  # O(n) time, O(n) space
    seen = {}
    for i, x in enumerate(nums):
        if target - x in seen:
            return seen[target - x], i
        seen[x] = i
```

## Say the brute force first

In interviews, stating the brute-force approach and its complexity before optimising shows structured thinking and gives you a correct fallback if time runs out.

**Quiz:** What does the hash-map solution to two-sum trade to achieve O(n) time?

- [ ] Correctness
- [ ] Sorting stability
- [x] O(n) extra space for the map
- [ ] Recursion depth

*Answer:* O(n) extra space for the map. Storing seen values in a hash map uses linear extra memory to avoid the inner loop.