Pair With Target Sum
EasyArrays & HashingFree
Problem
You are given an array of integers nums and an integer target. Exactly one pair of different positions i and j holds values that add up to target.
Return the two indices as [i, j] with i < j.
Example 1
- Input:
- nums = [4, 9, 1, 6], target = 7
- Output:
- [2, 3]
nums[2] + nums[3] = 1 + 6 = 7.
Example 2
- Input:
- nums = [5, 5, 3], target = 10
- Output:
- [0, 1]
The two 5s sit at different positions, so they form a valid pair.
Constraints
- 2 ≤ nums.length ≤ 10^4
- -10^9 ≤ nums[i], target ≤ 10^9
- Exactly one valid pair exists.
Hint
Show the first hint
For each number x, which other value would complete the pair?
Walkthrough
How to approach it
01Clarify before coding
- Can the same element be used twice? No: the two indices must be different, but equal values at different positions are fine.
- Is there always an answer? Yes, exactly one pair, so no need to handle 'not found'.
- Is the array sorted? No, so two pointers would need a sort that loses the original indices.
02Brute force
Check every pair (i, j) with i < j and return the first whose values add up to target.
Cost: O(n²) time, O(1) space: about 50 million checks for n = 10^4, too slow for a good interview answer.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.