Author at SyntaxFlow
Given an array of integers nums and an integer target, return the indices of the two numbers such that they add up to target.
You may assume that:
nums = [2,7,11,15]target = 9
[0,1]
nums[0] + nums[1]= 2 + 7= 9
Since the sum equals the target, we return the indices:
[0,1]
nums = [3,2,4]
target = 6
[1,2]
nums[1] + nums[2]= 2 + 4= 6
Return:
[1,2]
2 <= nums.length <= 10^4
-10^9 <= nums[i] <= 10^9
-10^9 <= target <= 10^9The most straightforward idea is:
For every element, check every other element and see whether their sum equals the target.
Since we need two numbers whose sum is target, we can try all possible pairs.
nums = [2,7,11,15]
target = 9
Check:
2 + 7 = 9 ✅
We found the answer, so return:
[0,1]
i.i, traverse the remaining array using index j.nums[i] + nums[j] == target
{i, j}.Dry Run
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
int n = nums.size();
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
if (nums[i] + nums[j] == target) {
return {i, j};
}
}
}
return {};
}
};Time Complexity
O(n²)
Reason:
n times.n times for each element.Total operations:
n × n = O(n²)
Space Complexity
O(1)
No extra data structure is used.
Why is this inefficient?
Suppose:
n = 10000
Then comparisons can be close to:
10000 × 10000= 100,000,000
That's huge.
Notice that for every number nums[i], we are repeatedly searching for:
target - nums[i]
If we could find this required value instantly instead of scanning the whole array, we could reduce the complexity from O(n²) to O(n).
This observation leads to the optimal Hash Map solution.
In the brute-force solution, for every number we searched the entire remaining array to find its partner.
Let's think differently.
Suppose:
nums = [2,7,11,15]
target = 9
We start with:
2
To make 9, we need:
9 - 2 = 7
So instead of searching the whole array later, what if we store numbers we've already seen in a hash map?
For every element nums[i], calculate:
required = target - nums[i]
If required already exists in the hash map, then we have found our answer.
Otherwise, store the current number and its index.
Dry Run:
required = target - nums[i]
required exists in the hash map:{hashMap[required], i}2. Otherwise, store:
hashMap[nums[i]] = i
4. Continue until the answer is found.
C++ code:
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
unordered_map<int, int> mp;
for (int i = 0; i < nums.size(); i++) {
int required = target - nums[i];
if (mp.find(required) != mp.end()) {
return {mp[required], i};
}
mp[nums[i]] = i;
}
return {};
}
};Time Complexity
O(n)
Reason:
O(1).Therefore:
n × O(1) = O(n)
Space Complexity
O(n)
In the worst case, all elements may be stored in the hash map.
Practice link:
Video reference: