Google: Return the Lexicographically Smallest Two-Sum Index Pair

Quick Overview

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.

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.

Overview: 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.

Approach

The rule that decides the answer is that the left index is minimized first. So the scan is driven by i: walk i from left to right, and the first i that has any partner after it produces the answer, because every later i is lexicographically worse regardless of its partner. This is why the common one-pass two-sum idea (scan j, look up target - nums[j] among values seen so far, return on the first hit) is not a solution to this problem -- that loop returns the pair with the smallest right index. On nums = [1, 4, 6, 100, 200, 9] with target = 10 it returns [1, 2], while the required answer is [0, 5].

Given the driving index i, the remaining question is: what is the smallest j > i with nums[j] == target - nums[i]? The reference answers it with a precomputed index of occurrences.

Index every position. One pass builds positions, mapping each distinct value to the list of positions where it occurs. Because the pass runs left to right, each list is already sorted ascending.
Consume positions as i advances. A second map, consumed, counts how many positions of each value lie at or before the current i. At step i the counter for nums[i] is incremented, so for any value v, positions[v][consumed[v]] is exactly the first occurrence of v strictly after i -- every earlier occurrence has already been counted off by the step that visited it.
Look up the complement. With complement = target - nums[i], if positions has that value and its cursor has not run past the end of its list, the entry at the cursor is the smallest valid j, and [i, j] is returned immediately. Otherwise no partner exists after i and the scan moves on.
No pair. Falling out of the loop means no i had a partner after it, so the function returns [].

Correctness of the tie-break follows directly: the loop returns at the first i that admits any partner (minimizing the left index), and at that i the cursor yields the earliest partner position (minimizing the right index among pairs sharing that left index).

Both maps are built and read with constant-time operations, and each position is appended once and consumed once, so the total work is O(n) with O(n) auxiliary space. nums is only read, never reordered or written, which also rules out the sort-a-copy-of-(value, index) approach's hazard of losing the original positions the answer must report.

On width: with nums[i] and target each bounded by 1e9 in magnitude, a pair sum or a complement target - nums[i] reaches 2e9. That is still inside the signed 32-bit range, whose maximum is 2,147,483,647, but with less than 7% of headroom. The problem asks for signed 64-bit accumulation, and the Java and C++ references follow it: they key their maps by long / long long and compute the complement at 64-bit width. Nothing in the stated input domain makes a 32-bit intermediate wrap, so this is a margin requirement rather than a trap -- but it is the margin that disappears the moment a variant adds a third term or the bounds are widened.

Time complexity:

O(n)

Space complexity:

O(n)