Start learning free

LESSON 212 OF 409 · BRUTE FORCE

Two Sum in C++ with O(n^2) Time Complexity

Practice O(n²) Read the full explanation

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)

Hints:

Let's come up with a brute force approach. Brute force tries each and every candidate to our solution. For this problem, the candidates are all the pairs of elements (nums[i], nums[j]). We should go through each pair of indices (i, j) such that 0 <= i < j < n. How can we achieve this?

Using two nested for loops! The first loop will try out each possible i between 0 and n - 2. The second loop will be written inside the first one and will try out each possible j between i + 1 and n - 1.

for each i : 0 -> n - 2:
	for each j : i + 1 -> n - 1:

What should be written inside these loops?

Inside the loops we should check if the pair (nums[i], nums[j]) is a solution, e.g. if nums[i] + nums[j] == target. If so, we should return the pair of indices (i, j):

for each i : 0 -> n - 2:
	for each j : i + 1 -> n - 1:
		if nums[i] + nums[j] == target:
			return [i, j]

What if there's no solution, when should we return [-1, -1]?

If the two loops terminate and we haven't returned anything, we can conclude there is no solution as we have tried all possible candidates and none was good. So, below the loops, we should return [-1, -1]:

for each i : 0 -> n - 2:
	for each j : i + 1 -> n - 1:
		if nums[i] + nums[j] == target:
			return [i, j]
return [-1, -1]

STEP 1 OF 4

Guided

Ctrl + Enter to check

C++ · BRUTE FORCE

Two Sum in C++, explained

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:

Keep going with C++About 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.

Start learning free