Skip to content
Two Sum Deep Dive: Why 'Check-Then-Put' Separates Memorizers from Engineers

Two Sum Deep Dive: Why 'Check-Then-Put' Separates Memorizers from Engineers

An interviewer's comprehensive breakdown of LeetCode Two Sum, revealing why the check-then-put pattern prevents self-matching, how HashMap achieves O(1) lookup via hash perturbation and red-black trees, and engineering optimizations like pre-allocation and overflow protection.

Rain's Path to Java Mastery
Rain's Path to Java Mastery
Rain's Path to Java Mastery

One: Clarify Boundaries Before Coding

The author recommends spending 60–90 seconds asking three boundary questions:

"Can the array contain duplicates? e.g., [3,3] with target=6 should return [0,1], right?"

"Is a solution guaranteed? If not, return empty array or throw exception?"

"Can the array contain negative numbers or zero?"

Why ask these? The problem asks for indices , not values (so sorting loses indices), duplicates cannot pair with themselves, and the range ±10⁹ means target - nums[i] can overflow int . Proactively clarifying these signals engineering mindset.

Two: Thought Evolution from O(n²) to O(n)

2.1 Brute Force: Runs but Interviewer Shakes Head

// Not recommended as first choice in interview: O(n²)
public int[] twoSumBrute(int[] nums, int target) {
    for (int i = 0; i < nums.length; i++) {
        for (int j = i + 1; j < nums.length; j++) {
            if (nums[i] + nums[j] == target) {
                return new int[]{i, j};
            }
        }
    }
    return new int[]{};
}

Analogy: Brute force is like everyone in a room shaking hands with everyone else — n people require n² handshakes. At n=10⁴, operations hit 10⁸ and time out. Interviewer's first reaction: "Does this person have space-for-time awareness?" So after writing brute force, explicitly state the bottleneck.

2.2 Key Leap: Reduce "Lookup" from O(n) to O(1)

Bottleneck: each number scans the whole array to find its "other half" — that lookup is O(n). Reframe: while traversing, don't ask "who else is in the array?" but ask "Have I seen target - nums[i] before?" HashMap answers this in O(1). Handshakes become door registration.

Brute: everyone shakes hands one by one  O(n²)
Hash: check registry on entry, locate in one second  O(n)

One-sentence summary: Walk and store, check then store.

2.3 Four Solutions Complexity Comparison

Brute double loop : Time O(n²), Space O(1). Applicable: tiny data, extreme memory limit. Interview rating: ❌ Only as warm-up.

Two-pass hash (store all then query) : Time O(n), Space O(n). Applicable: —. Interview rating: ⚠️ Redundant, self-match pitfall.

Sort + two pointers : Time O(n log n), Space O(n)* (needs extra mapping to preserve indices). Applicable: already sorted, only need values. Interview rating: ⚠️ Loses original indices.

One-pass hash : Time O(n) , Space O(n). Applicable: unsorted array, need indices. Interview rating: ✅ Standard interview answer.

* Sort+two-pointers preserving original indices needs extra O(n) space for mapping, worse than hash — detailed in section seven.

At n=10000, brute force ~100M ops, hash ~10K ops — 10,000× difference .

Three: Hand-Simulate Execution, Better Than Memorizing Code

Walk through nums = [2,7,11,15], target = 9:

Step i=0: nums[0]=2, complement=7 ❌, map={}, action: not found, store {2→0}

Step i=1: nums[1]=7, complement=2 ✅, map={2→0}, action: hit! return [0,1]

Note: hit at i=1, remaining 11 and 15 never examined — worst case map holds at most n-1 elements. But the first trap awaits.

Four: Core Code — Interview Standard Version

class Solution {
    public int[] twoSum(int[] nums, int target) {
        // key: element value, value: element index
        // We query by "value", must return "index", so key-value designed this way
        Map<Integer, Integer> map = new HashMap<>();

        for (int i = 0; i < nums.length; i++) {
            int complement = target - nums[i];

            // Check first: have we seen this complement before?
            if (map.containsKey(complement)) {
                return new int[]{map.get(complement), i};
            }

            // Store later: register current element for future matches
            map.put(nums[i], i);
        }

        // Problem guarantees solution; engineering prefers throwing over returning null
        throw new IllegalArgumentException("No two sum solution");
    }
}

