Two Sum

Problem Statement

Given an array of integers nums and an integer target, return the indices of the two numbers such that they add up to target.

You may assume that each input has exactly one solution, and you may not use the same element twice. You can return the answer in any order.

What to notice first

• The answer must return indices, not the values themselves.
• You are guaranteed exactly one valid pair, so you can stop as soon as you find it.
• The fastest common solution uses a hash map to remember what you have already seen.

Examples

Input	Target	Output	Explanation
[2, 7, 11, 15]	9	[0, 1]	nums[0] + nums[1] = 2 + 7 = 9
[3, 2, 4]	6	[1, 2]	nums[1] + nums[2] = 2 + 4 = 6
[3, 3]	6	[0, 1]	nums[0] + nums[1] = 3 + 3 = 6

Constraints

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

Real-World Applications

Where this pattern appears

• Cache lookup / request deduplication — given a list of request sizes, find two that together fill a fixed-size buffer exactly.
• Financial balance validation — check whether two transactions cancel each other out (sum to zero) during reconciliation.
• Network packet pairing — pair incoming and outgoing packets whose sizes sum to a known MTU boundary.
• Two-player game scoring — determine whether any two remaining moves together hit a target score.

Complexity Comparison

Approach	Time	Space	Returns	Best When
Brute Force	O(n²)	O(1)	Indices	Array is tiny, no extra memory allowed
Hash Map	O(n)	O(n)	Indices	General case — fast lookup, unsorted input
Two-Pointer	O(n log n)	O(n)*	Values	Array is already sorted or indices not required

* A sorted copy of the array is made to preserve the original order.

Which approach should you learn first?

• Pick Hash Map if you want the best all-around interview answer.
• Pick Brute Force if you are still learning how to reason about pairs.
• Pick Two-Pointer only if you are practicing the pattern or if the data is already sorted.

Best For Speed

Hash Map

O(n) time · O(n) space

Sorted Input

Two-Pointer

O(n log n) time · O(n) space

No Extra Memory

Brute Force

O(n²) time · O(1) space

Approach 1: Hash Map (Recommended)

★ Recommended

For each number, compute its complement (target - num) and check if that complement was already seen. Store each number → index mapping as we iterate.

The key idea is simple: instead of searching the whole array again, remember each number as you go. When the matching partner appears later, you can answer immediately.

⏱ Time O(n) Single pass 💾 Space O(n) Hash map storage

Step-by-step Example

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

Step	i	num	complement	seen (before)	Action
1	0	2	7	{}	7 not in seen → store {2: 0}
2	1	7	2	{2: 0}	2 found at index 0 → return [0, 1] ✓

Animated walkthrough

How the hash map solution finds the answer

Use Next or Autoplay to watch the current index, the complement calculation, and the lookup table change after each step.

Back Autoplay Next Reset

Step 1 of 3 Target: 9

Waiting to begin...

Array state

Memory / lookup state

Pseudocode

function twoSumHashMap(nums, target):
    seen = {}
    for i, num in enumerate(nums):
        complement = target - num
        if complement in seen:
            return [seen[complement], i]
        seen[num] = i

Solution Code

Python

two_sum_hash_map.py

from typing import List


def two_sum_hash_map(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
    return []

print(two_sum_hash_map([2, 7, 11, 15], target=9))  # [0, 1]

C++

two_sum_hash_map.cpp

#include <iostream>
#include <vector>
#include <unordered_map>

std::vector<int> twoSumHashMap(std::vector<int>& nums, int target) {
    std::unordered_map<int, int> seen;
    for (int i = 0; i < (int)nums.size(); i++) {
        int complement = target - nums[i];
        if (seen.count(complement)) {
            return {seen[complement], i};
        }
        seen[nums[i]] = i;
    }
    return {};
}

int main() {
    std::vector<int> nums = {2, 7, 11, 15};
    int target = 9;
    std::vector<int> result = twoSumHashMap(nums, target);
    for (int num : result) {
        std::cout << num << " ";
    }
    std::cout << std::endl;
    return 0;
}

Java

two_sum_hash_map.java

import java.util.Arrays;
import java.util.HashMap;

public class Main {
    public static int[] twoSumHashMap(int[] nums, int target) {
        HashMap<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[]{};
    }

    public static void main(String[] args) {
        int[] nums = {2, 7, 11, 15};
        int target = 9;
        int[] result = twoSumHashMap(nums, target);
        System.out.println(Arrays.toString(result));
    }
}

JavaScript

two_sum_hash_map.js

function twoSumHashMap(nums, target) {
    const seen = {};
    for (let i = 0; i < nums.length; i++) {
        const complement = target - nums[i];
        if (complement in seen) {
            return [seen[complement], i];
        }
        seen[nums[i]] = i;
    }
    return [];
}

const nums = [2, 7, 11, 15];
const target = 9;
const result = twoSumHashMap(nums, target);
console.log(result);

Rust

two_sum_hash_map.rs

use std::collections::HashMap;

fn two_sum_hash_map(nums: &[i32], target: i32) -> Vec<usize> {
    let mut seen: HashMap<i32, usize> = HashMap::new();
    for (i, &num) in nums.iter().enumerate() {
        let complement = target - num;
        if let Some(&j) = seen.get(&complement) {
            return vec![j, i];
        }
        seen.insert(num, i);
    }
    vec![]
}

fn main() {
    let nums = vec![2, 7, 11, 15];
    let target = 9;
    let result = two_sum_hash_map(&nums, target);
    println!("{:?}", result);
}

Go

two_sum_hash_map.go

package main

import "fmt"

func twoSumHashMap(nums []int, target int) []int {
  seen := make(map[int]int)
  for i, num := range nums {
    complement := target - num
    if j, ok := seen[complement]; ok {
      return []int{j, i}
    }
    seen[num] = i
  }
  return []int{}
}

func main() {
  nums := []int{2, 7, 11, 15}
  target := 9
  result := twoSumHashMap(nums, target)
  fmt.Println(result)
}

Approach 2: Two-Pointer

🎯 Interview Favourite

Sort the numbers, place one pointer at the beginning and one at the end, then adjust them based on whether the current sum is too small or too large.

Returns values, not indices

Sorting destroys original index positions. This approach returns the pair values. Use the Hash Map approach when the original indices are required.

⏱ Time O(n log n) Sort-dominated 💾 Space O(n) Sorted copy

Step-by-step Example

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

After sorting: [2, 3, 4]

Step	left	right	sorted[left]	sorted[right]	Sum	Action
1	0	2	2	4	6	== target → return [2, 4] ✓

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

After sorting: [2, 7, 11, 15]

Step	left	right	sorted[left]	sorted[right]	Sum	Action
1	0	3	2	15	17	> target → right—
2	0	2	2	11	13	> target → right—
3	0	1	2	7	9	== target → return [2, 7] ✓

Pseudocode

function twoSumTwoPointer(nums, target):
    sorted = sort(copy of nums)
    left, right = 0, len(sorted) - 1
    while left < right:
        currentSum = sorted[left] + sorted[right]
        if currentSum == target:
            return [sorted[left], sorted[right]]
        elif currentSum < target:
            left++
        else:
            right--
    return []

Solution Code

Python

two_sum_two_pointer.py

from typing import List


def two_sum_two_pointer(nums: List[int], target: int) -> List[int]:
    nums_sorted = sorted(nums)
    left, right = 0, len(nums_sorted) - 1
    while left < right:
        current_sum = nums_sorted[left] + nums_sorted[right]
        if current_sum == target:
            return [nums_sorted[left], nums_sorted[right]]
        elif current_sum < target:
            left += 1
        else:
            right -= 1
    return []

print(two_sum_two_pointer([2, 7, 11, 15], target=9))   # [2, 7]
print(two_sum_two_pointer([3, 2, 4], target=6))         # [2, 4]
print(two_sum_two_pointer([3, 3], target=6))            # [3, 3]

C++

two_sum_two_pointer.cpp

#include <iostream>
#include <vector>
#include <algorithm>

std::vector<int> twoSumTwoPointer(std::vector<int> nums, int target) {
    std::sort(nums.begin(), nums.end());
    int left = 0, right = (int)nums.size() - 1;
    while (left < right) {
        int currentSum = nums[left] + nums[right];
        if (currentSum == target) {
            return {nums[left], nums[right]};
        } else if (currentSum < target) {
            left++;
        } else {
            right--;
        }
    }
    return {};
}

int main() {
    std::vector<int> nums = {2, 7, 11, 15};
    int target = 9;
    std::vector<int> result = twoSumTwoPointer(nums, target);
    for (int num : result) {
        std::cout << num << " ";
    }
    std::cout << std::endl;
    return 0;
}

Java

two_sum_two_pointer.java

import java.util.Arrays;

public class Main {
    public static int[] twoSumTwoPointer(int[] nums, int target) {
        int[] sorted = nums.clone();
        Arrays.sort(sorted);
        int left = 0, right = sorted.length - 1;
        while (left < right) {
            int currentSum = sorted[left] + sorted[right];
            if (currentSum == target) {
                return new int[]{sorted[left], sorted[right]};
            } else if (currentSum < target) {
                left++;
            } else {
                right--;
            }
        }
        return new int[]{};
    }

    public static void main(String[] args) {
        int[] nums = {2, 7, 11, 15};
        int target = 9;
        int[] result = twoSumTwoPointer(nums, target);
        System.out.println(Arrays.toString(result));
    }
}

JavaScript

two_sum_two_pointer.js

function twoSumTwoPointer(nums, target) {
    const sorted = [...nums].sort((a, b) => a - b);
    let left = 0, right = sorted.length - 1;
    while (left < right) {
        const currentSum = sorted[left] + sorted[right];
        if (currentSum === target) {
            return [sorted[left], sorted[right]];
        } else if (currentSum < target) {
            left++;
        } else {
            right--;
        }
    }
    return [];
}

const nums = [2, 7, 11, 15];
const target = 9;
const result = twoSumTwoPointer(nums, target);
console.log(result);

Rust

two_sum_two_pointer.rs

fn two_sum_two_pointer(nums: &[i32], target: i32) -> Vec<i32> {
    let mut sorted = nums.to_vec();
    sorted.sort();
    let (mut left, mut right) = (0, sorted.len() - 1);
    while left < right {
        let current_sum = sorted[left] + sorted[right];
        if current_sum == target {
            return vec![sorted[left], sorted[right]];
        } else if current_sum < target {
            left += 1;
        } else {
            right -= 1;
        }
    }
    vec![]
}

fn main() {
    let nums = vec![2, 7, 11, 15];
    let target = 9;
    let result = two_sum_two_pointer(&nums, target);
    println!("{:?}", result);
}

Go

two_sum_two_pointer.go

package main

import (
  "fmt"
  "sort"
)

func twoSumTwoPointer(nums []int, target int) []int {
  sorted := make([]int, len(nums))
  copy(sorted, nums)
  sort.Ints(sorted)
  left, right := 0, len(sorted)-1
  for left < right {
    currentSum := sorted[left] + sorted[right]
    if currentSum == target {
      return []int{sorted[left], sorted[right]}
    } else if currentSum < target {
      left++
    } else {
      right--
    }
  }
  return []int{}
}

func main() {
  nums := []int{2, 7, 11, 15}
  target := 9
  result := twoSumTwoPointer(nums, target)
  fmt.Println(result)
}

Approach 3: Brute Force

✓ Simple

Check every possible pair using two nested loops.

This is the most direct approach. It is slow for large inputs, but it is a good mental starting point because there is almost no trick to it.

⏱ Time O(n²) All pairs checked 💾 Space O(1) No extra memory

Step-by-step Example

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

i	j	nums[i]	nums[j]	Sum	Match?
0	1	2	7	9	✓ → return [0, 1]

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

i	j	nums[i]	nums[j]	Sum	Match?
0	1	3	2	5	✗
0	2	3	4	7	✗
1	2	2	4	6	✓ → return [1, 2]

Pseudocode

function twoSumBruteForce(nums, target):
    for i in range(len(nums)):
        for j in range(i + 1, len(nums)):
            if nums[i] + nums[j] == target:
                return [i, j]

Solution Code

Python

two_sum_brute_force.py

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



Example 1:

Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].
Example 2:

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

Input: nums = [3,3], target = 6
Output: [0,1]
"""


# Approach 1: Brute Force
# This approach involves using two nested loops to iterate through every possible pair of numbers in the array and checking if their sum equals the target.

# Time Complexity: O(n^2)
from typing import List

def two_sum_brute_force(nums, target):
    for i in range(len(nums)):
        for j in range(i + 1, len(nums)):
            if nums[i] + nums[j] == target:
                return [i, j]

print(two_sum_brute_force([2,7,11,15], target = 9))  # [0, 1]

C++

two_sum_brute_force.cpp

#include <iostream>
#include <vector>

std::vector<int> twoSumBruteForce(std::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 {}; // Return an empty vector if no valid pair is found
}

int main() {
    std::vector<int> nums = {2, 7, 11, 15};
    int target = 9;
    std::vector<int> result = twoSumBruteForce(nums, target);
    for (int num : result) {
        std::cout << num << " ";
    }
    std::cout << std::endl;
    return 0;
}

Java

two_sum_brute_force.java

import java.util.Arrays;

public class Main {
    public static int[] twoSumBruteForce(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[] {}; // Return an empty array if no valid pair is found
    }

    public static void main(String[] args) {
        int[] nums = {2, 7, 11, 15};
        int target = 9;
        int[] result = twoSumBruteForce(nums, target);
        System.out.println(Arrays.toString(result));
    }
}

JavaScript

two_sum_brute_force.js

function twoSumBruteForce(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 []; // Return an empty array if no valid pair is found
}

const nums = [2, 7, 11, 15];
const target = 9;
const result = twoSumBruteForce(nums, target);
console.log(result);

Rust

two_sum_brute_force.rs

fn two_sum_brute_force(nums: &[i32], target: i32) -> Vec<usize> {
    let n = nums.len();
    for i in 0..n {
        for j in (i + 1)..n {
            if nums[i] + nums[j] == target {
                return vec![i, j];
            }
        }
    }
    vec![] // Return an empty vector if no valid pair is found
}

fn main() {
    let nums = vec![2, 7, 11, 15];
    let target = 9;
    let result = two_sum_brute_force(&nums, target);
    println!("{:?}", result);
}

Go

two_sum_brute_force.go

package main

import "fmt"

func twoSumBruteForce(nums []int, target int) []int {
    n := len(nums)
    for i := 0; i < n; i++ {
        for j := i + 1; j < n; j++ {
            if nums[i]+nums[j] == target {
                return []int{i, j}
            }
        }
    }
    return []int{} // Return an empty slice if no valid pair is found
}

func main() {
    nums := []int{2, 7, 11, 15}
    target := 9
    result := twoSumBruteForce(nums, target)
    fmt.Println(result)
}

Common mistakes

Watch for these pitfalls

• Returning the numbers instead of their indices in the hash map solution.
• Reusing the same element twice when the complement equals the current number.
• Forgetting that the two-pointer version here returns values after sorting, not original indices.

Related Problems

• Contains Duplicate ↗ Easy #217
• Two Sum II - Input Array Is Sorted ↗ Medium #167
• 3Sum ↗ Medium #15
• Palindrome Number ↗ Easy #9

Interview Tips

Key trade-offs to discuss

• Why hash map over brute force? Trading O(n) space to drop from O(n²) to O(n) time. Almost always the right call unless memory is severely constrained.
• Why not two-pointer for the standard problem? It loses original indices. An interviewer asking for indices is a deliberate signal to use a hash map.
• Edge cases to mention: negative numbers (all three approaches handle them), duplicate values like [3, 3] (hash map handles this because we check before inserting), and the constraint guarantees exactly one solution.
• Follow-up — Three Sum: The two-pointer technique extends naturally to three numbers in O(n²).

Next
#9 Palindrome Number →