Hash map

Return the indices of the two numbers that add up to a target.

Trigger

'A pair that sums to X' plus 'return indices'.

Approach

1. Say the brute force out loud — O(n²) nested loops — then discard it.
2. Trade space for time: one hash map from value to index.
3. Single pass: for each x, look up target − x before inserting x.

Target complexity

O(n) time, O(n) space.

Pitfall

Inserting before looking up, which lets an element pair with itself.

Say it out loud

“I'll trade space for time. A hash map gives me O(1) lookup of the complement, so one pass is enough — and I check before inserting so I never pair an element with itself.”

Solve on LeetCode

Decide whether two strings are permutations of each other.

Trigger

'Anagram', 'same letters', 'reordering'.

Approach

1. Length check first — a cheap early exit.
2. One Counter over the first string, decrement over the second, check all zeros.
3. Mention the sort-based alternative and why it is worse: O(n log n) versus O(n).

Target complexity

O(n) time, O(k) space where k is the alphabet size.

Pitfall

Assuming ASCII. Ask about Unicode — with combining characters, 'same letters' needs normalisation first.

Say it out loud

“Counting is linear where sorting is n log n, so I'll count. One question first: is this ASCII or Unicode? With Unicode I'd normalise before comparing, otherwise two visually identical strings can differ byte-wise.”

Solve on LeetCode

Group a list of words so that anagrams end up together.

Trigger

'Group equivalent things' — the canonical key pattern.

Approach

1. The craft is finding the key that makes equivalent inputs identical.
2. Sorted string as the key: simple, O(k log k) per word.
3. Better: a 26-tuple of counts, which is O(k) per word.

Target complexity

O(n·k) with the count key, versus O(n·k log k) with sorting.

Pitfall

Using a list as the dict key — it is unhashable. Use a tuple.

Say it out loud

“This is the canonical-key pattern: I need a function that maps every anagram of a word to the same value. Sorting works, but a tuple of letter counts is linear instead of n log n, and it's hashable so it can be the dict key directly.”

Solve on LeetCode

Find the length of the longest run of consecutive integers in an unsorted array.

Trigger

'Consecutive' plus an explicit O(n) requirement that rules out sorting.

Approach

1. Put everything in a set for O(1) membership.
2. Only start counting from a number x when x−1 is not in the set — that is a sequence start.
3. That guard is what keeps it linear: each element is visited by exactly one run.

Target complexity

O(n) time, O(n) space.

Pitfall

Counting from every element without the start guard, which turns it into O(n²).

Say it out loud

“Sorting would be n log n and the problem asks for linear. I'll use a set, and the trick is only to start a run when the predecessor is absent — that way each element is walked exactly once across all runs, so the total is linear despite the inner loop.”

Solve on LeetCode

Count the contiguous subarrays whose values sum to exactly k.

Trigger

'How many contiguous subarrays sum to X' — with negatives allowed, so no sliding window.

Approach

1. Brute force is O(n²) over all start-end pairs. Say it, then improve.
2. Prefix sums: sum(i..j) = pre[j] − pre[i−1].
3. So for each j I need the count of earlier prefixes equal to pre[j] − k — a hash map of counts.
4. Seed the map with {0: 1} so subarrays starting at index 0 are counted.

Target complexity

O(n) time, O(n) space.

Pitfall

Reaching for a sliding window. It only works with non-negative values; negatives break the monotonicity the window relies on.

Say it out loud

“A sliding window would need the sum to be monotonic in the window size, and with negative numbers it isn't. So I'll use prefix sums with a hash map of counts — the number of subarrays ending at j is the number of earlier prefixes equal to the current prefix minus k.”

Solve on LeetCode