Coding questions · Walmart Labs

Implement lexicographically smallest Two Sum

This question evaluates array manipulation, index-level reasoning, and algorithmic efficiency for locating pair sums under lexicographic tie-breaking, testing attention to ordering constraints and correct index selection.

You are given an unsorted integer array nums and an integer target.

Return the indices [i, j] (0-based) such that i < j and nums[i] + nums[j] == target.

If there are multiple valid pairs, return the pair with the smallest i. If there is still a tie (same i), return the one with the smallest j.

Assume at least one valid pair exists.

Follow-up (discussion only): Explain an efficient approach to find all triplets (i, j, k) with i < j < k such that nums[i] + nums[j] + nums[k] == 0, and you may ignore duplicate triplets (or assume all numbers are distinct).

Implement Lexicographically Smallest Two Sum

Constraints

2 <= len(nums) <= 2 * 10^5
-10^9 <= nums[i], target <= 10^9
nums is unsorted
At least one valid pair exists

Examples

Example 1

Input: ([2, 7, 11, 15], 9)
Output: [0, 1]

Explanation: nums[0] + nums[1] = 2 + 7 = 9, and this is the only valid pair.

Example 2

Input: ([1, 4, 5, 3, 2], 6)
Output: [0, 2]

Explanation: Valid pairs are [0, 2] (1 + 5) and [1, 4] (4 + 2). The pair [0, 2] is lexicographically smaller because it has the smaller first index.

Hints

Use a hash map from value to its first occurrence index so you can check whether the needed complement has appeared before in O(1) time.
Do not stop at the first valid pair you find. Keep comparing candidates using lexicographic order: smaller i first, then smaller j.