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

1. Brute Force Approach
2. Hashing (Optimized & Most Used)
3. 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

1. Use two nested loops
2. Pick first element at index i
3. Pick second element at index j (i + 1)
4. 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

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

1. Create an empty hash map
2. Traverse the array
3. 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

Next Problem in the Series

Subarray with Given Sum