Two Sum in C++ with O(n^2) 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:

For this lesson, your algorithm should run in O(n^2) time and use O(1) extra space.
(There exist faster solutions which we will discuss in future lessons)

Understanding the Problem

The core challenge of the 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 are multiple solutions or using the same index twice, which is not allowed.

Approach

To solve this problem, we can start with a naive approach and then discuss more optimized solutions.

Naive Solution

The naive solution involves checking all possible pairs of elements to see if they sum up to the target. This can be achieved using two nested loops:

for (int i = 0; i < nums.size() - 1; ++i) {
    for (int j = i + 1; j < nums.size(); ++j) {
        if (nums[i] + nums[j] == target) {
            return {i, j};
        }
    }
}
return {-1, -1};

This approach has a time complexity of O(n^2) and uses O(1) extra space. While it is simple, it is not efficient for large arrays.

Optimized Solution

A more optimized solution involves using a hash map to store the indices of the elements as we iterate through the array. This allows us to check if the complement of the current element (i.e., target - nums[i]) exists in the hash map in constant time.

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 current element and the complement.
If it does not exist, add the current element and its index to the hash map.
If no solution is found, return [-1, -1].

Code Implementation

#include <vector>
#include <unordered_map>
using namespace std;

vector<int> twoSum(vector<int>& nums, int target) {
    unordered_map<int, int> num_map; // To store the number and its index
    for (int i = 0; i < nums.size(); ++i) {
        int complement = target - nums[i];
        if (num_map.find(complement) != num_map.end()) {
            return {num_map[complement], i}; // Return the indices of the two numbers
        }
        num_map[nums[i]] = i; // Add the number and its index to the map
    }
    return {-1, -1}; // Return [-1, -1] if no solution is found
}

Complexity Analysis

The time complexity of the optimized solution is O(n) because we traverse 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 one element: 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:

// Test case 1: Normal case
assert(twoSum({2, 7, 11, 15}, 9) == vector<int>{0, 1});

// Test case 2: No solution
assert(twoSum({1, 2, 3}, 6) == vector<int>{-1, -1});

// Test case 3: Negative numbers
assert(twoSum({-1, -2, -3, -4, -5}, -8) == vector<int>{2, 4});

// Test case 4: Zero
assert(twoSum({0, 4, 3, 0}, 0) == vector<int>{0, 3});

Thinking and Problem-Solving Tips

When approaching such problems, consider the following tips:

Understand the problem requirements and constraints thoroughly.
Start with a brute force solution to get a basic understanding.
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 problem, explored a naive solution, and then optimized it using a hash map. 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.

Additional Resources

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