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