DSA SheetEasy
EditorialPractice

2 POINTERS › TWO POINTER ON ARRAYS

Two Sum

EasyEditorial · 5 minGenerated by gpt-5.6-luna · Aug 25

Open — the attempt gate is not wired up yet

This editorial is meant to unlock after you have run the problem at least once, with the worked solution behind one further deliberate click. That needs per-learner unlock state nothing stores today, so for now the whole article is open.

Try it yourself first →

Intuitioneach number tells you exactly what must have appeared before it

For a value x at index i to belong to the answer, its partner is not arbitrary: it must equal target - x. The problem therefore becomes a search for one earlier value while scanning the array. If that partner has already appeared, its stored index and i form the answer immediately.

Store each value together with its index as you pass it. The order matters: look for target - nums[i] before storing nums[i] itself. That guarantees the stored partner comes from a different index, so the current element can never be matched with itself. The unique-answer guarantee means the first match is enough.

Approachone lookup and one insertion per element

  1. Create a hash map from a value to its index, because checking every earlier value would repeat work and lead to quadratic time.
  2. Scan nums from left to right, keeping the current index i so the returned pair contains positions rather than only values.
  3. Compute need = target - nums[i], because only this complementary value can combine with nums[i] to reach target.
  4. Look up need before inserting the current value, because inserting first could let nums[i] match itself when need equals nums[i].
  5. If need is already in the map, return its stored index and i; the two indices are distinct because the current element has not been stored yet.
  6. If no match exists, store nums[i] with index i so a later element can use it as its earlier partner.
  7. Return an empty vector only as a fallback after the scan; the problem guarantees that a valid pair exists.

Complexityexpected bounds from constant-time hash operations

MEASUREBOUNDWHY
TimeO(n) expectedEach index is processed once, with one expected constant-time lookup and at most one expected constant-time insertion. The scan stops at the match, so it never does more than n iterations; pathological hash collisions can degrade this to O(n^2).
SpaceO(n) extraThe map stores at most one entry per scanned element, and the returned two-index vector is required output excluded from working-space usage. In the worst shape, the matching pair is at the end, so nearly all n values remain stored.
Here n is the number of elements in nums. The hash map's stated lookup and insertion costs are expected bounds.

Annotated solutionC++ · one pass with a value-to-index hash map

CPPOne left-to-right pass that checks the complement before recording the current value.
#include <unordered_map>
#include <vector>
using namespace std;

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int, int> seen;

        for (int i = 0; i < (int)nums.size(); i++) {
            int need = target - nums[i];
            auto it = seen.find(need);

            if (it != seen.end()) {
                return {it->second, i};
            }

            seen[nums[i]] = i;
        }

        return {};
    }
};

The two key lines are the lookup and the insertion order. At index i, find the complement among earlier elements first. Only when it is absent do you record the current value. This handles duplicates naturally: for [3, 3] with target 6, the first 3 is stored and the second 3 finds it, producing two different indices.

Common mistakesthree code shapes that lose the guarantee or the required performance

Previous · Find All K-Distant Indices in an Array