Quick Overview

Given an integer array and a target, return the indices of the only pair of different elements whose values add up to the target, smaller index first. Arrays hold up to 10,000 values of up to one billion in magnitude, and the task is a common warm-up that tests clean, efficient array reasoning.

Find the Unique Pair of Array Indices Whose Values Sum to a Target

Company: Meta

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Onsite

Given an array of integers `nums` and an integer `target`, return the indices of the two different elements whose values add up to `target`. ### Function Signature ```python def two_sum(nums: list[int], target: int) -> list[int]: ``` ### Rules - Exactly one pair of indices `i < j` satisfies `nums[i] + nums[j] == target`. - Return that pair as `[i, j]` with the smaller index first. - An element cannot be paired with itself, although equal values at different indices may form the pair. ### Constraints - `2 <= len(nums) <= 10000` - `-10^9 <= nums[i] <= 10^9` - `-10^9 <= target <= 10^9` - Exactly one valid pair exists. ### Examples **Example 1** Input: `nums = [2, 7, 11, 15]`, `target = 9` Output: `[0, 1]` Explanation: `nums[0] + nums[1] = 2 + 7 = 9`. **Example 2** Input: `nums = [3, 2, 4]`, `target = 6` Output: `[1, 2]` Explanation: `2 + 4 = 6`; index 0 cannot be used twice to make `3 + 3`. **Example 3** Input: `nums = [3, 3]`, `target = 6` Output: `[0, 1]`

Overview: Given an integer array and a target, return the indices of the only pair of different elements whose values add up to the target, smaller index first. Arrays hold up to 10,000 values of up to one billion in magnitude, and the task is a common warm-up that tests clean, efficient array reasoning.

Given an array of integers `nums` and an integer `target`, return the indices of the two different elements whose values add up to `target`. Implement `two_sum(nums, target)`. ### Rules - Exactly one pair of indices `i < j` satisfies `nums[i] + nums[j] == target`. - Return that pair as a list `[i, j]` with the smaller index first. - An element cannot be paired with itself, although equal values at different indices may form the pair. ### Constraints - `2 <= len(nums) <= 10000` - `-10^9 <= nums[i] <= 10^9` - `-10^9 <= target <= 10^9` - Exactly one valid pair exists. Every input value, every pairwise sum `nums[i] + nums[j]`, and every difference `target - nums[i]` lies within `[-2 * 10^9, 2 * 10^9]`, so no value exceeds `2^31 - 1`; signed 32-bit integers are sufficient. ### Examples **Example 1** Input: `nums = [2, 7, 11, 15]`, `target = 9` Output: `[0, 1]` Explanation: `nums[0] + nums[1] = 2 + 7 = 9`. **Example 2** Input: `nums = [3, 2, 4]`, `target = 6` Output: `[1, 2]` Explanation: `2 + 4 = 6`; index 0 cannot be used twice to make `3 + 3`.

Constraints

  • 2 <= len(nums) <= 10000
  • -10^9 <= nums[i] <= 10^9
  • -10^9 <= target <= 10^9
  • Exactly one valid pair exists.

Examples

Input: ([2, 7, 11, 15], 9)

Expected Output: [0, 1]

Explanation: Source example 1: 2 + 7 = 9 at indices 0 and 1.

Input: ([3, 2, 4], 6)

Expected Output: [1, 2]

Explanation: Source example 2 and self-pairing trap: 3 is target/2 but appears once, so [0, 0] is invalid; 2 + 4 = 6.

Hints

  1. For any fixed index, the value its partner must hold is completely determined by target and the value at that index.
  2. With up to 10,000 elements, checking every pair is roughly 50 million comparisons. Look for a way to tell whether a needed value has already appeared without rescanning the array.
  3. When target is exactly twice some value, that value counts only if it appears at two different indices. The answer always lists the smaller index first.

Loading coding console...

Show the approach

Approach

Scan the array once from left to right while keeping a hash map from each value already seen to the first index where it occurred. At index j, compute the complement target - nums[j]. If the complement is already in the map at index i, then i < j and nums[i] + nums[j] == target, so return [i, j]; otherwise record nums[j] (keeping its first index) and move on.

Invariant: before index j is processed, the map holds exactly the distinct values of nums[0..j-1], each mapped to its first index.

Correctness: let (i*, j*) be the unique valid pair. For every j < j*, no earlier index pairs with j (that would be a second valid pair), so the scan never returns early. At j = j*, nums[i*] is in the map because i* < j*, and it maps to i* itself: an earlier index i' with nums[i'] == nums[i*] would make (i', j*) a second valid pair. Looking up the complement before inserting the current value means an element is never paired with itself, so [3, 2, 4] with target 6 cannot yield [0, 0]. Because the matched index always comes from an earlier position, the result is already ordered with the smaller index first.

Edge cases: length 2, equal values forming the pair, zeros and a zero or negative target, a single value equal to target / 2, and values at +/-10^9 whose complements reach +/-2 * 10^9. Those complements still fit in a signed 32-bit integer; the Java and C++ references widen to 64-bit anyway.

Time complexity:
O(n)
Space complexity:
O(n)