Two Sum Leetcode Problem
Solving the “Two Sum” Problem in C++ a Beginner guide :
The “Two Sum” problem is a quintessential coding challenge frequently encountered in technical interviews and competitive programming. It involves finding two indices in an array of integers whose values sum up to a given target. In this blog post, we’ll explore four distinct approaches to solving this problem, ranging from brute force to more sophisticated hash map techniques.
Problem Statement
Given an array of integers nums and an integer target, return the indices of the two numbers such that they add up to target. Assume that each input has exactly one solution, and you cannot use the same element twice. The order of the returned indices does not matter.
Example:
Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].Approach 1: Brute Force
The simplest way to solve the problem is to check every possible pair of numbers and see if their sum equals the target.
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 {};
}
};Iterate through each element in the array using a nested loop. For each element, check every other element to see if their sum equals the target. If a pair is found that sums to the target, return their indices.
Complexity:
- Time complexity: O(n²)
- Space complexity: O(1)
Approach 2: Two Pointer Technique
By sorting the array and using two pointers, we can efficiently find the two numbers that sum up to the target.
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
vector<int> sortedNums(nums.begin(), nums.end());
sort(sortedNums.begin(), sortedNums.end());
int left = 0;
int right = sortedNums.size() - 1;
while(left < right){
int sum = sortedNums[left] + sortedNums[right];
if(sum == target){
vector<int> ans;
for(int i = 0; i < nums.size(); i++){
if(nums[i] == sortedNums[left] || nums[i] == sortedNums[right]){
ans.push_back(i);
}
}
return ans;
} else if(sum < target) left++;
else right--;
}
return {};
}
};
First be sort the input array and store a sorted copy of it. Then initialize two pointers, ‘left’ and ‘right’, pointing to the start and end of the sorted array, respectively. After it iterate through the array using of two pointers and check the sum o f the numbers at the pointers. If the sum equals the target, find the indices of the numbers in the original array and return them. If the sum is less than the target, move the left pointer to the right. If the sum is greater than the target, move the right pointer to the left And If no such pair is found, return an empty vector.
Complexity:
- Time complexity: O(n log n) due to sorting
- Space complexity: O(n)
Approach 3: Two-Pass Hash Table
By using a hash table, we can store the elements and their indices for quick lookup. This approach involves two passes through the array.
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
unordered_map<int, int> nums_map;
for(int i = 0; i < nums.size(); i++){
nums_map[nums[i]] = i;
}
for(int i = 0; i < nums.size(); i++){
int complement = target - nums[i];
if(nums_map.find(complement) != nums_map.end() && nums_map[complement] != i){
return {i, nums_map[complement]};
}
}
return {};
}
};Use an unordered_map (hash map) to store each element and its index. Iterate through the array and for each element, check if the complement (target — current element) exists in the map. If the complement exists and is not the same element, return the indices.
Get Prince kumar’s stories in your inbox
Join Medium for free to get updates from this writer.
Complexity:
- Time complexity: O(n)
- Space complexity: O(n)
Approach 4: One-Pass Hash Table
This approach combines the two steps of the previous method into a single pass through the array, improving efficiency.
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
unordered_map<int, int> nums_map;
for(int i = 0; i < nums.size(); i++){
int complement = target - nums[i];
if(nums_map.find(complement) != nums_map.end()){
return {nums_map[complement], i};
}
nums_map[nums[i]] = i;
}
return {};
}
};First Initialize an unordered_map to store each element’s value and its index. Then iterate through the array: For each element, calculate its complement (target — current element) and then Check if the complement exists in the hash map. If it exists, return the indices of the complement and the current element. Otherwise, add the current element and its index to the hash map. If no pair is found, return an empty vector.
Complexity:
- Time complexity: O(n)
- Space complexity: O(n)
Testing and Validation
We’ll test our solution with various test cases, including the examples provided in the problem statement :
- Example 1:
nums = [2,7,11,15], target = 9(Expected Output:[0,1]) - Example 2:
nums = [3,2,4], target = 6(Expected Output:[1,2]) - Example 3:
nums = [3,3], target = 6(Expected Output:[0,1])
Complexity Analysis:
- Brute Force: O(n²) time and O(1) space
- Two Pointer: O(n log n) time and O(n) space
- Two-Pass Hash Table: O(n) time and O(n) space
- One-Pass Hash Table: O(n) time and O(n) space
Conclusion
In this blog post, we’ve explored four different approaches to solving the “Two Sum” problem, each with its own advantages and trade-offs. From the straightforward brute force method to the highly efficient one-pass hash table technique, we’ve demonstrated how to implement each solution in C++. We encourage you to try these methods and explore other problems to further enhance your problem-solving skills.
Next Steps
For further exploration, consider solving similar problems such as “3 Sum” or “4 Sum.” Delve deeper into data structures and algorithms to broaden your understanding and improve your coding efficiency.
Hi, I’m Prince, a passionate software developer with expertise in C++ and problem-solving. You can connect with me on Linkedin or check out my GitHub repository for more coding adventures.
