Return the Lexicographically Smallest Two-Sum Index Pair

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.

Examples

nums = [4, 1, 5, 3, 3]
target = 6
pair = [1, 2]

Both [1, 2] and [3, 4] are valid; [1, 2] is lexicographically smaller.

nums = [2, 2]
target = 4
pair = [0, 1]

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.