Frequently Asked at Google — This problem has been reported multiple times in recent Google L4 interviews.

Two Sum and Its Variants

Problem Statement

You are given three flavors of the Two Sum pattern. Google loves this family because a strong candidate pivots between them fluently.

Variant 1 — Two Sum (LC 1, Easy): Given an unsorted array nums and a target, return the indices of the two numbers that add up to the target. Exactly one solution exists; you cannot reuse an element.

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

Variant 2 — Two Sum II (LC 167, Medium): Same problem but the array is already sorted in non-decreasing order. Return 1-indexed positions.

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

Variant 3 — 3Sum (LC 15, Medium): Return all unique triplets (a, b, c) from nums such that a + b + c == 0.

Input:  nums = [-1, 0, 1, 2, -1, -4]
Output: [[-1, -1, 2], [-1, 0, 1]]

Constraints: 2 <= nums.length <= 10^5, values fit in a 32-bit integer.

Difficulty: Easy / Medium / Medium

Pattern Recognition

Structure of input: array of integers — sometimes sorted, sometimes not.
What are we searching for? pairs or triplets matching a specific sum.
Which pattern fits? Hash map lookup (unsorted), two pointers (sorted), or outer loop + two pointers (triplets).
Why: If the array is sorted, two pointers collapse the search space in O(n). If unsorted, a hash map trades space for time so you avoid the O(n log n) sort. For 3Sum, sorting lets you both dedupe easily and reuse the two-pointer inner loop.

Google grades you on recognizing which variant is in front of you — the same problem family has three fundamentally different correct answers.

Approach

Variant 1 — Unsorted Two Sum

Brute force: Check every pair. O(n^2) time, O(1) space. Fine for tiny inputs, TLE for n = 10^5.

Optimal — Hash Map:

Key Insight: For each number x, the partner you need is target - x. A hash map answers "have I seen the partner?" in O(1).

Walk the array once. Before inserting nums[i], check if target - nums[i] already lives in the map. If yes, return both indices.

Time: O(n) — one pass, O(1) hash operations. Space: O(n) — the hash map.

Variant 2 — Sorted Two Sum (Two Pointers)

Key Insight: Sortedness lets you shrink the window from either end. If the current sum is too small, move left pointer right; if too big, move right pointer left.

Time: O(n). Space: O(1). This variant exists precisely to test whether you exploit sortedness — using a hash map here is a red flag.

Variant 3 — 3Sum

Key Insight: Fix one number, then the problem reduces to Two Sum on a sorted subarray. Sort once up front so dedup is trivial (skip equal neighbors).

For each i, use two pointers on i+1..n-1 to find pairs summing to -nums[i]. Skip duplicates both for i and for the two pointers.

Time: O(n^2) — outer loop times linear inner scan. Space: O(1) beyond the output.

Walkthrough

Take 3Sum on nums = [-1, 0, 1, 2, -1, -4].

Sort: [-4, -1, -1, 0, 1, 2].
i = 0, nums[i] = -4. Need pair summing to 4 from [-1, -1, 0, 1, 2]. left=1, right=5 → -1 + 2 = 1 (too small, left++). 0 + 2 = 2, 1 + 2 = 3. Never reaches 4. No triplet.
i = 1, nums[i] = -1. Need sum 1 from [-1, 0, 1, 2]. left=2, right=5 → -1 + 2 = 1 ✓. Push [-1, -1, 2]. Advance both, skip dupes.
i = 2, nums[i] = -1 — duplicate of previous i, skip.
i = 3, nums[i] = 0. Need sum 0 from [1, 2]. 1 + 2 = 3, too big, right--. Window closes. No triplet — wait, we missed (-1, 0, 1)! Actually we caught it at i=1: left=3 points to 0, right=4 points to 1, 0+1=1 ✓ so we push [-1, 0, 1] too.

Result: [[-1, -1, 2], [-1, 0, 1]].

Implementation

TypeScriptC++

typescript

// Variant 1 — Unsorted Two Sum
function twoSum(nums: number[], target: number): number[] {
    const seen = new Map<number, number>();
    for (let i = 0; i < nums.length; i++) {
        const need = target - nums[i];
        if (seen.has(need)) return [seen.get(need)!, i];
        seen.set(nums[i], i);
    }
    return [];
}

// Variant 2 — Sorted Two Sum (1-indexed result)
function twoSumSorted(numbers: number[], target: number): number[] {
    let left = 0, right = numbers.length - 1;
    while (left < right) {
        const sum = numbers[left] + numbers[right];
        if (sum === target) return [left + 1, right + 1];
        if (sum < target) left++;
        else right--;
    }
    return [];
}

// Variant 3 — 3Sum
function threeSum(nums: number[]): number[][] {
    nums.sort((a, b) => a - b);
    const result: number[][] = [];
    for (let i = 0; i < nums.length - 2; i++) {
        if (nums[i] > 0) break;                     // no triplet possible
        if (i > 0 && nums[i] === nums[i - 1]) continue; // dedupe outer
        let left = i + 1, right = nums.length - 1;
        while (left < right) {
            const sum = nums[i] + nums[left] + nums[right];
            if (sum === 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 (sum < 0) {
                left++;
            } else {
                right--;
            }
        }
    }
    return result;
}

cpp

// Variant 1 — Unsorted Two Sum
vector<int> twoSum(vector<int>& nums, int target) {
    unordered_map<int, int> seen;
    for (int i = 0; i < (int)nums.size(); i++) {
        int need = target - nums[i];
        auto it = seen.find(need);
        if (it != seen.end()) return {it->second, i};
        seen[nums[i]] = i;
    }
    return {};
}

// Variant 2 — Sorted Two Sum
vector<int> twoSumSorted(vector<int>& numbers, int target) {
    int left = 0, right = numbers.size() - 1;
    while (left < right) {
        int sum = numbers[left] + numbers[right];
        if (sum == target) return {left + 1, right + 1};
        if (sum < target) left++;
        else right--;
    }
    return {};
}

// Variant 3 — 3Sum
vector<vector<int>> threeSum(vector<int>& nums) {
    sort(nums.begin(), nums.end());
    vector<vector<int>> result;
    for (int i = 0; i + 2 < (int)nums.size(); i++) {
        if (nums[i] > 0) break;
        if (i > 0 && nums[i] == nums[i - 1]) continue;
        int left = i + 1, right = nums.size() - 1;
        while (left < right) {
            int sum = nums[i] + nums[left] + nums[right];
            if (sum == 0) {
                result.push_back({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 (sum < 0) left++;
            else right--;
        }
    }
    return result;
}

Watch out:
In 3Sum, forgetting the dedupe step on both outer and inner pointers returns duplicate triplets.
On sorted Two Sum, using a hash map "works" but misses the whole point — the interviewer will push you to O(1) space.
In the hash-map version, checking seen.has(nums[i]) before inserting prevents using the same element twice.

Complexity Analysis

	Time	Space
Two Sum brute	O(n^2)	O(1)
Two Sum hash	O(n)	O(n)
Two Sum sorted (two pointers)	O(n)	O(1)
3Sum	O(n^2)	O(1) or O(n) from sort

Bottleneck: Two Sum is bound by needing to look at every element. 3Sum is bound by the O(n^2) pair enumeration — sorting is strictly cheaper at O(n log n).

Edge Cases

Empty or length-1 array — 3Sum should return []; Two Sum variants have no answer.
All zeros for 3Sum — exactly one triplet [0,0,0]; dedup must not drop it.
Duplicates around the target — e.g., nums = [3, 3], target = 6. Hash map must insert after checking to handle this correctly.
Negative targets — the hash-map method handles them naturally; make sure you do not assume positive values.
Integer overflow on sum — in C++ use long long or reorder comparisons when values approach INT_MAX (Google interviewers love asking this).
Array of length 2 in 3Sum — loop guard i < n - 2 protects you.

LC 18 — 4Sum — Extends the pattern: sort, fix two, two pointers. O(n^3).
LC 259 — 3Sum Smaller — Count triplets with sum strictly less than target; same two-pointer skeleton, different accounting.
LC 170 — Two Sum III (data structure) — Design version that supports add and find; pushes you to pick between read-optimized and write-optimized hash maps.
LC 454 — 4Sum II — Split into two halves and hash, O(n^2). Good follow-up on trading time for space.

What Is Expected at Each Level

Junior: Solve LC 1 with the hash-map approach, state complexity correctly, handle the duplicate-key edge case.

Mid-level: Write all three variants cleanly, explain why the sorted version should not use a hash map, dedupe 3Sum without prompting, and recognize the nums[i] > 0 early exit.

Senior (L4 target): Discuss the space–time tradeoff explicitly, generalize to kSum recursively, note the O(n^2) lower bound for 3Sum under 3SUM-hardness, and connect it to problems like 4Sum II. Expect to write production-grade code: meaningful names, guard clauses, no mutation of input unless allowed.

Two Sum and Its Variants ​

Problem Statement ​

Pattern Recognition ​

Approach ​

Variant 1 — Unsorted Two Sum ​

Variant 2 — Sorted Two Sum (Two Pointers) ​

Variant 3 — 3Sum ​

Walkthrough ​

Implementation ​

Complexity Analysis ​

Edge Cases ​

Related Problems ​

What Is Expected at Each Level ​