Two Sum in C++
Introduction
Two Sum is one of the most popular array problems used in
Data Structures and Algorithms (DSA) and coding interviews.
The problem asks us to find two different elements in an array whose sum is
equal to a given target value.
In this tutorial, we will learn how to solve the
Two Sum problem in C++ using the
Brute Force approach. The solution uses two nested loops to
check every possible pair of elements in the array.
When a pair whose sum is equal to the target is found, the program returns the
indices of those two elements. This approach is simple and easy
to understand, making it a good starting point for learning the Two Sum problem.
Table of Contents
Problem Statement
Given an array of integers nums and an integer
target, find the indices of two different elements such that
their values add up to the target.
You may assume that each input has exactly one solution, and the same element
cannot be used twice.
The answer should contain the indices of the two elements.
Approach
We can solve the Two Sum problem using the
Brute Force approach.
The basic idea is to check every possible pair of elements in the array.
For each element at index i, we check the elements after it
using another loop starting from i + 1.
If the sum of the two elements is equal to the target, we immediately return
their indices.
For example, consider:
nums = [2, 7, 11, 15]
target = 9
We start with the first element:
2 + 7 = 9
Since the sum is equal to the target, the indices
0 and 1 are returned.
Algorithm
- Start the program.
- Take the array nums and the target value.
- Use an outer loop to traverse the array using index i.
- Start an inner loop from j = i + 1.
- Compare every possible pair of elements.
- Calculate nums[i] + nums[j].
- Check whether the sum is equal to the target.
- If the sum is equal to the target, return {i, j}.
- Continue checking pairs until a valid pair is found.
- If no pair is found, return an empty vector.
- Stop the program.
C++ Program
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target)
{
for(int i = 0; i < nums.size(); i++)
{
for(int j = i + 1; j < nums.size(); j++)
{
if(nums[i] + nums[j] == target)
{
return {i, j};
}
}
}
return {};
}
};
The function receives an integer array nums and an integer
target.
nums = [2, 7, 11, 15]
target = 9
The objective is to find two different elements whose sum is equal to
9.
Sample Output
[0, 1]
Output
The function returns the indices of the two elements whose sum is equal to the
target.
For the given example:
nums = [2, 7, 11, 15]
target = 9
The elements 2 and 7 produce the required sum:
2 + 7 = 9
Their indices are 0 and 1.
Therefore, the output is:
[0, 1]
Explanation
Step 1
Create the twoSum() function.
vector<int> twoSum(vector<int>& nums, int target)
- nums is the input integer array.
- target contains the required sum.
- The function returns a vector<int> containing the two indices.
Step 2
Use the outer loop to select the first element.
for(int i = 0; i < nums.size(); i++)
{
}
- i represents the index of the first element.
- The loop starts from index 0.
- The loop continues until the last index of the array.
Step 3
Use the inner loop to select the second element.
for(int j = i + 1; j < nums.size(); j++)
{
}
The inner loop starts from i + 1. This is important because
we should not use the same array element twice, and we do not need to check
the same pair again in reverse order.
For example, after checking:
nums[0] + nums[1]
there is no need to check:
nums[1] + nums[0]
Step 4
Check whether the sum of the two selected elements is equal to the target.
if(nums[i] + nums[j] == target)
{
}
- nums[i] represents the first selected element.
- nums[j] represents the second selected element.
- The two values are added together.
- The result is compared with the target.
Step 5
Return the indices when the required pair is found.
return {i, j};
The function returns the indices of the two elements instead of returning the
actual values.
For example:
nums = [2, 7, 11, 15]
target = 9
The pair 2 and 7 is found at indices
0 and 1.
Therefore:
return {0, 1};
Step 6
Return an empty vector if no pair is found.
return {};
This statement returns an empty vector. It acts as a fallback if the loops
finish without finding a pair whose sum equals the target.
Dry Run
Input
nums = [2, 7, 11, 15]
target = 9
Processing
| i |
j |
nums[i] |
nums[j] |
Sum |
Result |
| 0 |
1 |
2 |
7 |
9 |
Match Found |
At i = 0 and j = 1:
nums[0] + nums[1]
= 2 + 7
= 9
The result is equal to the target. Therefore, the function immediately returns:
[0, 1]
Output
[0, 1]
Flow of Execution
Start
│
▼
Receive nums
│
▼
Receive target
│
▼
Start outer loop
│
▼
Start inner loop
│
▼
Calculate nums[i] + nums[j]
│
▼
Sum == target?
│ │
Yes No
│ │
▼ │
Return {i,j} │
│
▼
Check next pair
│
▼
More pairs?
│ │
Yes No
│ │
└────┐ ▼
│ Return {}
│
▼
Stop
Time Complexity
| Case |
Complexity |
| Best Case |
O(1) |
| Average Case |
O(n²) |
| Worst Case |
O(n²) |
Overall Worst-Case Time Complexity:
O(n²)
The solution uses two nested loops. In the worst case, the outer loop and
inner loop examine almost every possible pair of elements.
For an array containing n elements, the number of possible
pairs is approximately:
n(n - 1) / 2
Therefore, the time complexity is:
O(n²)
Space Complexity
The algorithm does not use an additional data structure that grows with the
input size.
- The variables i and j require constant space.
- The returned vector contains two indices.
- No hash table or additional array is used by the algorithm.
Auxiliary Space Complexity: O(1)
The Brute Force approach is therefore considered a constant auxiliary-space
solution.
Applications
- Solving array-based programming problems.
- Finding pairs that satisfy a particular sum condition.
- Learning Brute Force problem-solving techniques.
- Understanding nested loops in DSA.
- Preparing for coding interviews.
- Practicing LeetCode array problems.
- Building a foundation for optimized Two Sum solutions.
- Understanding pair-searching problems.
- Learning how array indices are used in algorithms.
- Developing problem-solving skills for competitive programming.
Key Points
- Two Sum is a popular array problem.
- The objective is to find two different elements whose sum equals the target.
- The solution returns the indices of the two elements.
- The Brute Force approach checks every possible pair.
- The outer loop selects the first element.
- The inner loop starts from i + 1.
- Starting from i + 1 prevents using the same element twice.
- It also prevents checking the same pair in reverse order.
- The worst-case time complexity is O(n²).
- The auxiliary space complexity is O(1).
- The function immediately returns when a valid pair is found.
- An empty vector is returned if no pair is found.
- The Brute Force solution is simple but can be inefficient for large arrays.
Interview Questions
- What is the Two Sum problem?
- What is the objective of the Two Sum problem?
- What does the Two Sum function return?
- What is the Brute Force approach?
- Why are two loops used in the Brute Force solution?
- Why does the inner loop start from i + 1?
- Why can't the same array element be used twice?
- What is the time complexity of the Brute Force Two Sum solution?
- What is the space complexity of the Brute Force solution?
- What is the purpose of nums[i] + nums[j]?
- Why does the function return {i, j} instead of the values?
- What happens if no pair is found?
- How can Two Sum be optimized?
- How can a hash table be used to solve Two Sum?
- What is the time complexity of the optimized Two Sum solution?
- What is the difference between Brute Force and Hash Map approaches?
- Why is Two Sum commonly asked in coding interviews?
Frequently Asked Questions (FAQs)
1. What is Two Sum?
Two Sum is an array problem in which we need to find two different elements
whose sum is equal to a given target value.
2. What does the Two Sum solution return?
The solution returns the indices of the two elements whose sum equals the
target.
3. What approach is used in this solution?
This solution uses the Brute Force approach. It checks every
possible pair of elements in the array.
4. Why does the inner loop start from i + 1?
The inner loop starts from i + 1 so that the same element is
not used twice and previously checked pairs are not repeated.
5. What is the time complexity of this solution?
The worst-case time complexity is O(n²) because the algorithm
uses two nested loops to check possible pairs.
6. What is the space complexity?
The auxiliary space complexity is O(1) because the algorithm
does not use an additional data structure whose size depends on the input.
7. What happens when a valid pair is found?
The function immediately returns the indices of the pair using:
return {i, j};
8. What does return {} mean?
return {} returns an empty vector. It is used as a fallback
when no valid pair is found.
9. Can Two Sum be solved faster?
Yes. An optimized solution can use a hash table such as
unordered_map to reduce the average time complexity to
O(n).
10. Is the Brute Force solution useful?
Yes. Although it is not the most efficient solution for large inputs, the
Brute Force approach is simple and helps beginners understand the problem
before learning optimized solutions.
Keywords
Two Sum in C++, Two Sum LeetCode, Two Sum Problem in C++, Two Sum Brute Force,
Two Sum Algorithm, Two Sum Solution C++, LeetCode Two Sum Solution,
Two Sum DSA, Two Sum Coding Problem, Two Sum Interview Question,
Array Problems in C++, Brute Force Algorithm, C++ DSA Problems,
LeetCode Array Problems, Two Sum Time Complexity, Two Sum Space Complexity,
unordered_map Two Sum, Coding Interview Questions, Data Structures and
Algorithms in C++.
Conclusion
In this tutorial, we learned how to solve the Two Sum problem in
C++ using the Brute Force approach. The algorithm
uses two nested loops to check every possible pair of elements and returns the
indices when their sum matches the target.
The Brute Force approach is easy to understand and provides a good foundation
for learning array-based problem solving. However, its worst-case time
complexity is O(n²), which can become inefficient for large
arrays.
After understanding this solution, the next step is to learn the optimized
Hash Map approach, which can solve Two Sum in
O(n) average time.
Comments
Post a Comment