Problem Solving: Advanced

Solve pair problems in one pass

When an array is sorted, two pointers can find a pair that sums to a target in O(n) time instead of O(n²).

nums = [1, 3, 5, 7, 9]
target = 8
left, right = 0, len(nums) - 1
while left < right:
    s = nums[left] + nums[right]
    if s == target:
        print(f"Found: {nums[left]} + {nums[right]}")
        break
    elif s < target:
        ___left += 1right -= 1left -= 1
    else:
        ___right -= 1left += 1right += 1
else:
    print("No pair found")

The two-pointer technique achieves O(n) time by eliminating one element from the search space with every step. Either the left pointer advances or the right pointer retreats, so the total number of moves is at most n.

Replace nested loops with hash maps

Hash maps (Python dictionaries) provide O(1) average-case lookup. This single property is the key to optimizing countless algorithms.

Given an array and a target, find two numbers that sum to the target. The brute force O(n²) solution checks every pair. The hash map solution is O(n).

The key insight: instead of searching for each complement with complement in nums (O(n)), we store seen values in a dictionary for O(1) lookup.

Choosing when to use a hash map versus a brute-force scan is one of the most impactful optimization decisions you can make. Build the lookup once and query many times, check for the complement before storing the current value, and use enumerate when you need both index and value.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99

def two_sum(nums, target):
  seen = {}
  for i, num in enumerate(nums):
    seen[num] = i
    complement = target - num
    if complement in seen:
      return [seen[complement], i]
  return None

print(two_sum([3, 2, 4], 6))

Hash map lookups run in O(1) average time. This single property lets you replace an O(n²) double loop with an O(n) single loop: process each element once, look up its complement in constant time.

Count and rank items in one pass

word = "banana"
freq = {}
for ch in word:
    freq[ch] = freq.___getcountindex(ch, 0) + 1
most = ___maxminsorted(freq, key=freq.get)
print(f"{most}: {freq[most]}")

Python's collections.Counter builds frequency maps in a single call and adds useful methods like most_common(). Use it when writing production code, but understand the manual version for interviews and learning.

Answer range sum queries instantly

A prefix sum array stores running totals. Once built, you can calculate the sum of ANY subarray in O(1) time instead of O(n).

The prefix array has one more element than the original. Each prefix[i] is the sum of all elements before index i.

To get the sum from index i to j (inclusive), compute prefix[j+1] - prefix[i].

Many range sum queries

When you need repeated sums over different slices of static data

Finding target subarrays

Locate subarrays whose elements sum to a specific target value

Running averages

Calculate the average of any window without re-summing each time

Repeated range operations

Any "sum between index i and j" that runs inside a loop

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99

def range_sum(prefix, i, j):
  return prefix[j] - prefix[i]

nums = [3, 1, 4, 1, 5]
prefix = [0, 3, 4, 8, 9, 14]
print(range_sum(prefix, 1, 3))

The prefix array is one index longer than the original so that prefix[0] = 0 acts as a base. This design makes the range sum formula prefix[j+1] - prefix[i] work cleanly for all subarrays, including those starting at index 0.

Prefix sums excel when many range queries run on static data. Build the prefix array once in O(n), then answer each query in O(1). For m queries that is O(n + m) total, far better than O(n × m) with brute force.

Use sorting to unlock fast algorithms

Sorting is O(n log n), but it unlocks many efficient algorithms. If your problem allows reordering, sorting is often the key to an elegant solution.

Find the k smallest or largest elements by sorting, then taking a slice.

def has_close_pair(nums):
    ___nums.sort()nums.reverse()nums = list(set(nums))
    for i in range(len(nums) - 1):
        if abs(nums[i] - nums[i + 1]) ___<===>= 1:
            return True
    return False

print(has_close_pair([10, 3, 7, 4, 20]))

Sorting as preprocessing is a powerful general strategy. The O(n log n) cost of sorting is often dominated by the O(n) or O(n²) work you save afterward. When an unsorted problem seems to require checking all pairs, sort first and look only at adjacent elements.

The deduplication scenario above illustrates a recurring theme: real systems combine multiple algorithmic techniques. Hash-based grouping (O(n)) reduces the comparison space before fuzzy matching, which is the same idea behind choosing the right data structure first.