Return the Lexicographically Smallest Two-Sum Index Pair
Company: Google
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
## Return the Lexicographically Smallest Two-Sum Index Pair
### Problem
Implement `twoSumSmallestPair(nums, target) -> pair`.
Return the lexicographically smallest pair of distinct zero-based indices `[i, j]` such that `i < j` and `nums[i] + nums[j] == target`. Pair `[a, b]` is lexicographically smaller than `[c, d]` when `a < c`, or when `a == c` and `b < d`.
Return `[]` when no valid pair exists. Do not mutate `nums`.
### Constraints
- `0 <= nums.length <= 200,000`.
- `-1,000,000,000 <= nums[i], target <= 1,000,000,000`.
- Use signed 64-bit arithmetic for sums.
- Target expected `O(n)` time with a hash-based approach and `O(n)` auxiliary space.
```hint Make ties observable
Test an input with several valid pairs and duplicates before deciding what information a hash entry must retain to satisfy the output ordering.
```
### Examples
```text
nums = [4, 1, 5, 3, 3]
target = 6
pair = [1, 2]
```
Both `[1, 2]` and `[3, 4]` are valid; `[1, 2]` is lexicographically smaller.
```text
nums = [2, 2]
target = 4
pair = [0, 1]
```
```text
nums = [1, 2, 3]
target = 10
pair = []
```
### Discussion Requirements
- Explain why returning the first pair found by an arbitrary hash-map iteration order is not deterministic.
- Compare a one-pass hash approach with sorting a value-index copy, including how each preserves the required index tie-break.
Quick Answer: Find the lexicographically smallest pair of distinct indices whose array values sum to a target. Success depends on deterministic tie handling, duplicates, missing-result behavior, nonmutation, hash-based performance, and comparison with sorting-based alternatives.
Given an integer array `nums` and an integer `target`, return the **lexicographically smallest** pair of distinct zero-based indices `[i, j]` with `i < j` such that `nums[i] + nums[j] == target`.
Pair `[a, b]` is lexicographically smaller than pair `[c, d]` when `a < c`, or when `a == c` and `b < d`. In other words, among all valid pairs, first minimize the left index; only when the left indices tie, minimize the right index.
Return an empty list `[]` when no valid pair exists. Do not mutate `nums`.
### Output semantics
- The returned list is either empty or has exactly two elements, in the order `[i, j]` with `i < j`.
- Exactly one pair is correct for any input, because the lexicographic order above is a total order on index pairs.
- A pair is selected by its **indices**, not by its values. Two different index pairs holding the same values are still distinct answers.
### Examples
**Example 1**
```
Input: nums = [4, 1, 5, 3, 3], target = 6
Output: [1, 2]
```
Both `[1, 2]` (1 + 5) and `[3, 4]` (3 + 3) sum to 6. `[1, 2]` wins because `1 < 3`.
**Example 2**
```
Input: nums = [1, 4, 6, 100, 200, 9], target = 10
Output: [0, 5]
```
Both `[0, 5]` (1 + 9) and `[1, 2]` (4 + 6) sum to 10. `[0, 5]` wins because `0 < 1`, even though its right index `5` is much larger. Minimizing the right index is a different rule and produces the wrong answer here.
**Example 3**
```
Input: nums = [2, 2], target = 4
Output: [0, 1]
```
**Example 4**
```
Input: nums = [1, 2, 3], target = 10
Output: []
```
### Notes
- Duplicate values are allowed, and an element may not be paired with itself: `i` and `j` must be distinct positions.
- A pair sum, or a complement `target - nums[i]`, reaches 2,000,000,000 in absolute value -- inside the signed 32-bit range, but with under 7% to spare. Accumulate sums and complements in signed 64-bit integers (`long` in Java, `long long` in C++).
- The intended solution runs in `O(n)` time with `O(n)` auxiliary space.
Constraints
- 0 <= nums.length <= 200,000
- -1,000,000,000 <= nums[i] <= 1,000,000,000
- -1,000,000,000 <= target <= 1,000,000,000
- Pair sums and complements reach +/-2,000,000,000; use signed 64-bit arithmetic for sums (long in Java, long long in C++)
- nums must not be mutated by the solution
- Target complexity: O(n) time and O(n) auxiliary space
Examples
Input: ([], 6)
Expected Output: []
Input: ([5], 5)
Expected Output: []
Hints
- The pair with the smallest right index is not the same as the pair with the smallest left index. Decide which index the required order minimizes first, then drive your scan by that index.
- Fix a left index i. What you actually need is the smallest position j > i whose value equals target - nums[i]. Knowing every position at which each value occurs makes that question answerable without rescanning the suffix.
- Positions of equal values arrive in increasing order, so a single cursor per value can stay pointed at the first occurrence beyond the index you are currently considering, keeping the whole scan linear.