Link to the Problem
Youtube Video
If you prefer video over text, watch this.
Thought Process
We want to find two numbers that add up to the target. Simple approach is to try out all pairs to check if they add up to the target. However, if you observe this process, once we fix one number, say K, then we know what the other number must be and i.e. target-K. For any other number, they won’t add up to the target. Now if we know that search is a vital operation, employ the best data structure for the search i.e. hash set. Because we want to return indices, use hash map instead.
Algorithm
- Insert all elements with their indices in the map.
- For each number,
K–- Check the map if
Kexists & return the indices if it does.
- Check the map if
- Return empty response because there is no such pair.
Code
| class Solution { | |
| public: | |
| vector<int> twoSum(vector<int>& nums, int target) { | |
| unordered_map<int, int> m; // To store the integer and its index. | |
| int n = nums.size(); // Total integers. | |
| for (int i=0; i<n; i++) { // For each integer, say K - | |
| if (m.find(target-nums[i]) != m.end()) { // Check if (target - K) exists. | |
| return {i, m[target-nums[i]]}; // Yay, found the answer. | |
| } | |
| m[nums[i]] = i; // Save the K in the map with it's index. | |
| } | |
| return {}; // If the answer does not exists. | |
| } | |
| }; |
Is there anything that is still unclear? Let me know in the comments and I can elaborate further.
Don’t forget like & share the post, and subscribe to the blog to get notifications whenever solution to a new problem is added.
Happy Coding!
