Find the Lexicographically Smallest Index Pair Whose Values Sum to a Target
Company: Chewy
Role: Data Scientist
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
Given an integer array `nums` and an integer `target`, find two different positions in the array whose values add up to `target`, and return those positions as a pair of indices.
The report names this only as a very simple two-sum question at the end of a live-coding round; this version fixes the output format, the rule for choosing among several valid pairs, and the result when no pair exists.
### Function Signature
```python
def find_pair_with_sum(nums: list[int], target: int) -> list[int]:
```
### Rules
- Indices are 0-based. A valid pair is two indices `i` and `j` with `0 <= i < j < len(nums)` and `nums[i] + nums[j] == target`.
- An element cannot be paired with itself, but two different positions that hold equal values can form a pair.
- Return a valid pair as the two-element list `[i, j]`, smaller index first.
- If several valid pairs exist, return the one with the smallest `i`; if several valid pairs share that smallest `i`, return the one among them with the smallest `j`. In other words, return the lexicographically smallest `[i, j]`.
- If no valid pair exists, return the empty list `[]`.
### Constraints
- `1 <= len(nums) <= 10^5`
- `-10^9 <= nums[k] <= 10^9` for every index `k`
- `-2 * 10^9 <= target <= 2 * 10^9`
- Every value, the target and every pair sum have absolute value at most `2 * 10^9`, so all of them fit in a signed 32-bit integer (`2^31 - 1 = 2147483647`).
- Values may repeat and may be negative or zero; `nums` is not sorted.
### Examples
**Example 1**
```text
Input: nums = [3, 9, 4, 6, 1], target = 10
Output: [1, 4]
```
Two pairs sum to 10: indices 1 and 4 (9 + 1) and indices 2 and 3 (4 + 6). The pair with the smaller first index, `[1, 4]`, is returned.
**Example 2**
```text
Input: nums = [-4, 7, 0, -4], target = -8
Output: [0, 3]
```
The two -4 values sit at different positions, so they form a valid pair. No other pair sums to -8.
**Example 3**
```text
Input: nums = [5, 1, 3], target = 10
Output: []
```
Only 5 + 5 would reach 10, but there is a single 5 and an element cannot be paired with itself, so no valid pair exists.
Overview: A coding task that asks for two different positions in an integer array whose values add up to a target, returning the lexicographically smallest index pair, or an empty list when no pair exists. It tests efficient lookup on large inputs, handling of duplicate and negative values, and exact tie-breaking.
Read the full Chewy Data Scientist interview experience this question came from
Given an integer array `nums` and an integer `target`, find two different positions in `nums` whose values add up to `target`, and return those positions as a pair of indices.
**Rules**
- Indices are 0-based. A valid pair is two indices `i` and `j` with `0 <= i < j < len(nums)` and `nums[i] + nums[j] == target`.
- An element cannot be paired with itself, but two different positions that hold equal values can form a pair.
- Return a valid pair as the two-element list `[i, j]`, smaller index first.
- If several valid pairs exist, return the one with the smallest `i`; if several valid pairs share that smallest `i`, return the one among them with the smallest `j`. In other words, return the lexicographically smallest `[i, j]`.
- If no valid pair exists, return the empty list `[]`.
**Constraints**
- `1 <= len(nums) <= 10^5`
- `-10^9 <= nums[k] <= 10^9` for every index `k`
- `-2 * 10^9 <= target <= 2 * 10^9`
- Every value, the target and every pair sum have absolute value at most `2 * 10^9`, so all of them fit in a signed 32-bit integer (`2^31 - 1 = 2147483647`). Returned indices are below `10^5`.
- Values may repeat and may be negative or zero; `nums` is not sorted.
**Integer width:** no input, pair sum or output exceeds `2^31 - 1`, but a difference such as `target - nums[k]` is not covered by that bound: it can reach `3 * 10^9` in absolute value (for example `target = 2 * 10^9` with `nums[k] = -10^9`). If your approach computes such a value, use a 64-bit type for it (`long` in Java, `long long` in C++).
**Example 1**
```text
Input: nums = [3, 9, 4, 6, 1], target = 10
Output: [1, 4]
```
Two pairs sum to 10: indices 1 and 4 (9 + 1) and indices 2 and 3 (4 + 6). The pair with the smaller first index, `[1, 4]`, is returned.
**Example 2**
```text
Input: nums = [5, 1, 3], target = 10
Output: []
```
Only 5 + 5 would reach 10, but there is a single 5 and an element cannot be paired with itself, so no valid pair exists.
Constraints
- 1 <= len(nums) <= 10^5
- -10^9 <= nums[k] <= 10^9 for every index k
- -2 * 10^9 <= target <= 2 * 10^9
- Every value, the target and every pair sum have absolute value at most 2 * 10^9, so all of them fit in a signed 32-bit integer (2^31 - 1 = 2147483647).
- Values may repeat and may be negative or zero; nums is not sorted.
Examples
Input: ([3, 9, 4, 6, 1], 10)
Expected Output: [1, 4]
Explanation: Source Example 1: pairs [1, 4] and [2, 3] both sum to 10; the smallest i wins even though [2, 3] has the smaller j and completes first in a left-to-right scan.
Input: ([-4, 7, 0, -4], -8)
Expected Output: [0, 3]
Explanation: Source Example 2: two equal -4 values at different positions form the only pair; a map of each value's first index misses it.
Hints
- With len(nums) up to 10^5, checking every pair (about 5 * 10^9 of them) is too slow; aim for close to linear or n log n time.
- Two different positions holding equal values may pair, but one position may never pair with itself: compare target = 2 * nums[i] when that value occurs once with when it occurs twice.
- The required answer is the lexicographically smallest [i, j], which is not necessarily the first pair a left-to-right scan completes (in Example 1, [2, 3] completes before [1, 4]).