Quick 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.

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

Given an integer array `nums` and an integer `target`, find two different positions in `nums` whose values add up to `target`, and return those positions as a pair of indices. **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`). Returned indices are below `10^5`. - Values may repeat and may be negative or zero; `nums` is not sorted. **Integer width:** no input, pair sum or output exceeds `2^31 - 1`, but a difference such as `target - nums[k]` is not covered by that bound: it can reach `3 * 10^9` in absolute value (for example `target = 2 * 10^9` with `nums[k] = -10^9`). If your approach computes such a value, use a 64-bit type for it (`long` in Java, `long long` in C++). **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 = [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.

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

Input: ([3, 9, 4, 6, 1], 10)

Expected Output: [1, 4]

Explanation: Source Example 1: pairs [1, 4] and [2, 3] both sum to 10; the smallest i wins even though [2, 3] has the smaller j and completes first in a left-to-right scan.

Input: ([-4, 7, 0, -4], -8)

Expected Output: [0, 3]

Explanation: Source Example 2: two equal -4 values at different positions form the only pair; a map of each value's first index misses it.

Hints

  1. With len(nums) up to 10^5, checking every pair (about 5 * 10^9 of them) is too slow; aim for close to linear or n log n time.
  2. Two different positions holding equal values may pair, but one position may never pair with itself: compare target = 2 * nums[i] when that value occurs once with when it occurs twice.
  3. The required answer is the lexicographically smallest [i, j], which is not necessarily the first pair a left-to-right scan completes (in Example 1, [2, 3] completes before [1, 4]).

Find the First Index Pair with a Target Sum

mediumChewyData Scientist

Given an integer array nums and an integer target, find two different positions in nums whose values add up to target, and return those positions as a pair of indices.

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). Returned indices are below 10^5.
  • Values may repeat and may be negative or zero; nums is not sorted.

Integer width: no input, pair sum or output exceeds 2^31 - 1, but a difference such as target - nums[k] is not covered by that bound: it can reach 3 * 10^9 in absolute value (for example target = 2 * 10^9 with nums[k] = -10^9). If your approach computes such a value, use a 64-bit type for it (long in Java, long long in C++).

Example 1

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

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.

Examples

Example 1
Input
([3, 9, 4, 6, 1], 10)
Output
[1, 4]
Notes
Source Example 1: pairs [1, 4] and [2, 3] both sum to 10; the smallest i wins even though [2, 3] has the smaller j and completes first in a left-to-right scan.
Example 2
Input
([-4, 7, 0, -4], -8)
Output
[0, 3]
Notes
Source Example 2: two equal -4 values at different positions form the only pair; a map of each value's first index misses it.

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.

Comments (0)

No comments yet. Be the first to comment!

Submit your answer

Approved first answer today earns 30 XP
Bold⌘BItalic⌘IInline code⌘`Bullet listTab to nest (○ ■)Numbered listTab to nest (a. i.)QuoteCode block
Formatting help
Signature
def find_pair_with_sum(nums: list[int], target: int) -> list[int]:
Sample call
find_pair_with_sum([3, 9, 4, 6, 1], 10)
Language
Case 1
Input
([3, 9, 4, 6, 1], 10)
Expected
[1, 4]
Case 2
Input
([-4, 7, 0, -4], -8)
Expected
[0, 3]

Browse More Questions

Show the approach

Approach

Scan the indices from right to left while keeping a hash map from each value to the smallest index at which it occurs among the positions already scanned, all of which lie to the right of the current index. At index i, look up target - nums[i]. If it is present, the stored index is the smallest j > i with nums[i] + nums[j] == target, so [i, j] is the best pair whose first index is i; record it. Then store nums[i] -> i, overwriting any larger index for the same value.

Invariant: before index i is processed, the map holds, for every value that occurs in nums[i+1..n-1], its smallest index in that range. Correctness: each recorded pair is the best pair for its own i, and because i decreases, the last pair recorded has the smallest i that has any partner. That pair is therefore exactly the lexicographically smallest valid [i, j]. If no lookup succeeds, the answer stays [].

Edge cases: the lookup happens before nums[i] is inserted, so an element never pairs with itself. A singleton array or target = 2 * x with a single x returns []. An equal value further to the right is already in the map, so duplicates at different positions pair correctly. The difference target - nums[i] can reach 3 * 10^9 in absolute value, so Java and C++ compute it in 64 bits; inputs, pair sums and outputs fit in 32 bits.

Common wrong approaches: a left-to-right one-pass map that returns the first completed pair fails Example 1, where [2, 3] completes before [1, 4]. Sorting plus two pointers can find a pair that is not lexicographically smallest, and it reports indices in value order rather than index order. A map of each value's first or last index mishandles duplicate partners.

Time complexity:
O(n) expected
Space complexity:
O(n)