1. Two Sum

Difficulty: Easy

Topics: Array, Hash Table

Companies: Google, Amazon, Microsoft, Apple, Meta

Problem Statement

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]

Problem Link: View on LeetCode ↗

Approach 1: Brute Force

The simplest approach involves checking every possible pair in the array to see if their sum equals the target.

Algorithm Steps

Iterate through each element in the array
For each element, iterate through the rest of the array
Check if the current element and any subsequent element sum to the target
Return the indices when a valid pair is found

Brute Force Solution

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 {};
    }
};

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[0];
    }
}

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]
        return []

Complexity: O(n²) time, O(1) space

Approach 2: Two-pass Hash Table

This approach reduces the time complexity by using a hash table to store element indices for quick lookups.

Algorithm Steps

Create a hash map to store element-value to index mappings
In the first pass, populate the hash map with all elements
In the second pass, for each element, calculate the complement (target - current element)
Check if the complement exists in the hash map and is not the same element
Return the indices when a valid pair is found

Two-pass Hash Table Solution

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int, int> numMap;
        int n = nums.size();
        
        // Build the hash table
        for (int i = 0; i < n; i++) {
            numMap[nums[i]] = i;
        }
        
        // Find the complement
        for (int i = 0; i < n; i++) {
            int complement = target - nums[i];
            if (numMap.find(complement) != numMap.end() && numMap[complement] != i) {
                return {i, numMap[complement]};
            }
        }
        return {};
    }
};

class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> numMap = new HashMap<>();
        int n = nums.length;
        
        // Build the hash table
        for (int i = 0; i < n; i++) {
            numMap.put(nums[i], i);
        }
        
        // Find the complement
        for (int i = 0; i < n; i++) {
            int complement = target - nums[i];
            if (numMap.containsKey(complement) && numMap.get(complement) != i) {
                return new int[] {i, numMap.get(complement)};
            }
        }
        return new int[0];
    }
}

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        num_map = {}
        n = len(nums)
        
        # Build the hash table
        for i in range(n):
            num_map[nums[i]] = i
            
        # Find the complement
        for i in range(n):
            complement = target - nums[i]
            if complement in num_map and num_map[complement] != i:
                return [i, num_map[complement]]
        return []

Complexity: O(n) time, O(n) space

Approach 3: One-pass Hash Table (Optimal)

The most efficient solution that completes the task in a single pass through the array.

Algorithm Steps

Create a hash map to store element indices
Iterate through the array
For each element, calculate the complement (target - current element)
Check if the complement exists in the hash map
If found, return the indices immediately
Otherwise, add the current element and its index to the map

One-pass Hash Table Solution

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

class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> numMap = new HashMap<>();
        int n = nums.length;
        
        for (int i = 0; i < n; i++) {
            int complement = target - nums[i];
            if (numMap.containsKey(complement)) {
                return new int[] {numMap.get(complement), i};
            }
            numMap.put(nums[i], i);
        }
        return new int[0];
    }
}

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        num_map = {}
        for i, num in enumerate(nums):
            complement = target - num
            if complement in num_map:
                return [num_map[complement], i]
            num_map[num] = i
        return []

Optimal Solution: O(n) time, O(n) space - most efficient for large inputs

Approach Comparison

Approach	Time	Space	Best For
Brute Force	O(n²)	O(1)	Small arrays
Two-pass Hash Table	O(n)	O(n)	Medium arrays
One-pass Hash Table	O(n)	O(n)	All cases (optimal)

Recommendation: One-pass Hash Table is the optimal solution for most cases

Edge Cases

1. Duplicate elements

Input: nums = [3,3], target = 6 → Output: [0,1]

2. Negative numbers

Input: nums = [-1,-2,-3,-4,-5], target = -8 → Output: [2,4]

3. Zero as target

Input: nums = [0,4,3,0], target = 0 → Output: [0,3]

4. Large input size

Input: nums = [1,2,...,10000], target = 19999 → Output: [9999,10000]

Important: Handle duplicate elements carefully to avoid using the same element twice

Frequently Asked Questions

Why is the hash table approach more efficient?

The hash table reduces the time complexity from O(n²) to O(n) by allowing O(1) lookups for complements.

How does the one-pass approach handle duplicates?

Since we check for the complement before adding the current element to the map, we avoid using the same element twice.

What if there are multiple valid answers?

The problem states there's exactly one solution, so we don't need to handle multiple answers.

Can we use a different data structure?

A hash table provides the best average-case performance. Alternatives like balanced BSTs would have O(n log n) time.

How does the solution handle negative numbers?

The algorithm works with negative numbers since complement calculation and hash lookups function the same.

Is the solution order-sensitive?

The order of returned indices doesn't matter, as long as they point to elements that sum to the target.

What happens if no solution is found?

The problem guarantees one solution, but in practice, we return an empty list/array.

Can we solve with constant space?

For unsorted arrays, constant space solutions would require O(n²) time (brute force).

How would you handle sorted input?

For sorted arrays, we could use a two-pointer approach with O(n) time and O(1) space.

Why use unordered_map in C++?

unordered_map provides average O(1) time for operations, while map would be O(log n).

What's the worst-case for the hash table approach?

Worst-case is O(n) per operation (if many collisions), but average case is O(1).

How does Python's dictionary handle collisions?

Python uses open addressing with pseudo-random probing for collision resolution.

Can we optimize for memory?

If memory is critical, the brute force approach uses O(1) space but sacrifices time efficiency.

Final Recommendation: The one-pass hash table solution is optimal for both time and space complexity in real-world scenarios.