Find the Earliest Pair with a Target Sum
Company: Amazon
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: easy
Interview Round: Technical Screen
## Problem
Given an integer array `values` and an integer `target`, return the zero-based indices of two distinct elements whose sum equals `target`.
There may be several valid pairs. Return the pair with the smallest second index; among pairs with that second index, return the one with the smallest first index. Return `[-1, -1]` if no pair exists.
### Function Contract
Implement `twoSumEarliest(values, target)` and return a two-element integer array `[i, j]` with `i < j`.
### Constraints & Assumptions
- `0 <= len(values) <= 200,000`.
- Each value and `target` is between `-10^9` and `10^9`, inclusive.
- Intermediate addition fits in a signed 64-bit integer.
- The same array position may not be used twice, although equal values at different positions are allowed.
### Clarifying Questions to Ask
- Is a solution guaranteed? No.
- How are multiple solutions resolved? By the index rule in the prompt.
- Should the input be modified? No.
- Can negative values and duplicates appear? Yes.
```hint Scan in the order that defines the tie-break
If second indices are considered from left to right, the first complement already seen determines the earliest pair for that position.
```
### Examples
- `values = [2, 7, 11, 15]`, `target = 9` returns `[0, 1]`.
- `values = [3, 3]`, `target = 6` returns `[0, 1]`.
- `values = [1, 4, 2, 3]`, `target = 5` returns `[0, 1]`, not `[2, 3]`.
- `values = [5]`, `target = 10` returns `[-1, -1]`.
### Evaluation Focus
- Applies the deterministic tie-break without sorting away original indices.
- Handles duplicates, negatives, zero, and absence of a pair.
- Runs in expected `O(n)` time with `O(n)` auxiliary space.
### Extensions to Discuss
1. What changes if the array is already sorted?
2. How would you count all index pairs instead of returning one?
3. What trade-off allows `O(1)` extra space if modifying the input is permitted?
Quick Answer: Find two distinct array elements that sum to a target, returning the valid pair with the earliest second index and then the earliest first index, or a fixed sentinel when none exists.
## Problem
Given an integer array `values` and an integer `target`, return the zero-based indices of two distinct elements whose sum equals `target`.
There may be several valid pairs. Return the pair with the smallest second index; among pairs with that second index, return the one with the smallest first index. Return `[-1, -1]` if no pair exists.
### Function Contract
Implement `twoSumEarliest(values, target)` and return a two-element integer array `[i, j]` with `i < j`.
### Constraints & Assumptions
- `0 <= len(values) <= 200,000`.
- Each value and `target` is between `-10^9` and `10^9`, inclusive.
- Intermediate addition fits in a signed 64-bit integer.
- The same array position may not be used twice, although equal values at different positions are allowed.
### Clarifying Questions to Ask
- Is a solution guaranteed? No.
- How are multiple solutions resolved? By the index rule in the prompt.
- Should the input be modified? No.
- Can negative values and duplicates appear? Yes.
```hint Scan in the order that defines the tie-break
If second indices are considered from left to right, the first complement already seen determines the earliest pair for that position.
```
### Examples
- `values = [2, 7, 11, 15]`, `target = 9` returns `[0, 1]`.
- `values = [3, 3]`, `target = 6` returns `[0, 1]`.
- `values = [1, 4, 2, 3]`, `target = 5` returns `[0, 1]`, not `[2, 3]`.
- `values = [5]`, `target = 10` returns `[-1, -1]`.
### Evaluation Focus
- Applies the deterministic tie-break without sorting away original indices.
- Handles duplicates, negatives, zero, and absence of a pair.
- Runs in expected `O(n)` time with `O(n)` auxiliary space.
### Extensions to Discuss
1. What changes if the array is already sorted?
2. How would you count all index pairs instead of returning one?
3. What trade-off allows `O(1)` extra space if modifying the input is permitted?
Constraints
- 0 <= len(values) <= 200000.
- Every value and target is in [-1000000000, 1000000000].
- Use two distinct positions and return indices [i, j] with i < j.
- Choose the smallest second index, then the smallest first index.
- Return [-1, -1] when no pair exists.
- Intermediate addition and subtraction fit in signed 64-bit arithmetic.
Examples
Input: ([2, 7, 11, 15], 9)
Expected Output: [0, 1]
Explanation: Sample 1: indices zero and one form the earliest valid pair.
Input: ([3, 3], 6)
Expected Output: [0, 1]
Explanation: Sample 2: equal values at distinct positions may form the pair.
Hints
- Scan potential second indices from left to right so the first match automatically satisfies the primary tie-break.
- Remember only the earliest index for each value to satisfy the secondary tie-break.