.png)
Two Sum Problem
Problem Statement
Given an array of integers and a target value, find two distinct elements in the array such that their sum equals the given target.
You need to return:
- The indices of the two elements
OR - The elements themselves, depending on the problem statement
In most interview problems, indices are required.
Example 1
Input
arr = [2, 7, 11, 15]
target = 9
Output
Indices: [0, 1]
Explanation
arr[0] + arr[1] = 2 + 7 = 9
Example 2
Input
arr = [3, 2, 4]
target = 6
Output
Indices: [1, 2]
Why This Problem Is Important
The Two Sum problem is a classic interview question because it:
- Tests understanding of arrays and hashing
- Introduces time–space tradeoff
- Is often the first step toward:
- 3 Sum
- 4 Sum
- Subarray sum problems
- Appears frequently in:
- Coding interviews
- Online assessments
- Competitive programming
Approaches to Solve the Problem
- Brute Force Approach
- Hashing (Optimized & Most Used)
- Two Pointer Approach (For Sorted Arrays)
Approach 1: Brute Force Method
Idea
- Check all possible pairs
- If the sum of any pair equals the target, return their indices
Algorithm
- Use two nested loops
- Pick first element at index i
- Pick second element at index j (i + 1)
- If arr[i] + arr[j] == target, return indices
Time and Space Complexity
- Time Complexity: O(n²)
- Space Complexity: O(1)
All Implementations
C Implementation
#include<stdio.h>
int main() {
int arr[] = {2, 7, 11, 15};
int target = 9;
int n = 4;
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
if (arr[i] + arr[j] == target) {
printf("Indices: %d %d", i, j);
return 0;
}
}
}
return 0;
}
Output
Indices: 0 1
C++ Implementation
#include<iostream>
using namespace std;
int main() {
int arr[] = {2, 7, 11, 15};
int target = 9;
int n = 4;
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
if (arr[i] + arr[j] == target) {
cout << "Indices: " << i << " " << j;
return 0;
}
}
}
return 0;
}
Output
Indices: 0 1
Java Implementation
public class TwoSumBrute {
public static void main(String[] args) {
int[] arr = {2, 7, 11, 15};
int target = 9;
for (int i = 0; i < arr.length; i++) {
for (int j = i + 1; j < arr.length; j++) {
if (arr[i] + arr[j] == target) {
System.out.println("Indices: " + i + " " + j);
return;
}
}
}
}
}
Output
Indices: 0 1
Python Implementation
arr = [2, 7, 11, 15]
target = 9
for i in range(len(arr)):
for j in range(i + 1, len(arr)):
if arr[i] + arr[j] == target:
print("Indices:", i, j)
break
Output
Indices: 0 1
JavaScript Implementation
let arr = [2, 7, 11, 15];
let target = 9;
for (let i = 0; i < arr.length; i++) {
for (let j = i + 1; j < arr.length; j++) {
if (arr[i] + arr[j] === target) {
console.log("Indices:", i, j);
break;
}
}
}
Output
Indices: 0 1
![Solved] How to find all pairs which add up to a given value in an Integer Array in Java? Example | Java67](https://blogger.googleusercontent.com/img/a/AVvXsEjSxSZPeUblMKuSXUbJYzk5zLH1SPMUTxlQvnvP71OLs9LjZz7chv-bY0wp5FQSN_dy6oJXVOwI5UJTpqxUJZXAlhLyqi4cnMtNF42EU1FbGWrytKBpH2o18spbiKy9SZmqfRMSGgcGbD9amedUjwx_bfvtxkAWf2EGrCdUfaYra_8k3unru9YUDkex=w506-h297)
Approach 2: Using Hashing (Best Approach)
Idea
- Store elements and their indices in a hash map
- For each element:
- Calculate remaining = target - currentElement
- If remaining exists in the map, solution is found
Algorithm
- Create an empty hash map
- Traverse the array
- For each element:
- Compute remaining = target - arr[i]
- If remaining exists in map:
- Return indices
- Else store current element with index in map
Time and Space Complexity
- Time Complexity: O(n)
- Space Complexity: O(n)
C++ Implementation
#include<iostream>
#include<unordered_map>
using namespace std;
int main() {
int arr[] = {2, 7, 11, 15};
int target = 9;
unordered_map<int,int> mp;
for(int i = 0; i < 4; i++) {
int rem = target - arr[i];
if(mp.find(rem) != mp.end()) {
cout << "Indices: " << mp[rem] << " " << i;
return 0;
}
mp[arr[i]] = i;
}
return 0;
}
Output
Indices: 0 1
Java Implementation
import java.util.*;
public class TwoSum {
public static void main(String[] args) {
int[] arr = {2, 7, 11, 15};
int target = 9;
Map<Integer,Integer> map = new HashMap<>();
for(int i = 0; i < arr.length; i++) {
int rem = target - arr[i];
if(map.containsKey(rem)) {
System.out.println("Indices: " + map.get(rem) + " " + i);
return;
}
map.put(arr[i], i);
}
}
}
Output
Indices: 0 1
Python Implementation
arr = [2, 7, 11, 15]
target = 9
mp = {}
for i, num in enumerate(arr):
rem = target - num
if rem in mp:
print("Indices:", mp[rem], i)
break
mp[num] = i
Output
Indices: 0 1
JavaScript Implementation
let arr = [2, 7, 11, 15];
let target = 9;
let map = new Map();
for (let i = 0; i < arr.length; i++) {
let rem = target - arr[i];
if (map.has(rem)) {
console.log("Indices:", map.get(rem), i);
break;
}
map.set(arr[i], i);
}
Output
Indices: 0 1
Approach 3: Two Pointer Method (Sorted Array)
Idea
- Sort the array
- Use two pointers:
- One at the beginning
- One at the end
- Move pointers based on sum comparison
Time and Space Complexity
- Time Complexity: O(n log n)
- Space Complexity: O(1)
Note: This approach does not preserve original indices unless extra tracking is done.
C Implementation
#include<stdio.h>
int main() {
int arr[] = {2, 7, 11, 15};
int target = 9;
int n = 4;
// simple sort
for (int i = 0; i < n - 1; i++) {
for (int j = i + 1; j < n; j++) {
if (arr[i] > arr[j]) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
}
int left = 0, right = n - 1;
while (left < right) {
int sum = arr[left] + arr[right];
if (sum == target) {
printf("Elements: %d %d", arr[left], arr[right]);
return 0;
} else if (sum < target) {
left++;
} else {
right--;
}
}
return 0;
}
Output
Elements: 2 7
C++ Implementation
#include<iostream>
#include <algorithm>
using namespace std;
int main() {
int arr[] = {2, 7, 11, 15};
int target = 9;
int n = 4;
sort(arr, arr + n);
int left = 0, right = n - 1;
while (left < right) {
int sum = arr[left] + arr[right];
if (sum == target) {
cout << "Elements: " << arr[left] << " " << arr[right];
return 0;
} else if (sum < target) {
left++;
} else {
right--;
}
}
return 0;
}
Output
Elements: 2 7
Java Implementation
import java.util.Arrays;
public class TwoSumTwoPointer {
public static void main(String[] args) {
int[] arr = {2, 7, 11, 15};
int target = 9;
Arrays.sort(arr);
int left = 0, right = arr.length - 1;
while (left < right) {
int sum = arr[left] + arr[right];
if (sum == target) {
System.out.println("Elements: " + arr[left] + " " + arr[right]);
return;
} else if (sum < target) {
left++;
} else {
right--;
}
}
}
}
Output
Elements: 2 7
Python Implementation
arr = [2, 7, 11, 15]
target = 9
arr.sort()
left, right = 0, len(arr) - 1
while left < right:
s = arr[left] + arr[right]
if s == target:
print("Elements:", arr[left], arr[right])
break
elif s < target:
left += 1
else:
right -= 1
Output
Elements: 2 7
JavaScript Implementation
let arr = [2, 7, 11, 15];
let target = 9;
arr.sort((a, b) => a - b);
let left = 0, right = arr.length - 1;
while (left < right) {
let sum = arr[left] + arr[right];
if (sum === target) {
console.log("Elements:", arr[left], arr[right]);
break;
} else if (sum < target) {
left++;
} else {
right--;
}
}
Output
Elements: 2 7
Dry Run (Hashing Approach)
arr = [2, 7, 11, 15], target = 9
i = 0 → num = 2 → remaining = 7 → not found → store {2:0}
i = 1 → num = 7 → remaining = 2 → found → answer [0,1]
Summary
- Two Sum is a fundamental array + hashing problem
- Hashing provides the best and fastest solution
- Brute force helps understand the logic
- ..Forms the base for many advanced problems
Key Takeaways
- Best Time Complexity: O(n)
- Space Complexity: O(n)
- Hash map is the optimal choice
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
