Leetcode 1. Two Sum

Link to the Problem

Two Sum

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.

Leetcode 1. Two Sum - Diagram to assist visualization, Problem Solving, Leetcode, Leetcode Solutions, Crack Coding Interview, Coding Interview, Data Structures and Algorithms

Algorithm

  1. Insert all elements with their indices in the map.
  2. For each number, K
    1. Check the map if K exists & return the indices if it does.
  3. 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.
}
};
view raw Leetcode_1.cpp hosted with ❤ by GitHub

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!

Similar Problems

Leetcode 15. 3Sum



Related Posts


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s