Four key decisions, each worth explaining to interviewer:

Why HashMap : Need O(1) lookup, and must store both "value + index"

Key stores what : Element value — because query entry is value

Value stores what : Index — because problem requires returning index

Why single pass : Check while storing, avoids full extra traversal and naturally prevents self-match

⚠️ Container selection reminder: Never write HashSet . Set only stores values, cannot store indices — problem requires indices, must use Map. Common interview fail point.

Engineering Enhanced Version: Three Differentiators

class Solution {
    public int[] twoSum(int[] nums, int target) {
        // ① Input validation, defend illegal input
        if (nums == null || nums.length < 2) {
            throw new IllegalArgumentException("nums length insufficient");
        }

        // ② Pre-allocate capacity. Load factor 0.75, capacity ≈ n / 0.75 + 1 ≈ n * 4/3 + 1
        // Avoid repeated resize + rehash during traversal
        Map<Integer, Integer> map = new HashMap<>(nums.length * 4 / 3 + 1);

        for (int i = 0; i < nums.length; i++) {
            // ③ Use long for complement to prevent overflow
            // When nums[i] = Integer.MIN_VALUE, target - nums[i] overflows to negative, may false-hit
            long need = (long) target - nums[i];
            if (need < Integer.MIN_VALUE || need > Integer.MAX_VALUE) {
                map.put(nums[i], i);  // Complement out of int range, array cannot have it, skip
                continue;
            }

            // ④ Single get replaces containsKey + get (two hash lookups)
            Integer j = map.get((int) need);
            if (j != null) {
                return new int[]{j, i};  // j always < i, order naturally correct
            }
            map.put(nums[i], i);
        }
        throw new IllegalArgumentException("No two sum solution");
    }
}
⚡ Technical highlights: Single get replaces containsKey + get : latter computes hash twice, former once. getOrDefault(complement, -1) works too. Return order needs no extra check : found complement is always a "senior", map.get(complement) < i , order correct by construction. Pre-allocate capacity : aggressive n-1 works (solution guarantees map never fills), but n / 0.75 + 1 strictly avoids resize.

Five: Biggest Trap — Check Then Store

The sole fatal trap is order of containsKey and put. Two wrong patterns both fail:

Wrong 1: Store all first, then query

nums = [3, 3], target = 6
All stored → {3: 1}  // index 0 overwritten by index 1!
Query → get(3) returns 1 → result [1, 1] ❌
Same element used twice

Wrong 2: Put then check

nums = [3, 2, 4], target = 6
i=0: store {3:0}, then check complement 3 → found self → return [0, 0] ❌

Only correct way: check then store. At query moment, current element not yet in map — map only has "previous elements", self-match physically impossible.

Re-run duplicate case nums = [3,2,4], target=6:

i=0: num=3, check 3 → empty → store {3:0}
i=1: num=2, check 4 → none → store {3:0, 2:1}
i=2: num=4, check 2 → ✅ hit, get(2)=1 → return [1, 2]

What about "later duplicate overwrites earlier"? No issue. Problem guarantees unique solution; first occurrence stored first, waits for second to pair — [3,3], target=6 correctly returns [0,1].

💡 Bonus move: After coding, hand-simulate [3,3] , target=6 before interviewer — shows you considered duplicate boundary. Often worth more than code itself.

Mnemonic: Walk and store, check then store.

Code written, interviewer almost always asks next: Why is HashMap O(1)?

Six: Deep Dive — Why HashMap O(1)

High-frequency follow-up, separates "memorized" from "truly understand". JDK 1.8 HashMap = array + linked list + red-black tree :

Three key mechanisms:

Hash perturbation : (h = key.hashCode()) ^ (h >>> 16), mixes high 16 bits to reduce collisions.

Bucket indexing : (n - 1) & hash, bitwise AND replaces modulo, fast and uniform.

Collision fallback : chaining via linked list; list length ≥ 8 AND array length ≥ 64 → treeify to red-black tree , worst-case lookup from O(n) to O(log n).

🎤 Interview script, memorizable: "HashMap uses chaining for collisions, JDK 1.8 adds red-black tree for extreme lists. Ideal lookup O(1), even degraded to tree O(log n), far better than brute scan. Collisions don't cause wrong results — containsKey and get traverse list/tree comparing keys, only slower, never incorrect."

Also clarify two container choices:

Why HashMap not TreeMap?

Structure : HashMap = hash table (array + list/tree); TreeMap = red-black tree

Lookup : HashMap O(1) ✅; TreeMap O(log n)

Key ordered? : HashMap no; TreeMap yes

Need order here? : No

Verdict : HashMap ✅ optimal; TreeMap unnecessary, pays log n for nothing

Why HashMap not HashSet? Problem needs both "value exists?" and "give me index" — must store two pieces of info, Set only stores value, disqualified.

Seven: Follow-up — Why Not Sort + Two Pointers?

Interviewer often asks: "Sort then two pointers is O(n log n), why not use?"

It's valid but has a hard flaw: problem requires original indices . Sorting scrambles indices; to restore answer you'd need extra "value → original index" mapping, more code and space not saved.

Time : Hash table O(n) ; Sort + two pointers O(n log n)

Space : Hash table O(n); Sort + two pointers O(1), but O(n) if original indices needed

Return original indices : Hash table ✅ native; Sort + two pointers ❌ needs extra mapping

Best for : Hash table — unsorted array, need indices; Sort + two pointers — already sorted, only need values

But if interviewer says "array already sorted", switch to two pointers immediately — sorted gives monotonicity, opposing pointers converge, O(n) time + O(1) space, beats hash on memory:

public int[] twoSumSorted(int[] nums, int target) {
    int l = 0, r = nums.length - 1;
    while (l < r) {
        long sum = (long) nums[l] + nums[r];  // same, prevent overflow
        if (sum < target)      l++;  // sum too small → move left right
        else if (sum > target) r--;  // sum too large → move right left
        else return new int[]{l, r};  // NOTE: these are sorted indices
    }
    throw new IllegalArgumentException("No two sum solution");
}
⚠️ Trap reminder: If original indices required, must store (value, index) pairs before sorting, space back to O(n) — then hash is simpler. Articulating this trade-off is itself a bonus point.

Eight: Advanced — Four Engineering Optimizations

May not be used in interview, but mentioning them proves production experience.

Highlight 1: Pre-allocate Capacity, Eliminate Resize Jitter

HashMap default load factor 0.75, exceeding threshold triggers resize — capacity doubles + full rehash , noticeable jitter at scale. Pre-size with n / 0.75 + 1 (i.e., n * 4/3 + 1):

int initialCapacity = (int) (nums.length / 0.75f) + 1;
Map<Integer, Integer> map = new HashMap<>(initialCapacity);

Highlight 2: Single get Saves Half the Lookups

containsKey()

+ get() = two independent hash computations, wasteful. Replace with single get() null-check or getOrDefault(complement, -1), lookup cost halved.

Highlight 3: long Prevents Overflow

target - nums[i]

overflows at extremes: e.g., nums[i] = Integer.MIN_VALUE, target = 1 → 1 - (-2147483648) overflows to negative, may false-hit. Using long intermediate with range check is basic engineering hygiene.

Highlight 4: Massive Data — Eliminate Boxing Overhead

HashMap<Integer, Integer>

boxing heavy: each entry carries object header, two Integer objects, Node pointer — millions of elements explode memory. Performance-critical contexts switch to primitive map:

import it.unimi.dsi.fastutil.ints.Int2IntOpenHashMap;

Int2IntOpenHashMap idx = new Int2IntOpenHashMap(expectedSize);
idx.defaultReturnValue(-1);  // -1 as sentinel, avoids boxing null check
int j = idx.get(need);
if (j != -1) return new int[]{j, i};

Nine: Technical Difficulty Panorama (Self-Check List)

Condensed all traps into a list, scan before interview:

Lookup efficiency bottleneck : Brute O(n²), large data times out → HashMap reduces single lookup to O(1), overall O(n)

Self-match : Put then check, returns [0,0] → Check then store , map only has "seniors"

Duplicate overwrite : Store all then query, [3,3] returns [1,1] → Single pass check-while-store, first waits for second

Wrong container : HashSet loses index; TreeMap pays log n → HashMap stores "value → index"

Key-value reversed : Map stores "index → value" → Key=value, value=index, because query by value

Integer overflow : target - nums[i] wraps negative → Use long for complement + range check

Resize jitter : Default capacity 16, frequent resize+rehash → Pre-allocate with n * 4/3 + 1 Double hash lookup : containsKey + get two traversals → Single get null-check or getOrDefault Boxing memory bloat : Millions of elements memory spikes → fastutil / eclipse-collections primitive map

Sort loses indices : Two pointers returns wrong indices → Store (value, index) pairs, or revert to hash

Thread safety : JDK7 concurrent put → cycle deadloop; JDK8 still data loss → ConcurrentHashMap, or better: shard parallel, merge at end

Boundary input : null, length<2 → NPE → Input validation + throw IllegalArgumentException No-solution contract : Silent null return hides bug → Agree with interviewer: empty array or throw

Ten: High-Frequency Interviewer Follow-ups — Prep Ammo

Q1: Array already sorted, still use hash? No. Sorted → monotonicity → opposing two pointers O(n) time + O(1) space, saves memory. Watch index issue.

Q2: Return all unique pairs? Sort + two pointers, on hit l++ / r-- and skip duplicates ( while (l < r && nums[l] == nums[l+1]) l++). Hash can but needs extra dedup, messier.

Q3: Data too large for memory? Three axes: ① External sort + merge two pointers; ② Bucket by value range to disk, load per bucket (or sharded external hash, MapReduce); ③ Bitmap / BloomFilter for existence pre-check, reduce useless I/O. Reaching distributed = this round stable.

Q4: Thread-safe HashMap? No. JDK7 concurrent put → list cycle deadloop; JDK8 fixed loop but still data overwrite. Use ConcurrentHashMap, or better — shard parallel, each thread local map, merge finally , avoid shared writes at source.

Q5: Upgrade to 3Sum (LeetCode 15)? Sort + two pointers fixing one number, core difficulty shifts to dedup: outer skip same first number, inner skip same pair values. Most common next station.

Q6: Go / Python differences? Logic identical, syntax only: Go map[int]int, Python dict, both hash O(1) lookup.

Q7: No extra space allowed? Only fallback brute O(n²) or sort+two pointers — but indices scrambled, must save original indices, full circle back to O(n) space. Explaining this "circle back" to interviewer beats saying "impossible".

Eleven: Interview Rhythm — Soft Details That Decide 60 vs 90

❌ Two cardinal sins:

Start writing brute force silently — impression score ×0.6;

Recite optimal solution instantly, skip thinking — interviewer suspects memorization.

✅ Correct rhythm, five steps:

Spend 60–90s clarifying boundaries (duplicates, solution existence, negatives);

Verbally state brute as baseline, explicitly pinpoint bottleneck "lookup is O(n)";

Naturally transition to hash optimization, highlight "space for time";

Write code, announce complexity: time O(n), space O(n);

Proactively explain edge handling: check-then-store prevents self-match, overflow, no-solution fallback.

Closing script, ready to use:

"This problem's core isn't 'can you write a hash map', but whether you have space-for-time optimization instinct and true understanding of HashMap internals. In practice: clarify boundaries first, state brute as baseline, transition to hash, code with 'check-then-store' detail — that's basically a pass."

Final Words

One sentence captures all:

Two Sum = hash map space-for-time, compresses "double loop" into "single pass"; engineering adds three cuts: check-then-store prevents self-match, long prevents overflow, pre-allocate prevents resize.

Practical advice: don't stop at AC — explain every line's "why" to yourself: why this key-value design, why check-then-store, why not TreeMap. What you can articulate is what truly sticks.

Original Source

Signed-in readers can open the original source through BestHub's protected redirect.

Sign in to view source
Republication Notice

This article has been distilled and summarized from source material, then republished for learning and reference. If you believe it infringes your rights, please contactadmin@besthub.devand we will review it promptly.

JavaHashMapinterview preparationEngineering PracticesAlgorithm OptimizationHash TableTime ComplexityTwo Sum
Reader feedback

How this landed with the community

Sign in to like

Rate this article

Was this worth your time?

Sign in to rate
Discussion

0 Comments

Thoughtful readers leave field notes, pushback, and hard-won operational detail here.