Pair Sum

Given a slice of integers and a target, return the indices of the two numbers that add up to the target. Scan left to right and return the first such pair you can complete: when you reach index j, return [i, j] for the earliest earlier index i whose value is the needed complement. Return the indices in increasing order. You may assume exactly one valid answer exists per test.

pairSum(nums, target)

Input format: nums | target — space-separated integers, a pipe, then the target. Output the two indices separated by a space.

Examples

pairSum([]int{3, 2, 4}, 6)    // → [1, 2]
pairSum([]int{2, 7, 11}, 9)   // → [0, 1]
pairSum([]int{3, 3}, 6)       // → [0, 1]

Walkthrough

Starting with the obvious approach

The most direct way: for every pair of indices (i, j), check if nums[i] + nums[j] == target. Two nested loops, done — but O(n²). For every element, you rescan the rest of the list looking for its partner. On a list of a few thousand numbers, that's millions of comparisons for what should be a simple lookup.

The nested loop repeats work: by the time you're checking index j, you already know every value before it. You just don't have a fast way to ask "have I seen the number I need?" — you're re-deriving that answer from scratch every time.

The key reframe

Instead of asking "does some other index pair with j?", flip it: "what value would I need to have already seen to pair with nums[j]?" That's target - nums[j] — the complement. A hash map gives you an O(1) average-case way to check "have I seen this complement, and where?"

Building the one-pass solution

Walk through the list once, tracking the current index j.
Before storing anything, check: is target - nums[j] already a key in your map? If yes, you've found your pair — return [i, j] using the stored index i.
If not, record nums[j] → j in the map, but only if that value isn't already stored, so the earliest occurrence wins for duplicates.
Because you check for the complement before inserting the current value, you never accidentally pair an element with itself.

Why order of operations matters here

A common bug: inserting the current value before checking for its complement. For nums = [3, 3] with target = 6, inserting first would immediately "find" index 0 as the complement of index 0 — pairing an element with itself. Check first, then insert, and that never happens — the earliest-index tie-break falls out for free.

This trades O(n) extra space (the map) for turning O(n²) time into O(n). Whenever you catch yourself rescanning past data to answer "have I seen X?", a hash map that remembers what you've visited usually collapses two nested loops into one.

main.py

Auto-saved

Console

Press Run to execute your code, or Submit to test and complete this problem.