Solving the ‘Two Sum Problem’ on LeetCode — C++ Solutions Walkthrough

Image Source

Introduction

In this post, we will delve into three diverse solutions to the Two Sum Problem in C++, evaluating their time and space complexity to aid in understanding the most optimal approach. A detailed, step-by-step explanation with commented code for each solution is provided to offer deeper insights and clarity after the conclusion, ensuring a comprehensive grasp of the various methods available.

Problem Description

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

C++ Function Signature:

vector<int> twoSum(vector<int>& nums, int target);

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]

Solution 1: Brute Force Approach

Explanation

In this approach, we iterate through the entire array, and for each element, we iterate through the remaining elements to find a pair that sums up to the target. This method guarantees a solution if one exists as it checks every possible pair.

C++ Code:

class Solution {
public:
    vector<int> twoSum(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 {};
  }
};

Time Complexity: O(n²), In the worst case, for each element in the array, we iterate through the rest of the array to find the complement. With n as the number of elements, we perform roughly n * (n-1) / 2 comparisons, resulting in a time complexity of O(n²).

Space Complexity: O(1), No additional data structures (like arrays or hash maps) are used, and the extra space required does not depend on the size of the input array, hence the space complexity is constant, O(1).

Solution 2: Two-Pass Hash Table

Explanation

We use a hash map to reduce the time complexity. First, we add each element and its index to a hash map. Then, we iterate through the array again and check if each element’s complement (target — element) exists in the hash map.

C++ Code:

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

Time Complexity: O(n), We perform two separate iterations through the array. In the first iteration, we add each element and its index to a hash map, which takes O(n) time. In the second iteration, we check for each element’s complement in the hash map, which again takes O(n) time. So, the total time complexity is O(n) + O(n), which is O(n).

Space Complexity: O(n), We use a hash map to store the elements and their indices. In the worst case, the hash map stores all the n elements of the array, leading to a space complexity of O(n).

Solution 3: One-Pass Hash Table

Explanation

This approach optimizes the Two-Pass Hash Table Approach by only making one iteration through the array. During the iteration, we add each element’s index to a hash map and check if the complement already exists in the hash map.

C++ Code:

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

Time Complexity: O(n), In this approach, we iterate through the array once, performing both the addition of elements to the hash map and the check for the complement in the same pass. Each of these operations takes constant time, O(1), on average. Hence, for n elements, the time complexity is O(n).

Space Complexity: O(n), Just like the two-pass hash table approach, we use a hash map to store the array elements and their indices. In the worst case, all n elements are stored, leading to a space complexity of O(n).

Conclusion and Comparison

In solving the Two Sum problem, we’ve explored three distinctive methods, each with its pros and cons. The Brute Force Approach, while straightforward, is inefficient for large datasets. The Two-Pass Hash Table offers better performance by utilizing a hash table, and the One-Pass Hash Table stands out as the most time-efficient option, especially beneficial for larger datasets.

Final Thoughts

Each method has its place. For smaller datasets, the Brute Force Approach might be sufficient. However, its quadratic time complexity makes it unsuitable for processing large datasets. The Two-Pass Hash Table approach offers an excellent middle-ground solution, enhancing time efficiency while keeping the implementation relatively simple. Finally, the One-Pass Hash Table approach stands out as the most time-efficient option, especially beneficial for larger datasets where execution time is paramount. Your choice should weigh the dataset’s size against the trade-off between time and space complexity. For most real-world scenarios, a linear time complexity solution like the One-Pass Hash Table approach is typically the most beneficial, ensuring optimal performance and efficient resource utilization.

1. Big O Notation Guide
2. LeetCode Problem

Thank you for reading! If you find this guide helpful, please consider highlighting, clapping, responding or connecting with me on Twitter/X as it’s very appreciated!

Also check out my other Leetcode Walkthrough Lists:

• Palindrome Number Problem

Step-by-Step Explanations with Code Comments

In this section, each solution is broken down, providing the C++ code with comments and step-by-step explanations for a deeper understanding.

Solution 1: Brute Force Approach with Comments

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        // Step 1: Iterate over the numbers in the array.
        for (int i = 0; i < nums.size(); i++) {
            // Step 2: For each number, iterate over the rest of the numbers in the array.
            for (int j = i + 1; j < nums.size(); j++) {
                // Step 3: Check if the current two numbers add up to the target.
                if (nums[i] + nums[j] == target) {
                    return {i, j};
                }
            }
        }
        // Step 4: If no such pair is found, return an empty vector.
        return {};
    }
};

• Step 1: The outer loop iterates over the numbers in the array.
• Step 2: The inner loop iterates over the rest of the numbers for each number from the outer loop.
• Step 3: If a pair sums up to the target, their indices are returned.
• Step 4: If no such pair is found, an empty vector is returned.

Solution 2: Two-Pass Hash Table Approach with Comments

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        // Step 1: Create a map to store numbers and their indices.
        unordered_map<int, int> numMap;
        // Step 2: Add each number and its index to the map.
        for (int i = 0; i < nums.size(); i++) {
            numMap[nums[i]] = i;
        }
        // Step 3: Check for each number, if its complement exists in the map.
        for (int i = 0; i < nums.size(); i++) {
            int complement = target - nums[i];
            // Ensure the complement is not the number itself.
            if (numMap.count(complement) && numMap[complement] != i) {
                // Step 4: If the complement exists, the indices are returned.
                return {i, numMap[complement]};
            }
        }
        // Step 5: If no two numbers sum up to the target, return an empty vector.
        return {};
    }
};

• Step 1: A map is created to store numbers and their indices.
• Step 2: Each number and its index are added to the map.
• Step 3: For each number, it checks if its complement exists in the map (ensuring it’s not the number itself).
• Step 4: If the complement exists, the indices are returned, otherwise, move to the next iteration.
• Step 5: If no pair sums up to the target, an empty vector is returned.

Solution 3: One-Pass Hash Table Approach with Comments

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        // Step 1: Again, create a map to store numbers and their indices.
        unordered_map<int, int> numMap;
        // Step 2: During iteration over the numbers, the complement is calculated for each number.
        for (int i = 0; i < nums.size(); i++) {
            int complement = target - nums[i];
            // Step 3: It checks if the complement exists in the map. If so, the indices are returned.
            if (numMap.count(complement)) {
                return {numMap[complement], i};
            }
            // Step 4: Otherwise, the current number and its index are added to the map.
            numMap[nums[i]] = i;
        }
        // Step 5: If no pair sums up to the target, return an empty vector.
        return {};
    }
};

• Step 1: A map is created to store numbers and their indices.
• Step 2: During iteration over the numbers, the complement is calculated for each number.
• Step 3: It checks if the complement exists in the map. If so, the indices are returned.
• Step 4: Otherwise, the current number and its index are added to the map.
• Step 5: If no pair sums up to the target, an empty vector is returned.