From Brute Force to Efficient Solutions

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.

Two-sum: three solutions

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

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.

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

• Correctness
• Sorting stability
• O(n) extra space for the map
• Recursion depth