How to Solve ‘Two Sum – Leetcode’ Problem?

Two Sum Leetcode is one of the most commonly asked problems in technical/programming interviews. Let us take a look at What is a Two Sum problem?

Suppose we want to find combinations of pairs of numbers from the given list of numbers whose addition yields a given target. This is described by the famous ‘Two Sum’ problem described on LeetCode

How to Solve ‘Two Sum – Leetcode’ problem?

First, we need to understand that we are looking for a pair of numbers that add up to the given target. It’s a search operation and we would need to iterate till the end of the given array to find the numbers.

The simplest brute force approach would be to iterate through the entire input array select a number ‘i’ and select another consecutive number ‘j’ and see if we can add up them and reach target ‘T’. This approach will definitely work but with the worst time complexity of O(N²). Hence, this might not work in all scenarios. Can we do better?

Since it’s a search operation. We can use hashmap data structures and hash the difference between the Target ‘T’ and the current number ‘nums[i]’ along with nums[i] so that in future iterations we can use the precomputed difference and find the pair of numbers that add up to the target ‘T’. The runtime complexity of this approach would be O(n) as Hashmap takes only O(1) time to search the stored number.

Here are the steps or pseudo code of the algorithm:

• Start
• Create a empty Hashmap
• For each number nums[i] in the input array
  • Find if difference of Target ‘T’ and nums[i] is already seen
    • Return the pair to calling function
  • Store the current number in hashmap
• End

Here is the C++ implementation of the ‘Two Sum’ problem

vector<int> twoSum(vector<int>& nums, int T) {
  // Hashmap to store the seen number
  unordered_map<int, int> D; 
  // Iterate through all numbers  
  for(int i=0; i<nums.size(); ++i){ 
    // Find Target - nums[i] in Hashmap
    if(D.count((T - nums[i]))){ 
      // If found, Return as pair(vector) of numbers
      return {D[ T - nums[i] ], i}; 
    }
    // Store current number in Hashmap
    D[nums[i]] = i; 
  }
  // Return empty vector if pair cannot be found
  return {}; 
}

Some of the practical applications of Hashmaps

1. Dictonary
2. File systems
3. Password Verification
4. Storage optimization in servers etc,.