Two Sum IV - O(n) Time Complexity in C++

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) time and use O(n) space.

Understanding the Problem

The core challenge of this problem is to find two indices in an array such that the sum of the elements at these indices equals 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 start with a naive approach and then optimize it:

Naive Approach

The naive approach involves using two nested loops to check all possible pairs of indices. This approach has a time complexity of O(n^2), which is not optimal for large arrays.

Optimized Approach

To achieve O(n) time complexity, we can use a hash map (unordered_map in C++). The idea is to iterate through the array and for each element, check if the complement (target - current element) exists in the hash map. If it does, we have found our solution. If not, we add the current element and its index to the hash map.

Algorithm

Here is a step-by-step breakdown of the optimized algorithm:

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

Code Implementation


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

std::vector<int> twoSum(const std::vector<int>& nums, int target) {
    // Create a hash map to store the value and its index
    std::unordered_map<int, int> indexOfValue;
    
    // Iterate through the array
    for (int j = 0; j < nums.size(); ++j) {
        int complement = target - nums[j];
        
        // Check if the complement exists in the hash map
        if (indexOfValue.find(complement) != indexOfValue.end()) {
            // If found, return the indices
            return {indexOfValue[complement], j};
        }
        
        // Otherwise, add the current element and its index to the hash map
        indexOfValue[nums[j]] = j;
    }
    
    // If no solution is found, return [-1, -1]
    return {-1, -1};
}

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

Complexity Analysis

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

Edge Cases

Potential edge cases include:

An empty array: The function should return [-1, -1].
An array with no valid pairs: The function should return [-1, -1].
Negative numbers and zero: The function should handle these correctly.

Testing

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

1. nums = [2, 7, 11, 15], target = 9 -> Output: [0, 1]
2. nums = [3, 2, 4], target = 6 -> Output: [1, 2]
3. nums = [3, 3], target = 6 -> Output: [0, 1]
4. nums = [], target = 0 -> Output: [-1, -1]
5. nums = [1, 2, 3], target = 7 -> Output: [-1, -1]

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 data structures that can optimize your solution.
Practice similar problems to improve your problem-solving skills.

Conclusion

In this blog post, we discussed the Two Sum problem, its significance, and various approaches to solve it. We provided a detailed explanation of the optimized solution using a hash map and analyzed its complexity. Understanding and solving such problems is crucial for improving algorithmic thinking and coding skills.

Additional Resources

For further reading and practice, consider the following resources: