Two Sum solution and explanation
Google
TCS
Infosys
Deloitte
8 more videos on this problem
Two Sum - Leetcode 1 - HashMap - PythonNeetCode · 8:26 · 2.1M views
LeetCode Two Sum Solution Explained - JavaNick White · 10:31 · 247K views
Python Programming Practice: LeetCode #1 -- Two SumDataDaft · 13:09 · 246K views
LeetCode Exercise in Java Tutorial - Two Sum FAST SolutionCoding with John · 23:36 · 242K views
LeetCode 1: Two Sum | Coding Interview SolutionAbstracted Away · 6:22 · 175K views
Leetcode | 1. Two Sum | Easy | Java SolutionDeveloper Docs · 5:41 · 149K views
Two Sum (LeetCode #1) | 3 Solutions with animations | Study AlgorithmsNikhil Lohia · 17:36 · 125K views
Two Sum - Leetcode 1 - Hashmaps & Sets (Python)Greg Hogg · 4:25 · 66K views
Two Sums Python Solution - LeetCode #1Professor Oakes · 5:29 · 60K views
The problem
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]
Constraints:
2 <= nums.length <= 104-109 <= nums[i] <= 109-109 <= target <= 109- Only one valid answer exists.
O(n2) time complexity?Approach overview
Problem Overview: Given an array of integers nums and a target value, return the indices of the two numbers whose sum equals the target. Each input has exactly one valid pair, and you cannot reuse the same element twice.
Approach 1: Brute Force (O(n^2) time, O(1) space)
The straightforward solution checks every possible pair in the array. Use two nested loops: the outer loop selects the first number, and the inner loop scans the rest of the array to find a number that completes the target sum. For each pair (i, j), check whether nums[i] + nums[j] == target. This approach uses constant extra memory because it only compares values directly. The downside is performance. With n elements, you perform roughly n*(n-1)/2 comparisons, leading to O(n^2) time complexity. Brute force works for small inputs and is often the first step in reasoning about array problems.
Approach 2: Hash Map (O(n) time, O(n) space)
The optimal solution uses a hash table to track previously seen numbers while scanning the array once. For each element nums[i], compute the complement target - nums[i]. If that complement already exists in the hash map, you have found the pair and can return the stored index along with i. If not, store the current value and its index in the map and continue iterating. Hash lookups and insertions run in average O(1) time, so processing the entire array takes O(n). This approach trades memory for speed, storing up to n elements in the map. It’s a classic use of a hash table to convert repeated searches into constant‑time lookups.
The key insight is that instead of searching the array twice for every element, you store previously seen values so the complement check becomes a constant-time operation. This pattern appears in many interview problems where you need fast membership checks inside a single pass.
Recommended for interviews: Interviewers typically expect the hash map solution. Starting with the brute force approach demonstrates you understand the baseline logic and constraints. Moving to the O(n) hash table optimization shows problem‑solving skill and familiarity with common array and lookup patterns. In most real interview settings, candidates who reach the hash map solution quickly and explain the complement logic clearly are demonstrating the intended solution path.
Approach 1: Brute Force Approach
This approach uses a simple brute force algorithm, which consists of checking each pair of numbers to see if they add up to the target. Although this is straightforward, it is not the most efficient method. We loop through each number in the array using two nested loops, effectively trying all combinations of two numbers.
def twoSum(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]
nums = [2, 7, 11, 15]
target = 9
result = twoSum(nums, target)
print(result)import java.util.*;
public class Main {
public static int[] twoSum(int[] nums, int target) {
for (int i = 0; i < nums.length; i++) {
for (int j = i + 1; j < nums.length; j++) {
if (nums[i] + nums[j] == target) {
return new int[] { i, j };
}
}
}
return new int[] {};
}
public static void main(String[] args) {
int[] nums = { 2, 7, 11, 15 };
int target = 9;
int[] result = twoSum(nums, target);
System.out.println("[" + result[0] + ", " + result[1] + "]");
}
}#include <iostream>
#include <vector>
std::vector<int> twoSum(std::vector<int>& nums, int target) {
for (int i = 0; i < nums.size(); ++i) {
for (int j = i + 1; j < nums.size(); ++j) {
if (nums[i] + nums[j] == target) {
return {i, j};
}
}
}
return {};
}
int main() {
std::vector<int> nums = {2, 7, 11, 15};
int target = 9;
std::vector<int> result = twoSum(nums, target);
std::cout << "[" << result[0] << ", " << result[1] << "]" << std::endl;
return 0;
}function twoSum(nums, target) {
for (let i = 0; i < nums.length; i++) {
for (let j = i + 1; j < nums.length; j++) {
if (nums[i] + nums[j] === target) {
return [i, j];
}
}
}
return [];
}
let nums = [2, 7, 11, 15];
let target = 9;
let result = twoSum(nums, target);
console.log(result);#include <stdio.h>
void twoSum(int* nums, int numsSize, int target, int* returnSize) {
*returnSize = 2;
int result[2];
for (int i = 0; i < numsSize; i++) {
for (int j = i + 1; j < numsSize; j++) {
if (nums[i] + nums[j] == target) {
result[0] = i;
result[1] = j;
printf("[%d, %d]\n", result[0], result[1]);
return;
}
}
}
}
int main() {
int nums[] = {2, 7, 11, 15};
int numsSize = sizeof(nums) / sizeof(nums[0]);
int target = 9;
int returnSize;
twoSum(nums, numsSize, target, &returnSize);
return 0;
}using System;
class Program {
static int[] TwoSum(int[] nums, int target) {
for (int i = 0; i < nums.Length; i++) {
for (int j = i + 1; j < nums.Length; j++) {
if (nums[i] + nums[j] == target) {
return new int[] { i, j };
}
}
}
return new int[] {};
}
static void Main() {
int[] nums = { 2, 7, 11, 15 };
int target = 9;
int[] result = TwoSum(nums, target);
Console.WriteLine($"[{result[0]}, {result[1]}]");
}
}The Python solution uses two nested loops to traverse the list. It checks for a pair whose sum equals the target. When such a pair is found, it returns their indices in a list.
Time Complexity: O(n^2)
Space Complexity: O(1)
Approach 2: Hash Map Approach
This efficient approach utilizes a hash map to store the difference between the target and the current element (called 'complement') as the key and the element's index as the value. As we iterate through the array, we check if the current element is a key in the hash map, which indicates that its complement was seen earlier, thus allowing us to retrieve the correct indices quickly.
def twoSum(nums, target):
hashmap = {}
for i, num in enumerate(nums):
complement = target - num
if complement in hashmap:
return [hashmap[complement], i]
hashmap[num] = i
nums = [2, 7, 11, 15]
target = 9
result = twoSum(nums, target)
print(result)import java.util.*;
public class Main {
public static int[] twoSum(int[] nums, int target) {
Map<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
int complement = target - nums[i];
if (map.containsKey(complement)) {
return new int[] { map.get(complement), i };
}
map.put(nums[i], i);
}
return new int[] {};
}
public static void main(String[] args) {
int[] nums = { 2, 7, 11, 15 };
int target = 9;
int[] result = twoSum(nums, target);
System.out.println("[" + result[0] + ", " + result[1] + "]");
}
}#include <iostream>
#include <unordered_map>
#include <vector>
std::vector<int> twoSum(std::vector<int>& nums, int target) {
std::unordered_map<int, int> hashmap;
for (int i = 0; i < nums.size(); i++) {
int complement = target - nums[i];
if (hashmap.find(complement) != hashmap.end()) {
return {hashmap[complement], i};
}
hashmap[nums[i]] = i;
}
return {};
}
int main() {
std::vector<int> nums = {2, 7, 11, 15};
int target = 9;
std::vector<int> result = twoSum(nums, target);
std::cout << "[" << result[0] << ", " << result[1] << "]" << std::endl;
return 0;
}function twoSum(nums, target) {
const hashmap = {};
for (let i = 0; i < nums.length; i++) {
let complement = target - nums[i];
if (hashmap[complement] !== undefined) {
return [hashmap[complement], i];
}
hashmap[nums[i]] = i;
}
return [];
}
let nums = [2, 7, 11, 15];
let target = 9;
let result = twoSum(nums, target);
console.log(result);#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int* twoSum(int* nums, int numsSize, int target, int* returnSize) {
int* result = (int*)malloc(2 * sizeof(int));
int* hashTable = (int*)calloc(10000, sizeof(int)); // Simple hash table
for (int i = 0; i < numsSize; i++) {
int complement = target - nums[i];
if (hashTable[complement] != 0) {
result[0] = hashTable[complement] - 1;
result[1] = i;
*returnSize = 2;
return result;
}
hashTable[nums[i]] = i + 1;
}
*returnSize = 0;
return NULL;
}
int main() {
int nums[] = {2, 7, 11, 15};
int target = 9;
int returnSize;
int* result = twoSum(nums, 4, target, &returnSize);
printf("[%d, %d]\n", result[0], result[1]);
free(result);
return 0;
}using System;
using System.Collections.Generic;
class Program {
static int[] TwoSum(int[] nums, int target) {
Dictionary<int, int> map = new Dictionary<int, int>();
for (int i = 0; i < nums.Length; i++) {
int complement = target - nums[i];
if (map.ContainsKey(complement)) {
return new int[] { map[complement], i };
}
map[nums[i]] = i;
}
return new int[] {};
}
static void Main() {
int[] nums = { 2, 7, 11, 15 };
int target = 9;
int[] result = TwoSum(nums, target);
Console.WriteLine($"[{result[0]}, {result[1]}]");
}
}The Python solution uses a dictionary to store the numbers and their indices. As we iterate through the list, we determine the complement and check if it's already stored in the dictionary. If yes, it is a solution to the problem.
Time Complexity: O(n)
Space Complexity: O(n)
Approach 3: Hash Table
We can use a hash table d to store each element and its corresponding index.
Traverse the array nums, for the current element nums[i], we first check if target - nums[i] is in the hash table d. If it is in d, it means the target value has been found, and we return the indices of target - nums[i] and i.
Time complexity is O(n), and space complexity is O(n), where n is the length of the array nums.
function twoSum(nums: number[], target: number): number[] {
const d = new Map<number, number>();
for (let i = 0; ; ++i) {
const x = nums[i];
const y = target - x;
if (d.has(y)) {
return [d.get(y)!, i];
}
d.set(x, i);
}
}func twoSum(nums []int, target int) []int {
d := map[int]int{}
for i := 0; ; i++ {
x := nums[i]
y := target - x
if j, ok := d[y]; ok {
return []int{j, i}
}
d[x] = i
}
}class Solution {
fun twoSum(nums: IntArray, target: Int): IntArray {
val m = mutableMapOf<Int, Int>()
nums.forEachIndexed { i, x ->
val y = target - x
val j = m.get(y)
if (j != null) {
return intArrayOf(j, i)
}
m[x] = i
}
return intArrayOf()
}
}class Solution {
func twoSum(_ nums: [Int], _ target: Int) -> [Int] {
var d = [Int: Int]()
for (i, x) in nums.enumerated() {
let y = target - x
if let j = d[y] {
return [j, i]
}
d[x] = i
}
return []
}
}use std::collections::HashMap;
impl Solution {
pub fn two_sum(nums: Vec<i32>, target: i32) -> Vec<i32> {
let mut d = HashMap::new();
for (i, &x) in nums.iter().enumerate() {
let y = target - x;
if let Some(&j) = d.get(&y) {
return vec![j as i32, i as i32];
}
d.insert(x, i);
}
vec![]
}
}# @param {Integer[]} nums
# @param {Integer} target
# @return {Integer[]}
def two_sum(nums, target)
d = {}
nums.each_with_index do |x, i|
y = target - x
if d.key?(y)
return [d[y], i]
end
d[x] = i
end
endclass Solution {
/**
* @param Integer[] $nums
* @param Integer $target
* @return Integer[]
*/
function twoSum($nums, $target) {
$d = [];
foreach ($nums as $i => $x) {
$y = $target - $x;
if (isset($d[$y])) {
return [$d[$y], $i];
}
$d[$x] = $i;
}
}
}import scala.collection.mutable
object Solution {
def twoSum(nums: Array[Int], target: Int): Array[Int] = {
val d = mutable.Map[Int, Int]()
var ans: Array[Int] = Array()
for (i <- nums.indices if ans.isEmpty) {
val x = nums(i)
val y = target - x
if (d.contains(y)) {
ans = Array(d(y), i)
} else {
d(x) = i
}
}
ans
}
}import std/enumerate
import std/tables
proc twoSum(nums: seq[int], target: int): seq[int] =
var d = initTable[int, int]()
for i, x in nums.pairs():
let y = target - x
if d.hasKey(y):
return @[d[y], i]
d[x] = i
return @[]class Solution {
func twoSum(nums: Array<Int64>, target: Int64): Array<Int64> {
let d = HashMap<Int64, Int64>()
for (i in 0..nums.size) {
if (d.contains(target - nums[i])) {
return [d[target - nums[i]], i]
}
d[nums[i]] = i
}
[]
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Brute Force Approach | Time Complexity: O(n^2) |
| Hash Map Approach | Time Complexity: O(n) |
| Hash Table | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force (Nested Loops) | O(n^2) | O(1) | Small arrays or when demonstrating the baseline logic before optimizing |
| Hash Map Lookup | O(n) | O(n) | General case; preferred interview solution with fast complement lookup |
Frequently asked questions
Is Two Sum easy or hard?
Two Sum is categorized as an Easy problem. The brute force logic is straightforward, but the key learning objective is recognizing how a hash table reduces the search from O(n^2) to O(n). It is often the first problem used to introduce hash map optimization patterns.
How to solve Two Sum in O(n)?
Use a hash map to store numbers you have already visited along with their indices. While iterating through the array, compute the complement as target minus the current value. If the complement exists in the map, return the stored index and the current index. Each element is processed once, giving O(n) time.
What is the best approach for Two Sum?
The hash map approach is the most efficient solution. Iterate through the array once while storing previously seen numbers in a hash table. For each value, check if its complement (target minus the current number) already exists in the map. This achieves O(n) time complexity with O(n) extra space.
What data structure is used in Two Sum?
The optimal solution relies on a hash table (hash map or dictionary). The structure stores previously seen numbers and allows constant‑time lookups to check whether the complement of the current number already exists.
What is the time complexity of Two Sum?
Time complexity depends on the approach used. The brute force solution checks every pair and runs in O(n^2) time with O(1) space. The optimal hash map approach processes the array once and performs constant‑time lookups, giving O(n) time and O(n) space.
Two Sum Python or Java solution approach?
Both Python and Java typically implement the optimal solution using a hash map. In Python, a dictionary stores number-to-index mappings. In Java, a HashMap<Integer, Integer> performs the same role. The algorithm remains identical and runs in O(n) time.
Is Two Sum asked at Google, Amazon, or Meta?
Two Sum is one of the most common array and hash table interview questions and has appeared in interview preparation sets for companies like Amazon, Meta, and Google. It is often used as a warm‑up problem to test knowledge of hash maps and basic algorithmic thinking.