PracHub
QuestionsCoachesLearningGuidesInterview Prep

Quick Overview

This question evaluates array and hashing algorithms, pair-sum reasoning including duplicate handling and lexicographic minimality, streaming and external-memory algorithm design, trade-offs in time/space complexity, and extension to three-sum with deduplication.

  • Medium
  • Amazon
  • Coding & Algorithms
  • Data Scientist

Solve two-sum variants at scale

Company: Amazon

Role: Data Scientist

Category: Coding & Algorithms

Difficulty: Medium

Interview Round: Onsite

Base task: Given nums = [3, 1, 2, 2, 4] and target = 4, return the 0-based index pair (i, j) with i < j such that nums[i] + nums[j] = target. If multiple pairs exist, return the lexicographically smallest (i, j). Achieve expected O(n) time and O(n) extra space; justify correctness for duplicates. Follow-ups: 1) If nums is already sorted ascending, provide an O(n) time, O(1) space solution and prove minimal lexicographic pair selection still holds. 2) Streaming variant: nums arrives as an unbounded stream and you must answer membership queries two_sum_exists(x) online with sublinear memory. Propose a data structure, update/query costs, and false-positive/false-negative trade-offs if any. 3) Very large array (hundreds of millions of ints) under a 200MB RAM cap. Describe an external-memory or hashing-with-bucketing approach, handling negatives and overflow. 4) Extend to three-sum for a sorted array; give complexity and deduplication strategy.

Quick Answer: This question evaluates array and hashing algorithms, pair-sum reasoning including duplicate handling and lexicographic minimality, streaming and external-memory algorithm design, trade-offs in time/space complexity, and extension to three-sum with deduplication.

Two-Sum: lexicographically smallest index pair

Given an integer array `nums` and an integer `target`, return the 0-based index pair `[i, j]` with `i < j` such that `nums[i] + nums[j] == target`. If several pairs exist, return the lexicographically smallest pair (smallest `i`, then smallest `j`). If no pair exists, return an empty list `[]`. Achieve expected O(n) time and O(n) extra space. The array is NOT assumed to be sorted and may contain duplicates, zeros, and negatives. Correctness with duplicates: scan left to right; for each index `j`, check whether the complement `target - nums[j]` was already seen at some earlier index `i < j`. Storing only the FIRST index at which each value appears guarantees the smallest possible `i` for any matching `j`, and scanning `j` in increasing order yields the lexicographically smallest pair overall.

Constraints

  • 0 <= len(nums) <= 10^5
  • -10^9 <= nums[i], target <= 10^9
  • Indices are 0-based and the returned pair must satisfy i < j
  • Return [] when no valid pair exists

Examples

Input: ([3, 1, 2, 2, 4], 4)

Expected Output: [0, 1]

Explanation: nums[0]+nums[1]=3+1=4. Pair (2,3)=2+2=4 also works but (0,1) is lexicographically smaller.

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

Expected Output: [0, 1]

Explanation: 2+7=9.

Input: ([3, 3], 6)

Expected Output: [0, 1]

Explanation: Duplicate values: first 3 stored at index 0, second 3 at index 1 finds complement.

Input: ([1, 2, 3], 7)

Expected Output: []

Explanation: No pair sums to 7.

Input: ([], 5)

Expected Output: []

Explanation: Empty input.

Input: ([5], 5)

Expected Output: []

Explanation: A single element cannot form a pair.

Input: ([0, 4, 3, 0], 0)

Expected Output: [0, 3]

Explanation: Two zeros at indices 0 and 3 sum to 0; the earliest-index zero is paired with the next matching zero.

Input: ([-3, 4, 3, 90], 0)

Expected Output: [0, 2]

Explanation: -3 + 3 = 0; works with negatives.

Input: ([1, 1, 1, 1], 2)

Expected Output: [0, 1]

Explanation: First two 1s give the lexicographically smallest pair.

Hints

  1. A single pass with a hash map from value -> earliest index gives O(n) time.
  2. Store only the FIRST index at which each value occurs so the matching i is as small as possible.
  3. Scanning j from left to right and taking the first complement hit yields the lexicographically smallest (i, j).

Follow-up 1 - Sorted array two-sum in O(1) extra space

The array `nums` is now guaranteed to be sorted in ascending order. Return an index pair `[lo, hi]` with `lo < hi` such that `nums[lo] + nums[hi] == target`, using O(n) time and O(1) extra space. Return `[]` if no pair exists. Use the two-pointer technique: start `lo` at the left end and `hi` at the right end. If the sum is too small, increment `lo`; if too large, decrement `hi`; on equality, return the pair. Because the array is sorted, every candidate sum is monotone in each pointer move, so no valid pair is ever skipped. Note on duplicates: the pure O(1)-space two-pointer returns a VALID outermost index pair, not necessarily the lexicographically smallest one. For example, on `[1,1,1,1]` with target 2 it returns `[0,3]` (the first equality it meets), which is acceptable here since recovering the absolute-smallest index pair among equal values would require extra bookkeeping and break the O(1)-space guarantee.

Constraints

  • nums is sorted in non-decreasing order
  • 0 <= len(nums) <= 10^5
  • -10^9 <= nums[i], target <= 10^9
  • Return [] when no valid pair exists

Examples

Input: ([1, 2, 2, 3, 4], 4)

