The Two Sum problem is a common interview question that tests your understanding of algorithms and data structures. The goal is simple: given an array of integers and a target value, find two numbers that add up to the target and return their indices.

In this post, we will walk through how to solve the Two Sum problem in C++, starting from a brute force solution and then moving to a more optimized approach using a hash map (unordered map). We will also cover the time and space complexities of each approach.

Problem Statement

Given an array of integers nums and an integer target, return the indices of the two numbers such that they add up to the target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

Example:

Input: nums = [2, 7, 11, 15], target = 9
Output: [0, 1]
Explanation: Because nums[0] + nums[1] = 2 + 7 = 9.

Approach 1: Brute Force Solution

The brute-force approach checks all possible pairs in the array to see if their sum equals the target. This method is straightforward but inefficient for large arrays.

Algorithm:

  1. Use two nested loops.
  2. For each element nums[i], iterate through the array with another element nums[j] where j > i.
  3. Check if nums[i] + nums[j] equals the target.
  4. If the sum matches the target, return their indices.

Code:

#include <iostream>
#include <vector>

std::vector<int> twoSum(const std::vector<int>& nums, int target) {
    for (int i = 0; i < nums.size(); i++) {
        for (int j = i + 1; j < nums.size(); j++) {
            if (nums[i] + nums[j] == target) {
                return {i, j};  // Return the indices as a vector
            }
        }
    }
    return {};  // Return an empty vector if no solution is found
}

int main() {
    std::vector<int> nums = {2, 7, 11, 15};
    int target = 9;

    std::vector<int> result = twoSum(nums, target);
    if (!result.empty()) {
        std::cout << "Indices: [" << result[0] << ", " << result[1] << "]\n";
    } else {
        std::cout << "No solution found\n";
    }
    return 0;
}

Explanation:

  • We use two nested loops to find all pairs of numbers.
  • If the sum of two numbers equals the target, their indices are returned.

Time Complexity:

  • O(n²): We check each pair of elements, resulting in quadratic time complexity.
  • Space Complexity: O(1) because no additional space is used apart from the input.

Approach 2: Optimized Solution Using Hash Map (Unordered Map)

The brute-force approach can be optimized using a hash map (unordered map in C++). The idea is to use the hash map to store each element's complement (target - nums[i]) as we iterate through the array. If we find a number that matches the complement already in the map, we have found the solution.

Algorithm:

  1. Create an unordered map to store the value of the number and its index.
  2. Loop through the array:
    • Calculate the complement (target - nums[i]).
    • Check if the complement is in the map.
    • If it is, return the current index and the stored index from the map.
    • If not, add the current number and its index to the map.

Code:

#include <iostream>
#include <unordered_map>
#include <vector>

std::vector<int> twoSum(const std::vector<int>& nums, int target) {
    std::unordered_map<int, int> numMap;  // Create a hash map to store numbers and their indices
    
    for (int i = 0; i < nums.size(); i++) {
        int complement = target - nums[i];  // Calculate the complement
        
        if (numMap.find(complement) != numMap.end()) {  // If complement is found in the map
            return {numMap[complement], i};  // Return the indices
        }
        
        numMap[nums[i]] = i;  // Add the number and its index to the map
    }
    
    return {};  // Return an empty vector if no solution is found
}

int main() {
    std::vector<int> nums = {2, 7, 11, 15};
    int target = 9;

    std::vector<int> result = twoSum(nums, target);
    if (!result.empty()) {
        std::cout << "Indices: [" << result[0] << ", " << result[1] << "]\n";
    } else {
        std::cout << "No solution found\n";
    }
    return 0;
}

Explanation:

  • We loop through the array, calculating the complement for each number.
  • We use an unordered map (numMap) to store the indices of numbers we’ve seen so far.
  • If the complement is already in the map, we return the current index and the index of the complement.

Time Complexity:

  • O(n): We loop through the array once, and each lookup in the map takes constant time.
  • Space Complexity: O(n) because we store up to n elements in the map.

Edge Cases

While the problem guarantees exactly one solution, you should still account for various edge cases during implementation:

  1. Negative and Positive Numbers:
    The array may contain both negative and positive numbers. Ensure that the solution works for both.

    std::vector<int> nums = {-3, 4, 3, 90};
int target = 0;
std::vector<int> result = twoSum(nums, target);
std::cout << result[0] << ", " << result[1] << std::endl;  // Output: 0, 2

  2. Duplicate Values:
    The array may contain duplicate values, and the solution should still return the correct indices.

    std::vector<int> nums = {3, 3};
int target = 6;
std::vector<int> result = twoSum(nums, target);
std::cout << result[0] << ", " << result[1] << std::endl;  // Output: 0, 1

  3. Array with Only Two Elements:
    Since the problem guarantees at least two elements, the array can have exactly two elements, and the solution should still work.

    std::vector<int> nums = {1, 4};
int target = 5;
std::vector<int> result = twoSum(nums, target);
std::cout << result[0] << ", " << result[1] << std::endl;  // Output: 0, 1

  4. Zeros in the Array:
    If the array contains zeros, the solution should correctly handle the target involving zero.

    std::vector<int> nums = {0, 4, 3, 0};
int target = 0;
std::vector<int> result = twoSum(nums, target);
std::cout << result[0] << ", " << result[1] << std::endl;  // Output: 0, 3

  5. Large Inputs:
    If the array contains a large number of elements, the hash map approach ensures efficiency even with significant data size.

    std::vector<int> nums(100000);
for (int i = 0; i < 100000; i++) nums[i] = i;
int target = 199999;
std::vector<int> result = twoSum(nums, target);
std::cout << result[0] << ", " << result[1] << std::endl;  // Output: 99998, 99999

Testing the Solution

It’s always important to test the solution with different scenarios:

int main() {
    // Test case 1: Normal case
    std::vector<int> result1 = twoSum({2, 7, 11, 15}, 9);
    std::cout << "Result: [" << result1[0] << ", " << result1[1] << "]\n";  // Output: [0, 1]

    // Test case 2: No valid pair
    std::vector<int> result2 = twoSum({1, 2, 3}, 10);
    std::cout << "Result: " << (result2.empty() ? "No solution" : "Solution found") << "\n";  // Output: No solution

    // Test case 3: Same element twice
    std::vector<int> result3 = twoSum({3, 3}, 6);
    std::cout << "Result: [" << result3[0] << ", " << result3[1] << "]\n";  // Output: [0, 1]

    // Test case 4: Large array
    std::vector<int> result4 = twoSum({1, 5, 3, 7, 11, 8}, 15);
    std::cout << "Result: [" << result4[0] << ", " << result4[1] << "]\n";  // Output: [1, 4]
}

Conclusion

In this post, we’ve discussed two approaches to solving the Two Sum problem in C++. The brute-force approach is easy to understand but inefficient for large arrays. The optimized approach, using a hash map, improves the time complexity to O(n) by using constant-time lookups. Understanding these approaches helps build a foundation in both problem-solving and data structures like hash maps.