Solving the Two-Sum Problem: A Comprehensive Guide

Introduction

In this post, we will dive into the Two-Sum problem, a widely known algorithmic challenge often featured in coding interviews. The problem has two main variants, each presenting a unique twist. Let’s walk through both, explore various solutions, and learn how to solve them efficiently.

Two-Sum Problem Variants

Variant 1: Finding a Pair That Adds Up to the Target

In the first variation, you're given an array and a target number, and your goal is to determine whether any two distinct numbers from the array sum up to the target.

Example:
Let’s consider the following array and target:

arr = [2, 6, 5, 8, 11]
target = 14

The task is to find two numbers from the array that add up to 14. In this case, 6 and 8 are the pair that sums up to 14.

Approach:

• If a pair is found, return True.
• If no such pair exists, return False.

This variant tests whether a pair exists that satisfies the condition.

You can try out this problem using the following link.

Variant 2: Returning Indices of the Pair

In the second variant, you're given an array and a target number, but this time, your task is to return the indices of the two numbers that add up to the target.

Example:
Given the same array and target:

arr = [2, 6, 5, 8, 11]
target = 14

The output should return the indices of 6 and 8 because their sum is 14. The result will be the indices [1, 3] as arr[1] = 6 and arr[3] = 8.

You can try this problem using the following link.

Approaches to Solve the Two-Sum Problem

1. Brute Force Approach

The most straightforward way to solve the problem is through a brute force approach. This method involves iterating over all pairs of numbers in the array and checking if their sum matches the target.

Steps:

1. Loop through each element in the array.
2. For each element, loop through all subsequent elements.
3. Check if the sum of the two numbers equals the target.
4. If a pair is found, return the indices or True (depending on the problem variant).
5. If no pair is found after all iterations, return False (for Variant 1) or an empty result (for Variant 2).

Code Implementation:

Brute Force Approach - O(n^2) time complexity

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

Complexity Analysis:

Time Complexity: O(n²), due to the nested loops.

Space Complexity: O(1), since no additional space is used.

Two-Pointers Approach for Variant 1

Another efficient approach for Variant 1 is the two-pointers technique. This approach works only if the array is sorted.

Steps:

1. Sort the array (if not already sorted).

2. Initialize two pointers:

   • One at the start (left pointer)
   • One at the end (right pointer)

3. While left < right:

   • Compute sum = arr[left] + arr[right].
   • If sum == target, return True.
   • If sum < target, move the left pointer forward.
   • If sum > target, move the right pointer backward.
   • If no pair is found, return False.

Code Implementation:

Two-Pointers Approach - O(n log n) time complexity (due to sorting)

def two_sum_sorted(arr, target):
    arr.sort()  # Ensure array is sorted
    left, right = 0, len(arr) - 1

    while left < right:
        current_sum = arr[left] + arr[right]
        if current_sum == target:
            return True
        elif current_sum < target:
            left += 1
        else:
            right -= 1

    return False

Complexity Analysis:

• Time Complexity: O(n log n) due to sorting, but O(n) for the two-pointer search.

• Space Complexity: O(1), as no additional space is used.

2. Optimized Approach Using a Hash Map

A more efficient solution uses a hash map to store the numbers we've already seen while iterating through the array. This allows us to check if the complement (the difference between the target and the current number) exists in constant time.

Steps:

1. Initialize an empty hash map.
2. Iterate through the array:
3. Compute the complement: complement = target - current_number.
4. Check if the complement is already in the hash map.
5. If it is, return the indices of the current element and the complement.
6. Otherwise, add the current element to the hash map with its index.
7. If no pair is found after iterating through the entire array, return an empty result.

Complexity Analysis:

• Time Complexity: O(n), since we only traverse the array once, and hash map operations are O(1) on average.

• Space Complexity: O(n), as we store elements in a hash map.

C++ Implementation of the Optimized Approach

For those who prefer C++, here’s the optimized solution:

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

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

JavaScript Implementation of the Optimized Approach

For JavaScript developers, here's the optimized solution:

function twoSum(nums, target) {
    let mapper = new Map();
    for (let i = 0; i < nums.length; i++) {
        let complement = target - nums[i];
        if (mapper.has(complement)) {
            return [mapper.get(complement), i];
        }
        mapper.set(nums[i], i);
    }
    return [];
}

Ruby Implementation of the Optimized Approach

For Ruby developers, here's the optimized solution:

def two_sum(nums, target)
    mapper = {}
    nums.each_with_index do |num, i|
        complement = target - num
        return [mapper[complement], i] if mapper.key?(complement)
        mapper[num] = i
    end
    []
end

Python Implementation of the Optimized Approach

The Python solution is as follows:

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

Conclusion

Brute Force Approach: Simple but inefficient with a time complexity of O(n²). It works well for small arrays but is slow for larger inputs.

Optimized Approach with Hash Map: Improves the time complexity to O(n), making it the preferred solution for large arrays. It leverages a hash map for constant-time lookups and inserts.

The Two-Sum problem is a great example of how hash maps can optimize solutions for problems involving searching and pairing. Whether you're tackling this problem in an interview or learning algorithms, understanding time and space complexities helps in selecting the best approach.

Feel free to explore the problem further or try it yourself using the links provided:

Variant 1: Simple Two-Sum Problem

Variant 2: Two-Sum Problem with Indices

Good luck, Happy Coding!