Expected Output: [0, 3]

Explanation: nums[0]+nums[3]=1+3=4 after the right pointer steps in from value 4.

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

Expected Output: [0, 1]

Explanation: 2+7=9 at the leftmost two elements.

Input: ([1, 3, 4, 5, 7, 11], 9)

Expected Output: [2, 3]

Explanation: Pointers converge to 4+5=9.

Input: ([-3, 0, 3, 4, 90], 0)

Expected Output: [0, 2]

Explanation: -3+3=0; works with negatives in a sorted array.

Input: ([1, 2, 3], 7)

Expected Output: []

Explanation: No pair reaches 7.

Input: ([], 5)

Expected Output: []

Explanation: Empty input.

Input: ([5], 5)

Expected Output: []

Explanation: Single element cannot pair.

Input: ([1, 1, 1, 1], 2)

Expected Output: [0, 3]

Explanation: With all-equal values the two-pointer meets equality immediately at the outermost indices [0,3].

Input: ([2, 3, 4], 6)

Expected Output: [0, 2]

Explanation: 2+4=6 at the two ends.

Hints

  1. Place one pointer at each end and move them inward based on the comparison of the current sum to target.
  2. Sorted order makes the sum monotone in each move, so a too-small sum means advance the left pointer and a too-large sum means retreat the right pointer.
  3. On the first equality you may return immediately; with duplicate values this gives a valid outermost pair, not necessarily the smallest indices.

Follow-up 4 - Three-sum on a sorted array (unique triplets)

Given an integer array `nums` and an integer `target`, return all UNIQUE triplets `[a, b, c]` (as value triplets, each non-decreasing) such that `a + b + c == target`. No two returned triplets may be the same multiset of values. Return the triplets sorted in ascending order. Approach: sort `nums` (O(n log n)), then fix the first element with an outer loop and solve a two-sum on the remaining suffix with the two-pointer technique (O(n) per fix), giving O(n^2) overall. Deduplicate by skipping equal values for the fixed index and, after recording a hit, skipping equal values for both the left and right pointers. This yields each distinct value-triplet exactly once. Complexity: O(n^2) time, O(1) extra space beyond the sort and output.

Constraints

  • 0 <= len(nums) <= 3000
  • -10^9 <= nums[i], target <= 10^9
  • Triplets are value triplets (multisets), deduplicated
  • Each triplet is returned in non-decreasing order and the overall list is sorted ascending

Examples

Input: ([-1, 0, 1, 2, -1, -4], 0)

Expected Output: [[-1, -1, 2], [-1, 0, 1]]

Explanation: Classic 3-sum=0: the two distinct triplets after dedup of the repeated -1.

Input: ([0, 0, 0, 0], 0)

Expected Output: [[0, 0, 0]]

Explanation: All zeros yield a single deduplicated triplet.

Input: ([1, 2, 3, 4, 5], 9)

Expected Output: [[1, 3, 5], [2, 3, 4]]

Explanation: Two triplets sum to 9.

Input: ([0, 1, 1], 2)

Expected Output: [[0, 1, 1]]

Explanation: 0+1+1=2 is a valid triplet.

Input: ([], 0)

Expected Output: []

Explanation: Empty input.

Input: ([1, 2], 3)

Expected Output: []

Explanation: Fewer than three elements.

Input: ([-2, 0, 1, 1, 2], 0)

Expected Output: [[-2, 0, 2], [-2, 1, 1]]

Explanation: Dedup of the repeated 1 keeps one [-2,1,1].

Input: ([3, 3, 3, 0, 0, 0], 9)

Expected Output: [[3, 3, 3]]

Explanation: Only the three 3s reach 9; deduplicated to one triplet.

Input: ([-4, -2, -1, 0, 1, 2, 3], 0)

Expected Output: [[-4, 1, 3], [-2, -1, 3], [-2, 0, 2], [-1, 0, 1]]

Explanation: Four distinct triplets sum to 0 across negatives and positives.

Hints

  1. Sort first; then fix the smallest element and run a two-pointer two-sum on the remaining suffix.
  2. Skip duplicate values for the fixed index to avoid emitting the same triplet from a different starting position.
  3. After recording a match, advance the left pointer past equal values and retreat the right pointer past equal values to deduplicate.
Last updated: Jun 26, 2026

Loading coding console...

PracHub

Master your tech interviews with 8,000+ real questions from top companies.

Product

  • Questions
  • Learning Tracks
  • Interview Guides
  • Resources
  • Premium
  • For Universities
  • Student Access

Browse

  • By Company
  • By Role
  • By Category
  • Topic Hubs
  • SQL Questions
  • AI Coding Questions
  • Compare Platforms
  • Discord Community

Support

  • support@prachub.com
  • (916) 541-4762

Legal

  • Privacy Policy
  • Terms of Service
  • About Us

© 2026 PracHub. All rights reserved.

Related Coding Questions

  • Implement Top-p (Nucleus) Sampling in NumPy - Amazon (medium)
  • Implement Multi-Head Attention from Scratch in NumPy - Amazon (medium)
  • Detect and Break a Cycle in a Singly Linked List - Amazon (medium)
  • Caesar Cipher with Translation-Table Optimization - Amazon (medium)
  • Minimum Drone Delivery Time on a Ring of Hubs - Amazon (medium)