Two Sum II 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 this problem is to find two distinct indices in the array such that the sum of the elements at these indices equals the target value. This problem is significant in various applications, such as financial analysis, where you might need to find two transactions that sum up to a specific amount.

Potential pitfalls include assuming that there might be multiple solutions or using the same index twice, which is not allowed.

Approach

To solve this problem, we can use a hash map to store the indices of the elements as we iterate through the array. This allows us to check in constant time whether the complement of the current element (i.e., target - current element) has already been seen.

Let's discuss a naive solution first:

Naive Solution

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

Optimized Solution

An optimized solution uses a hash map to store the indices of the elements. As we iterate through the array, we check if the complement of the current element (i.e., target - current element) is already in the hash map. If it is, we have found our solution. Otherwise, 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 (i.e., target - current element).
Check if the complement is already in the hash map.
If it is, return the indices of the complement and the current element.
If it is not, 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>

using namespace std;

vector<int> twoSum(vector<int>& nums, int target) {
    // Create a hash map to store the indices of the elements
    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 is already in the hash map
        if (num_map.find(complement) != num_map.end()) {
            // If found, return the indices
            return {num_map[complement], i};
        }
        
        // Otherwise, add the current element 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 optimized solution is O(n) because we iterate through the array once, and each lookup in the hash map is O(1) on average. The space complexity is also O(n) because we store the indices of the elements in the hash map.

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 elements sum up to the target: The function should return [-1, -1].

To test these edge cases, we can add the following test cases:

int main() {
    vector<int> nums1 = {};
    int target1 = 9;
    vector<int> result1 = twoSum(nums1, target1);
    cout << "Indices: [" << result1[0] << ", " << result1[1] << "]" << endl;

    vector<int> nums2 = {5};
    int target2 = 5;
    vector<int> result2 = twoSum(nums2, target2);
    cout << "Indices: [" << result2[0] << ", " << result2[1] << "]" << endl;

    vector<int> nums3 = {1, 2, 3};
    int target3 = 6;
    vector<int> result3 = twoSum(nums3, target3);
    cout << "Indices: [" << result3[0] << ", " << result3[1] << "]" << endl;

    return 0;
}

Testing

To test the solution comprehensively, we should include a variety of test cases, from simple to complex. We can use testing frameworks like Google Test for C++ to automate the testing process.

Thinking and Problem-Solving Tips

When approaching such problems, it is essential to:

Understand the problem requirements and constraints thoroughly.
Think about different approaches and their time and space complexities.
Start with a naive solution and then optimize it.
Consider edge cases and how to handle them.

To develop problem-solving skills, practice solving similar problems and study various algorithms and data structures.

Conclusion

In this blog post, we discussed the Two Sum II problem, understood its core challenges, and explored different approaches to solve it. We provided a detailed explanation of the optimized solution, including its algorithm, code implementation, and complexity analysis. We also discussed edge cases and testing strategies. Understanding and solving such problems is crucial for improving problem-solving skills and preparing for technical interviews.

Additional Resources

For further reading and practice problems related to the topic, consider the following resources: