// The Two Sum Family: Pointers vs HashMap

one problem, two tools

Two Sum is the rare interview question that is really a tool choice in disguise. Both two pointers and the hashmap solve it in linear time once their precondition is met — the whole game is knowing which precondition you have and what each tool silently costs you.

The rest of this page: the same input pushed through both tools, what sorting quietly destroys, the framing that generalizes the dictionary far beyond Two Sum, and the follow-up question interviewers love to ask.

the two solutions, side by side

Sorted input → pointers. This is Two Sum II (LC 167), returning 0-based positions:

public int[] TwoSumSorted(int[] sorted, int target)
{
    int left = 0, right = sorted.Length - 1;

    while (left < right)
    {
        int sum = sorted[left] + sorted[right];
        if (sum == target)
            return [left, right];           // positions in the SORTED order

        if (sum < target) left++;           // sorted[left] too small for everyone
        else right--;                       // sorted[right] too big for everyone
    }
    return [];
}

Unsorted input → dictionary. This is Two Sum (LC 1):

public int[] TwoSum(int[] nums, int target)
{
    Dictionary<int, int> seen = new();      // value → index where it sits

    for (int i = 0; i < nums.Length; i++)
    {
        int need = target - nums[i];        // what would complete me right now
        if (seen.TryGetValue(need, out int j))
            return [j, i];                  // original indices, intact

        seen[nums[i]] = i;                  // now nums[i] is the one waiting
    }
    return [];                              // no pair exists
}

From ten thousand feet they are the same algorithm: one pass, and each element either resolves the search or narrows it. The difference is where the knowledge lives. The pointer version stores it in the sorted order itself — which is why it costs nothing. The dictionary version has to buy a memory, because in unsorted data the order carries no information.

the same input through both

nums = [5, 2, 7, 4, 3], target = 6 — the answer LC 1 wants is [1, 3] (2 + 4).

The dictionary, one pass — ask before you store:

The pointers, on a sorted copy [2, 3, 4, 5, 7]:

Both tools found 2 + 4. Only one of them can still tell you where those values were.

when sorting destroys information

Sorting is lossy: it throws away position. Two Sum II never notices, because its answer is phrased in sorted positions to begin with. LC 1’s answer is original positions — so a plain sort discards exactly the thing you were asked to return. You can patch it by decorating every value with its index before sorting:

public int[] TwoSumSortFirst(int[] nums, int target)
{
    // carry each value's original index — the O(1)-space claim just died
    var pairs = new (int Val, int Idx)[nums.Length];
    for (int i = 0; i < nums.Length; i++) pairs[i] = (nums[i], i);
    Array.Sort(pairs);                      // tuples compare by Val, then Idx

    int left = 0, right = pairs.Length - 1;
    while (left < right)
    {
        int sum = pairs[left].Val + pairs[right].Val;
        if (sum == target)
            return [Math.Min(pairs[left].Idx, pairs[right].Idx),
                    Math.Max(pairs[left].Idx, pairs[right].Idx)];

        if (sum < target) left++;
        else right--;
    }
    return [];
}

It works — on the trace input the pairs sort to (2,1) (3,4) (4,3) (5,0) (7,2), the same three steps as above land on (2,1) and (4,3), and out comes [1, 3]. Now look at the bill: an O(n) pairs array plus an O(n log n) sort — strictly worse than the dictionary on both axes. The patch exists only to prove it isn’t worth applying.

“key = what I need”

The dictionary line worth memorizing isn’t code, it’s the question behind it: standing at element i, what would I need to see to be done right now? Make that the lookup key. Then store yourself under the name a future element will ask for. The key is never “what I have” — it’s “what someone is waiting for”:

// the one-pass lookup shape behind the whole Two Sum family
Dictionary<int, int> seen = new();
for (int i = 0; i < items.Length; i++)
{
    int need = WhatWouldFinishMeNow(items[i], target);  // complement / prefixSum − k / …
    if (seen.TryGetValue(need, out int found))
        return Answer(found, i);            // ask BEFORE you store — no self-matching
    seen[KeyOf(items[i])] = InfoOf(i);      // register: someone later may need me
}
return [];

The ask-before-store order matters twice: it stops an element from matching itself (target 6, element 3 must not pair with its own entry), and it means every hit pairs the current element with a strictly earlier one — no pair is ever counted twice. The framing scales across the whole hashmap topic:

That last row is the entire tradeoff restated: a sorted array is a dictionary whose lookup is “move a pointer”.

the decision table

the family tree: 167 → 1 → 15 → 560

167  Two Sum II (sorted)      converging pointers — O(1) space, the root
 │
 │   drop the "sorted" guarantee: order now carries no information
 ▼
  1  Two Sum (unsorted)       the dictionary takes over — key = target − x
 │
 │   add a third addend: fix one element, the rest is 167 again
 ▼
 15  3Sum                     sort + outer loop + converging pointers
 │
 │   pairs of elements become pairs of PREFIX SUMS — count, don't locate
 ▼
560  Subarray Sum Equals K    the dictionary returns — key = prefixSum − k

• Two Sum II (LC 167) — where the discard argument is proven. Everything below inherits it.
• Two Sum (LC 1) — same question, minus the sorted guarantee. The tool flips because the answer wants indices and sorting would destroy them.
• 3Sum (LC 15) — the tool flips back: 3Sum’s answer wants values, not indices, so sorting is safe again — and it’s what makes duplicate-skipping and the inner pointer walk possible.
• Subarray Sum Equals K (LC 560) — the deep cut: prefix[j] - prefix[i] = k is Two Sum over running totals. Here the hashmap isn’t chosen, it’s forced — sorting prefix sums would destroy the subarray structure entirely.

when the interviewer asks “what if it’s sorted?”

The follow-up comes in both directions, and it’s a gift — it’s checking whether you chose your tool or just memorized it. Have the answers ready:

You solved LC 1 with a dictionary. “What if the input were sorted?” — “Then I’d switch to opposite-end two pointers: same O(n) time, O(1) space instead of O(n), because sorted order lets each comparison discard every pair involving one end. The dictionary only earns its space cost when order carries no information.”

You used pointers. “And if it’s not sorted?” — “Sorting first costs O(n log n) and loses the original indices. A value→index dictionary does one O(n) pass and keeps them — I’d trade O(n) space for that.”

“Can you keep O(1) space and return original indices?” — “Not below O(n²). Every fast approach pays either the sort — which loses indices unless I decorate values with them, and that’s O(n) space again — or the dictionary. I’d name that tradeoff and ask which resource matters more here.”

Saying the third answer out loud — naming the impossibility instead of flailing at it — is worth more than either solution. It’s the same recognition skill the master table trains across all seventeen patterns.