Two Sum

🎯

Two Sum

easyHASH_MAPAmazonGoogleFacebook

Imagine you are shopping and want to find two items that exactly match your gift card balance. How do you quickly find those two items?

💡 This problem is about finding pairs in a list that sum to a target. Beginners often struggle because they try inefficient methods or don't leverage hash maps for quick lookups.

📋

Problem Statement

Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target. You may assume that each input would have exactly one solution, and you may not use the same element twice. You can return the answer in any order.

1 ≤ nums.length ≤ 10^5-10^9 ≤ nums[i] ≤ 10^9-10^9 ≤ target ≤ 10^9Exactly one valid answer exists

💡

Example

Input"nums = [2,7,11,15], target = 9"

Output[0,1]

nums[0] + nums[1] = 2 + 7 = 9

Input"nums = [3,2,4], target = 6"

Output[1,2]

nums[1] + nums[2] = 2 + 4 = 6

• Array with only two elements → returns [0,1]
• Negative numbers included → works correctly
• Target is zero and array contains zero and another number → finds correct pair
• Multiple pairs possible but only one valid answer guaranteed → returns that one

⚠️

Common Mistakes

Checking pairs with same index twice

Returns invalid pair or duplicates

✅ Ensure inner loop starts from i+1 or check complement index != current index

Not handling negative numbers or zero correctly

Misses valid pairs or crashes

✅ No special fix needed, just test with negatives and zero

Using list.index() inside loop (Python) causing O(n^2)

Slower than expected, TLE on large inputs

✅ Use hash map for O(1) lookups

Returning values instead of indices

Fails problem requirement, wrong output

✅ Return indices as per problem statement

Not returning immediately after finding pair

May return wrong or multiple answers

✅ Return as soon as valid pair found

🧠

Brute Force (Nested Loops)

💡 Starting with brute force helps understand the problem deeply by checking all pairs, even though it's inefficient.

Intuition

Check every pair of numbers to see if they sum to the target. This guarantees finding the answer but is slow.

Algorithm

1. Iterate over each element in the array with index i.
2. For each i, iterate over the elements after i with index j.
3. Check if nums[i] + nums[j] equals the target.
4. If yes, return the indices [i, j].

💡 The double loop is easy to understand but can be hard to optimize without a better insight.

</>

Code

from typing import List

def two_sum(nums: List[int], target: int) -> List[int]:
    n = len(nums)
    for i in range(n):
        for j in range(i + 1, n):
            if nums[i] + nums[j] == target:
                return [i, j]

# Driver code
if __name__ == '__main__':
    print(two_sum([2,7,11,15], 9))  # Output: [0, 1]

Line Notes

for i in range(n):Outer loop picks the first element to pair

for j in range(i + 1, n):Inner loop picks the second element after i to avoid repeats

if nums[i] + nums[j] == target:Check if current pair sums to target

return [i, j]Return indices immediately when pair found

import java.util.*;

public class TwoSum {
    public static int[] twoSum(int[] nums, int target) {
        int n = nums.length;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if (nums[i] + nums[j] == target) {
                    return new int[]{i, j};
                }
            }
        }
        return new int[0]; // no solution
    }

    public static void main(String[] args) {
        int[] result = twoSum(new int[]{2,7,11,15}, 9);
        System.out.println(Arrays.toString(result)); // [0, 1]
    }
}

Line Notes

for (int i = 0; i < n; i++) {Outer loop selects first number

for (int j = i + 1; j < n; j++) {Inner loop selects second number after i

if (nums[i] + nums[j] == target) {Check if sum matches target

return new int[]{i, j};Return indices immediately when found

#include <iostream>
#include <vector>
using namespace std;

vector<int> twoSum(vector<int>& nums, int target) {
    int n = nums.size();
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            if (nums[i] + nums[j] == target) {
                return {i, j};
            }
        }
    }
    return {};
}

int main() {
    vector<int> nums = {2,7,11,15};
    vector<int> res = twoSum(nums, 9);
    cout << "[" << res[0] << ", " << res[1] << "]" << endl; // [0, 1]
    return 0;
}

Line Notes

for (int i = 0; i < n; i++) {Outer loop picks first element

for (int j = i + 1; j < n; j++) {Inner loop picks second element after i

if (nums[i] + nums[j] == target) {Check if sum equals target

return {i, j};Return indices immediately when found

function twoSum(nums, target) {
    const n = nums.length;
    for (let i = 0; i < n; i++) {
        for (let j = i + 1; j < n; j++) {
            if (nums[i] + nums[j] === target) {
                return [i, j];
            }
        }
    }
    return [];
}

// Test
console.log(twoSum([2,7,11,15], 9)); // [0, 1]

Line Notes

for (let i = 0; i < n; i++) {Outer loop selects first number

for (let j = i + 1; j < n; j++) {Inner loop selects second number after i

if (nums[i] + nums[j] === target) {Check if sum matches target

return [i, j];Return indices immediately when found

⏱

Complexity

TimeO(n^2)

SpaceO(1)

Two nested loops each can run up to n times, so n*n = n^2 operations

💡 For n=20, this means 400 checks, which is okay, but for n=100000, 10 billion checks is too slow.

Interview Verdict: Use only to introduce - too slow for large inputs

This approach is simple but inefficient; interviewers expect you to improve it.

🧠

Using Hash Map for Complement Lookup

💡 This approach uses a hash map to store seen numbers and their indices, enabling quick complement checks.

Intuition

For each number, check if its complement (target - number) exists in the map. If yes, return indices; else add the number to the map.

Algorithm

1. Create an empty hash map to store number → index.
2. Iterate over the array with index i.
3. Calculate complement = target - nums[i].
4. If complement is in the map, return [map[complement], i].
5. Otherwise, add nums[i] with index i to the map.

💡 The key insight is to check complements on the fly, avoiding repeated pair checks.

</>

Code

from typing import List

def two_sum(nums: List[int], target: int) -> List[int]:
    seen = {}
    for i, num in enumerate(nums):
        complement = target - num
        if complement in seen:
            return [seen[complement], i]
        seen[num] = i

# Driver code
if __name__ == '__main__':
    print(two_sum([2,7,11,15], 9))  # Output: [0, 1]

Line Notes

seen = {}Initialize empty dictionary to store seen numbers and their indices

for i, num in enumerate(nums):Iterate over array with index and value

complement = target - numCalculate the needed complement to reach target

if complement in seen:Check if complement was seen before to form a pair

seen[num] = iAdd current number and index to map for future complements

import java.util.*;

public class TwoSum {
    public static int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> seen = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            int complement = target - nums[i];
            if (seen.containsKey(complement)) {
                return new int[]{seen.get(complement), i};
            }
            seen.put(nums[i], i);
        }
        return new int[0];
    }

    public static void main(String[] args) {
        int[] result = twoSum(new int[]{2,7,11,15}, 9);
        System.out.println(Arrays.toString(result)); // [0, 1]
    }
}

Line Notes

Map<Integer, Integer> seen = new HashMap<>();Create map to store number → index

for (int i = 0; i < nums.length; i++) {Iterate over array indices

int complement = target - nums[i];Calculate complement needed

if (seen.containsKey(complement)) {Check if complement exists in map

seen.put(nums[i], i);Add current number and index to map

#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;

vector<int> twoSum(vector<int>& nums, int target) {
    unordered_map<int, int> seen;
    for (int i = 0; i < nums.size(); i++) {
        int complement = target - nums[i];
        if (seen.find(complement) != seen.end()) {
            return {seen[complement], i};
        }
        seen[nums[i]] = i;
    }
    return {};
}

int main() {
    vector<int> nums = {2,7,11,15};
    vector<int> res = twoSum(nums, 9);
    cout << "[" << res[0] << ", " << res[1] << "]" << endl; // [0, 1]
    return 0;
}

Line Notes

unordered_map<int, int> seen;Hash map to store number → index for O(1) lookup

for (int i = 0; i < nums.size(); i++) {Iterate over array indices

int complement = target - nums[i];Calculate complement needed to reach target

if (seen.find(complement) != seen.end()) {Check if complement exists in map

seen[nums[i]] = i;Add current number and index to map

function twoSum(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 [];
}

// Test
console.log(twoSum([2,7,11,15], 9)); // [0, 1]

Line Notes

const seen = new Map();Initialize map for number → index storage

for (let i = 0; i < nums.length; i++) {Iterate over array indices

const complement = target - nums[i];Calculate complement needed

if (seen.has(complement)) {Check if complement exists in map

seen.set(nums[i], i);Add current number and index to map

⏱

Complexity

TimeO(n)

SpaceO(n)

Single pass through array with O(1) average lookup in hash map, total O(n)

💡 For n=100000, this means about 100000 operations, which is efficient and fast.

Interview Verdict: Accepted - optimal time complexity for this problem

This is the standard solution interviewers expect for Two Sum.

🧠

Sorting + Two Pointers (Not Applicable Here)

💡 Sorting and two pointers is a common approach for sum problems but not suitable here because we must return original indices.

Intuition

Sort the array and use two pointers from start and end to find the sum, but sorting changes indices.

Algorithm

1. Copy and sort the array while keeping track of original indices.
2. Use two pointers at start and end to find two numbers summing to target.
3. Return the original indices of these two numbers.

💡 This approach requires extra bookkeeping and is less efficient due to sorting.

</>

Code

from typing import List

def two_sum(nums: List[int], target: int) -> List[int]:
    nums_with_index = list(enumerate(nums))
    nums_with_index.sort(key=lambda x: x[1])
    left, right = 0, len(nums) - 1
    while left < right:
        current_sum = nums_with_index[left][1] + nums_with_index[right][1]
        if current_sum == target:
            return [nums_with_index[left][0], nums_with_index[right][0]]
        elif current_sum < target:
            left += 1
        else:
            right -= 1

# Driver code
if __name__ == '__main__':
    print(two_sum([2,7,11,15], 9))  # Output: [0, 1]

Line Notes

nums_with_index = list(enumerate(nums))Pair each number with its original index

nums_with_index.sort(key=lambda x: x[1])Sort pairs by number value

while left < right:Two pointers to find sum

return [nums_with_index[left][0], nums_with_index[right][0]]Return original indices when sum found

import java.util.*;

public class TwoSum {
    public static int[] twoSum(int[] nums, int target) {
        int n = nums.length;
        int[][] numsWithIndex = new int[n][2];
        for (int i = 0; i < n; i++) {
            numsWithIndex[i][0] = i;
            numsWithIndex[i][1] = nums[i];
        }
        Arrays.sort(numsWithIndex, Comparator.comparingInt(a -> a[1]));
        int left = 0, right = n - 1;
        while (left < right) {
            int sum = numsWithIndex[left][1] + numsWithIndex[right][1];
            if (sum == target) {
                return new int[]{numsWithIndex[left][0], numsWithIndex[right][0]};
            } else if (sum < target) {
                left++;
            } else {
                right--;
            }
        }
        return new int[0];
    }

    public static void main(String[] args) {
        int[] result = twoSum(new int[]{2,7,11,15}, 9);
        System.out.println(Arrays.toString(result)); // [0, 1]
    }
}

Line Notes

int[][] numsWithIndex = new int[n][2];Store pairs of index and value

Arrays.sort(numsWithIndex, Comparator.comparingInt(a -> a[1]));Sort by value

while (left < right) {Two pointers to find sum

return new int[]{numsWithIndex[left][0], numsWithIndex[right][0]};Return original indices

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

vector<int> twoSum(vector<int>& nums, int target) {
    int n = nums.size();
    vector<pair<int,int>> numsWithIndex;
    for (int i = 0; i < n; i++) {
        numsWithIndex.push_back({i, nums[i]});
    }
    sort(numsWithIndex.begin(), numsWithIndex.end(), [](const pair<int,int>& a, const pair<int,int>& b) {
        return a.second < b.second;
    });
    int left = 0, right = n - 1;
    while (left < right) {
        int sum = numsWithIndex[left].second + numsWithIndex[right].second;
        if (sum == target) {
            return {numsWithIndex[left].first, numsWithIndex[right].first};
        } else if (sum < target) {
            left++;
        } else {
            right--;
        }
    }
    return {};
}

int main() {
    vector<int> nums = {2,7,11,15};
    vector<int> res = twoSum(nums, 9);
    cout << "[" << res[0] << ", " << res[1] << "]" << endl; // [0, 1]
    return 0;
}

Line Notes

vector<pair<int,int>> numsWithIndex;Store pairs of original index and value

sort(numsWithIndex.begin(), numsWithIndex.end(), [](const pair<int,int>& a, const pair<int,int>& b) {Sort pairs by value using custom comparator

while (left < right) {Two pointers to find sum

return {numsWithIndex[left].first, numsWithIndex[right].first};Return original indices

function twoSum(nums, target) {
    const numsWithIndex = nums.map((num, idx) => [num, idx]);
    numsWithIndex.sort((a, b) => a[0] - b[0]);
    let left = 0, right = nums.length - 1;
    while (left < right) {
        const sum = numsWithIndex[left][0] + numsWithIndex[right][0];
        if (sum === target) {
            return [numsWithIndex[left][1], numsWithIndex[right][1]];
        } else if (sum < target) {
            left++;
        } else {
            right--;
        }
    }
    return [];
}

// Test
console.log(twoSum([2,7,11,15], 9)); // [0, 1]

Line Notes

const numsWithIndex = nums.map((num, idx) => [num, idx]);Pair each number with original index

numsWithIndex.sort((a, b) => a[0] - b[0]);Sort pairs by number value

while (left < right) {Two pointers to find sum

return [numsWithIndex[left][1], numsWithIndex[right][1]];Return original indices when sum found

⏱

Complexity

TimeO(n log n)

SpaceO(n)

Sorting takes O(n log n), two pointers scan in O(n), total O(n log n)

💡 For n=100000, sorting is slower than hash map approach but still acceptable.

Interview Verdict: Accepted but not preferred due to sorting overhead and complexity

Good to mention to show knowledge but hash map is better here.

📊

All Approaches - One-Glance Tradeoffs

💡 Use the hash map approach in 95% of interviews for best balance of speed and simplicity.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	O(n^2)	O(1)	No	N/A	Mention only - never code for large inputs
2. Hash Map Complement Lookup	O(n)	O(n)	No	N/A	Code this approach for optimal solution
3. Sorting + Two Pointers	O(n log n)	O(n)	No	N/A	Mention as alternative, explain why less suitable

💼

Interview Strategy

💡 Use this guide to understand the problem deeply, practice all approaches, and prepare to explain tradeoffs clearly.

How to Present

Step 1: Clarify problem constraints and assumptions.Step 2: Present brute force approach and analyze complexity.Step 3: Introduce hash map approach for optimization.Step 4: Mention sorting + two pointers and why it's less suitable.Step 5: Code the hash map approach carefully.Step 6: Test with edge cases and explain your reasoning.

Time Allocation

Clarify: 2min → Approach: 3min → Code: 8min → Test: 2min. Total ~15min

What the Interviewer Tests

Ability to optimize from brute force, use hash maps correctly, handle edge cases, and communicate clearly.

Common Follow-ups

• What if the array is sorted? → Use two pointers approach.
• What if multiple pairs exist? → Return any one valid pair.
• What if no pair exists? → Return empty or error.
• Can you do it in one pass? → Yes, hash map approach is single pass.

💡 These follow-ups test your adaptability and deeper understanding of the problem.

🔍

Pattern Recognition

When to Use

1) Need to find pairs with a sum or complement 2) Array or list input 3) Return indices or positions 4) Exactly one solution guaranteed

Signature Phrases

two numbers add up to targetreturn indices of the two numbers

NOT This Pattern When

Problems asking for subsets or combinations without fixed pair size are different patterns.

Similar Problems

3Sum - find triplets summing to zero, extends Two Sum logic4Sum - find quadruplets summing to target, builds on Two SumTwo Sum II - Input array is sorted - uses two pointers instead of hash map

Practice

1. Consider the following Python code for grouping anagrams. What is the value of anagram_map after processing the input ["eat", "tea", "bat"]?

easy

A. [["eat", "tea"], ["bat"]]

B. [["eat"], ["tea"], ["bat"]]

C. [["eat", "bat"], ["tea"]]

D. [["bat", "tea"], ["eat"]]

Solution

1. Step 1: Trace first string "eat"

   Count array increments for 'e', 'a', 't'. Key tuple created and "eat" added to anagram_map[key].

2. Step 2: Trace second string "tea"

   Count array matches "eat"'s key, so "tea" appended to same list.

3. Step 3: Trace third string "bat"

   Count array differs, new key created, "bat" added to new list.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   "eat" and "tea" grouped, "bat" separate [OK]

Hint: Anagrams share identical frequency count keys [OK]

Common Mistakes:

• Confusing keys causing separate groups
• Appending to wrong list
• Off-by-one in count array

2. You are given two strings s and t. You need to determine if there exists a one-to-one character mapping from s to t such that replacing characters in s with their mapped characters produces t. Which algorithmic approach guarantees an optimal solution for this problem?

easy

A. Dynamic programming to track substring isomorphisms

B. Greedy approach that maps characters as they appear without checking reverse mapping

C. Bidirectional hash map mapping that ensures one-to-one character correspondence

D. Brute force nested loops checking all character pairs for consistency

Solution

1. Step 1: Understand the problem constraints

   The problem requires a one-to-one mapping between characters of two strings, ensuring no two characters in s map to the same character in t and vice versa.

2. Step 2: Identify the approach that enforces bidirectional mapping

   Only the bidirectional hash map approach maintains two maps: one from s to t and another from t to s, ensuring the mapping is consistent and one-to-one.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Bidirectional mapping prevents false positives like mapping "ab" to "aa" [OK]

Hint: One-to-one mapping requires bidirectional checks [OK]

Common Mistakes:

• Assuming single-direction mapping suffices
• Using DP which is unnecessary
• Relying on greedy without reverse check

3. Consider the following Python code implementing the optimal bucket sort approach for top K frequent elements. What is the value of res just before the function returns when called with nums = [1,2,2,3] and k = 2?

easy

A. [1, 2]

B. [2, 1]

C. [2, 3]

D. [3, 2]

Solution

1. Step 1: Calculate frequency map for nums=[1,2,2,3]

   freq = {1:1, 2:2, 3:1}, max_freq = 2

2. Step 2: Fill buckets and collect top k=2 elements

   buckets = [[], [1,3], [2]]; iterate from freq=2 down: add 2, then freq=1 add 1; res = [2,1]

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Order depends on bucket insertion; here 2 appears before 1 [OK]

Hint: Trace buckets from highest frequency down [OK]

Common Mistakes:

• Confusing order of elements in buckets
• Assuming sorted order inside buckets
• Off-by-one in frequency indexing

4. The following code attempts to detect a continuous subarray sum divisible by k. Which line contains a subtle bug that can cause incorrect results on some inputs?

medium

A. Line 7: normalizing k if negative

B. Line 9: computing total modulo k without handling negative values

C. Line 3: initializing remainder_map with {0: -1}

D. Line 12: checking if subarray length > 1

Solution

1. Step 1: Identify modulo operation on line 9

   The code uses total = total % k without adjusting for negative totals, which can yield negative remainders.

2. Step 2: Understand impact of negative remainders

   Negative remainders cause incorrect remainder_map keys, missing valid subarrays.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Modulo must be normalized to non-negative remainder [OK]

Hint: Modulo with negatives must be normalized to positive remainder [OK]

Common Mistakes:

• Not normalizing modulo results for negative sums
• Overwriting remainder_map entries instead of preserving earliest index
• Allowing subarrays of length 1 to return True

5. What is the time complexity of the optimal character frequency counting approach for grouping anagrams, given n strings each of length k?

medium

A. O(n * k log k)

B. O(n^2 * k log k)

C. O(n * k)

D. O(n * k^2)

Solution

1. Step 1: Identify loops in the algorithm

   Outer loop runs n times, inner loop counts characters in each string of length k.

2. Step 2: Analyze operations inside loops

   Counting frequency is O(k), creating tuple key is O(26) constant, appending to map is O(1).

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Overall complexity is O(n * k) [OK]

Hint: Frequency counting is linear in string length [OK]

Common Mistakes:

• Confusing sorting cost with counting
• Assuming k log k due to sorting
• Mistaking quadratic complexity