Two Sum

Given an integer array nums and an integer target, return the indices of two distinct elements whose values add up to target. Exactly one valid pair exists. Return the lower index first.

Pattern: Hash map complement lookup

• Mental model: as you scan left to right, keep a map from each value already seen to its index.
• Invariant: before checking nums[i], the map contains only earlier indices, so a found complement can never reuse the current element.
• Complexity: one pass gives O(n) time; the map may store up to O(n) values.

Input / output

• Input: nums: integer[], target: integer
• Output: [leftIndex, rightIndex]

Examples

1. nums = [2, 7, 11, 15], target = 9 returns [0, 1] because 2 + 7 = 9.
2. nums = [3, 2, 4], target = 6 returns [1, 2].

Constraints

• 2 <= nums.length <= 10,000
• -1,000,000 <= nums[i], target <= 1,000,000
• Do not reuse the same array element.

Follow-up Can you solve it in linear time with a single pass and explain the memory tradeoff?