Two Sum - Leetcode Solution

Problem Link

Step-by-Step Thought Process

Brute Force

Understand the problem: Find two numbers in an array that sum to a target value and return their indices.
Get the length n of the input array nums.
Iterate through each index i from 0 to n-1 using a loop.
For each i, iterate through each index j from i+1 to n-1 using a nested loop.
Check if nums[i] + nums[j] equals the target.
If true, return a tuple or list containing indices i and j.

Code Solution (Brute Force)

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        n = len(nums)
        for i in range(n):
            for j in range(i+1, n):
                if nums[i] + nums[j] == target:
                    return (i, j)
    # Time: O(n^2)
    # Space: O(1)

#include <vector>
using namespace std;

class Solution {
public:
    vector<int> twoSum(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 {}; // If no solution found
    }
};
// Time: O(n^2)
// Space: O(1)

class Solution {
    public int[] twoSum(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[] {}; // If no solution found
    }
}
// Time: O(n^2)
// Space: O(1)

var twoSum = function(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 []; // If no solution found
};
// Time: O(n^2)
// Space: O(1)

Why the Brute-Force Solution is Inefficient

The brute-force solution checks every possible pair of numbers, leading to:

Time Complexity: O(n²), where n is the length of the array, due to nested loops iterating over all pairs.
Space Complexity: O(1), as only a constant amount of extra space is used.
Performance Issue: The quadratic time complexity makes it slow for large arrays, as it doesn't leverage any data structures to reduce the number of comparisons.

Optimal Solution

The optimal solution uses a hash map to achieve O(n) time complexity:

Initialize an empty hash map to store numbers and their indices.
Iterate through the array with index i from 0 to length-1.
For each number nums[i], compute the complement y as target minus nums[i].
Check if y exists in the hash map and its index is not i.
If found, return a list containing i and the index of y from the hash map.
Otherwise, add nums[i] and its index i to the hash map.

Code Solution (Optimal)

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        h = {}
        for i in range(len(nums)):
            h[nums[i]] = i

        for i in range(len(nums)):
            y = target - nums[i]

            if y in h and h[y] != i:
                return [i, h[y]]
# Time Complexity: O(n)
# Space Complexity: O(n)

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

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int, int> h;
        for (int i = 0; i < nums.size(); ++i) {
            h[nums[i]] = i;
        }

        for (int i = 0; i < nums.size(); ++i) {
            int y = target - nums[i];
            if (h.find(y) != h.end() && h[y] != i) {
                return {i, h[y]};
            }
        }

        throw invalid_argument("No two sum solution");
    }
};

import java.util.HashMap;
import java.util.Map;

public class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> h = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            h.put(nums[i], i);
        }

        for (int i = 0; i < nums.length; i++) {
            int y = target - nums[i];
            if (h.containsKey(y) && h.get(y) != i) {
                return new int[] {i, h.get(y)};
            }
        }

        throw new IllegalArgumentException("No two sum solution");
    }
}

var twoSum = function(nums, target) {
    const h = new Map();
    for (let i = 0; i < nums.length; i++) {
        h.set(nums[i], i);
    }

    for (let i = 0; i < nums.length; i++) {
        const y = target - nums[i];
        if (h.has(y) && h.get(y) !== i) {
            return [i, h.get(y)];
        }
    }

    throw new Error("No two sum solution");
};

Detailed Explanation

Understanding the Problem: Two Sum

The “Two Sum” problem is one of the most well-known algorithmic challenges. Given an array of integers nums and an integer target, the task is to find the indices of two distinct numbers in nums such that they add up to target.

For example:

nums = [2, 7, 11, 15], target = 9 → Output: [0, 1] because 2 + 7 = 9.
nums = [3, 2, 4], target = 6 → Output: [1, 2]

Why This Problem Matters

Two Sum introduces fundamental concepts in problem solving: iteration, complement computation, and the power of hash maps for constant-time lookup. It also forms the basis for more complex variations like Three Sum, Four Sum, and problems involving pairs with constraints.

Brute Force Approach

The most straightforward solution is to use two nested loops to check every pair of numbers. For each element nums[i], we scan the remaining elements to find if any nums[j] satisfies nums[i] + nums[j] == target.

While easy to implement, this method performs poorly on large arrays due to its quadratic time complexity.

Brute Force Steps:

Loop i from 0 to n - 1.
Loop j from i + 1 to n - 1.
If nums[i] + nums[j] == target, return [i, j].
If no such pair is found, return an empty list or null.

Optimal Solution: Hash Map for Complements

A more efficient solution uses a hash map to store previously seen numbers and their indices. As we iterate through the array, we calculate the complement target - nums[i] and check if it's already in the map. If it is, we return the current index and the stored index of the complement.

Hash Map Steps:

Initialize an empty map seen = {}.
Loop over the array with index i and value num.
Compute complement = target - num.
If complement exists in seen, return [seen[complement], i].
Otherwise, store seen[num] = i.

Example Walkthrough

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

i = 0, num = 3 → complement = 3 → not in seen → store {3: 0}
i = 1, num = 2 → complement = 4 → not in seen → store {2: 1}
i = 2, num = 4 → complement = 2 → 2 is in seen → return [1, 2]

Time and Space Complexity

Time Complexity: O(n), where n is the length of the array. We loop through the array once, and hash map lookups and inserts are constant time.
Space Complexity: O(n), for storing up to n elements in the map.

Edge Cases to Consider

Exactly two numbers → trivial case
Multiple valid pairs → usually return the first one found
No valid pair → return [] or throw an error depending on the implementation
Negative numbers and zero → ensure complements are correctly computed

Conclusion

The “Two Sum” problem is a great introduction to using hash maps to speed up lookups and eliminate redundant comparisons. Understanding this approach is key to tackling more advanced problems involving combinations, subsets, or real-time aggregation.

Get Personalized Support at AlgoMap Bootcamp 💡