Amazon — Two Sum and Variants (HashMap, Two Pointers, 3Sum, 4Sum)

Problem Statement#

Given an integer array nums and a target integer target, return indices of the two numbers that add up to target. Exactly one valid answer exists.

Constraints:

• 2 <= nums.length <= 10^4
• -10^9 <= nums[i] <= 10^9
• -10^9 <= target <= 10^9
• Exactly one solution exists

Input:  nums = [2, 7, 11, 15], target = 9
Output: [0, 1]

Input:  nums = [3, 2, 4], target = 6
Output: [1, 2]

Why This Problem Matters#

Two Sum (LeetCode 1) is LeetCode's most-solved problem and Amazon's most-used screening question. It is the entry point to an entire family of complement-search problems. Amazon uses Two Sum to quickly filter for candidates who understand hash lookups vs brute-force search, and then escalates to 3Sum, 4Sum, or "Two Sum in a BST" to test generalization.

The O(N^2) brute force checks every pair. The O(N) hashmap stores each element's index as you scan; for each element, check whether its complement (target - current) already exists in the map. This one-pass approach demonstrates the "complement lookup" mental model that extends directly to 3Sum (fix one element, two-pointer the rest) and 4Sum (fix two elements).

Every major tech company — Meta, Google, Apple, Microsoft — asks Two Sum or a variant. Mastering the hashmap approach and the two-pointer approach (for sorted arrays) is mandatory for any coding interview.

The Core Insight#

Two Sum (unsorted, find indices): Use a hashmap mapping value to index. For each element, check if target - element is in the map. If yes, return both indices. Otherwise, add current element to the map.

Two Sum II (sorted, find values): Use two pointers at both ends. If their sum equals target, return. If sum is too small, advance left pointer. If sum is too large, retreat right pointer.

3Sum: Fix one element, then run Two Sum II on the remaining sorted array. Skip duplicates to avoid repeated results.

4Sum: Fix two elements, then run Two Sum II (or 3Sum logic). Skip duplicates at each level.

Visual Dry Run#

Two Sum: nums=[2,7,11,15], target=9

Solution (Optimal)#

class Solution:
    # Two Sum — O(N) hashmap
    def twoSum(self, nums: list, target: int) -> list:
        seen = {}
        for i, num in enumerate(nums):
            complement = target - num
            if complement in seen:
                return [seen[complement], i]
            seen[num] = i
        return []
 
    # Two Sum II (sorted) — O(N) two pointers
    def twoSumSorted(self, numbers: list, target: int) -> list:
        left, right = 0, len(numbers) - 1
        while left < right:
            s = numbers[left] + numbers[right]
            if s == target:
                return [left + 1, right + 1]
            elif s < target:
                left += 1
            else:
                right -= 1
        return []
 
    # 3Sum — O(N^2) sort + two pointers
    def threeSum(self, nums: list) -> list:
        nums.sort()
        result = []
        for i in range(len(nums) - 2):
            if i > 0 and nums[i] == nums[i - 1]:
                continue
            left, right = i + 1, len(nums) - 1
            while left < right:
                s = nums[i] + nums[left] + nums[right]
                if s == 0:
                    result.append([nums[i], nums[left], nums[right]])
                    while left < right and nums[left] == nums[left + 1]:
                        left += 1
                    while left < right and nums[right] == nums[right - 1]:
                        right -= 1
                    left += 1
                    right -= 1
                elif s < 0:
                    left += 1
                else:
                    right -= 1
        return result

// Two Sum — O(N) hashmap
var twoSum = function(nums, target) {
    const seen = new Map();
    for (let i = 0; i < nums.length; i++) {
        const complement = target - nums[i];
        if (seen.has(complement)) return [seen.get(complement), i];
        seen.set(nums[i], i);
    }
    return [];
};
 
// 3Sum — O(N^2) sort + two pointers
var threeSum = function(nums) {
    nums.sort((a, b) => a - b);
    const result = [];
    for (let i = 0; i < nums.length - 2; i++) {
        if (i > 0 && nums[i] === nums[i-1]) continue;
        let left = i + 1, right = nums.length - 1;
        while (left < right) {
            const s = nums[i] + nums[left] + nums[right];
            if (s === 0) {
                result.push([nums[i], nums[left], nums[right]]);
                while (left < right && nums[left] === nums[left+1]) left++;
                while (left < right && nums[right] === nums[right-1]) right--;
                left++; right--;
            } else if (s < 0) left++;
            else right--;
        }
    }
    return result;
};

Time: O(N) for Two Sum; O(N^2) for 3Sum/4Sum Space: O(N) for hashmap; O(1) additional for two pointers (not counting output)

Common Mistakes#

• Returning [i, i] when an element equals half of target — element cannot pair with itself
• Not skipping duplicates in 3Sum — results in duplicate triplets
• Off-by-one: skipping duplicate check at nums[left] == nums[left+1] instead of after recording
• Using Two Sum (unsorted) approach on sorted Two Sum II — O(N) hashmap is correct but two pointers is expected
• Sorting a mutable reference for 3Sum then expecting original indices — 3Sum asks for values, not indices

Interview Tips#

• For basic Two Sum, code the hashmap version — O(N) and one pass
• For sorted arrays, always mention two pointers — shows awareness of the sorted property
• 3Sum: sort first, fix one element, two-pointer the rest; skip duplicates at each level
• 4Sum: same pattern as 3Sum with one extra loop; O(N^3) which is acceptable
• Amazon often asks "what if multiple solutions exist?" — return all of them or the first one

Follow-up Questions#

• How do you solve Two Sum if duplicates exist and you want all pairs? — HashSet of complements
• How do you solve Two Sum in a BST? — In-order traversal to sorted list, then two pointers
• What if the array is too large for memory? — External sort + two pointers from file
• How do you find the closest pair sum to target? — Two pointers, track minimum difference
• How do you extend 3Sum to k-Sum? — Recursively reduce: fix one element, recurse on (k-1)-Sum

Key Takeaways#

• Two Sum with hashmap is O(N) one-pass: look up complement before inserting current element
• Two Sum II (sorted) uses two pointers: advance left if sum is small, retreat right if sum is large
• 3Sum sorts then fixes one element and two-pointers the rest: O(N^2) with duplicate skipping
• Duplicate skipping in 3Sum is mandatory: skip at the outer loop and inner pointer after recording
• Amazon tests Two Sum first, then escalates to 3Sum or variants — prepare the full family
• The complement-lookup pattern (check if target - x exists) is the universal Two Sum mental model
• 4Sum applies the same pattern one level deeper: fix two elements, two-pointer the remaining sorted subarray