Two Sum III in C++ (O(n log n) Time Complexity)

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input will have at most one solution, and you may not use the same index twice.

In case no solution exists, return [-1, -1]

Example:

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

Note:

Your algorithm should run in O(n log n) time and use O(n) extra space.

Understanding the Problem

The core challenge of the "Two Sum III" problem is to find two distinct indices in an array such that the numbers at those indices add up to a given target. This problem is significant in various applications, such as financial transactions, where you need to find pairs of transactions that sum up to a specific amount.

Potential pitfalls include assuming multiple solutions or using the same index twice, which the problem explicitly forbids.

Approach

To solve this problem, we can consider multiple approaches:

Naive Solution

The naive solution involves checking all pairs of numbers to see if they sum up to the target. This approach has a time complexity of O(n^2), which is not optimal for large arrays.

Optimized Solution Using Hash Map

A more efficient approach uses a hash map to store the indices of the numbers we have seen so far. This allows us to check in constant time if the complement of the current number (i.e., target - current number) exists in the hash map.

Optimized Solution Using Sorting and Two Pointers

Another approach involves sorting the array and using two pointers to find the two numbers that sum up to the target. This approach has a time complexity of O(n log n) due to the sorting step.

Algorithm

Let's break down the hash map approach step-by-step:

Initialize an empty hash map.
Iterate through the array.
For each number, calculate its complement (target - current number).
Check if the complement exists in the hash map.
If it exists, return the indices of the current number and its complement.
If it doesn't exist, add the current number and its index to the hash map.
If no solution is found, return [-1, -1].

Code Implementation

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

using namespace std;

vector<int> twoSum(vector<int>& nums, int target) {
    // Create a hash map to store the indices of the numbers
    unordered_map<int, int> num_map;
    
    // Iterate through the array
    for (int i = 0; i < nums.size(); ++i) {
        int complement = target - nums[i];
        
        // Check if the complement exists in the hash map
        if (num_map.find(complement) != num_map.end()) {
            // If found, return the indices
            return {num_map[complement], i};
        }
        
        // Add the current number and its index to the hash map
        num_map[nums[i]] = i;
    }
    
    // If no solution is found, return [-1, -1]
    return {-1, -1};
}

int main() {
    vector<int> nums = {2, 7, 11, 15};
    int target = 9;
    vector<int> result = twoSum(nums, target);
    
    cout << "Indices: [" << result[0] << ", " << result[1] << "]" << endl;
    
    return 0;
}

Complexity Analysis

The time complexity of the hash map approach is O(n) because we iterate through the array once. The space complexity is also O(n) due to the hash map storing the indices.

In comparison, the sorting and two pointers approach has a time complexity of O(n log n) due to the sorting step and a space complexity of O(1) if sorting is done in place.

Edge Cases

Potential edge cases include:

An empty array: The function should return [-1, -1].
An array with one element: The function should return [-1, -1].
No two numbers sum up to the target: The function should return [-1, -1].

Testing

To test the solution comprehensively, consider the following test cases:

Simple case: nums = [2, 7, 11, 15], target = 9 (Expected output: [0, 1])
No solution: nums = [1, 2, 3], target = 6 (Expected output: [-1, -1])
Negative numbers: nums = [-1, -2, -3, -4], target = -6 (Expected output: [1, 3])
Large array: nums = [1, 2, 3, ..., 1000000], target = 1999999 (Expected output: [999998, 999999])

Thinking and Problem-Solving Tips

When approaching such problems, consider the following tips:

Understand the problem constraints and requirements thoroughly.
Start with a brute-force solution to understand the problem better.
Think about how to optimize the solution using data structures like hash maps.
Practice similar problems to improve problem-solving skills.

Conclusion

In this blog post, we discussed the "Two Sum III" problem, explored various approaches to solve it, and provided a detailed explanation of the hash map solution. Understanding and solving such problems is crucial for developing strong problem-solving skills in programming.

We encourage you to practice and explore further to enhance your understanding and proficiency.

Additional Resources

For further reading and practice, consider the following resources: