Two Sum Coding Interview Question – Solved

Two sum is one of the popular coding interview questions asked in many software engineering interviews. You can find this question on popular coding websites such as Hackerrank, LeetCode, and Interviewbit.

Today we will be discussing the possible solution and algorithm related to this question. So, let see or understand the questions first.

Question – Two Sum

Given an array of integers number and an integer targetNum, return indices of the two numbers such that they add up to targetNum.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

You can return the answer in any order.

Example 1:

Input: nums = [2,7,11,15], target = 17
Output: [1,2]
Output: Because nums[1] + nums[2] == 17, we return [1, 2].

Constraints:

• 2 <= number.length <= 103
• -109 <= number[i] <= 109
• -109 <= targetNum <= 109
• Only one valid answer exists.

Two Sum Algorithm

Approach 1: Brute Force (C++)

The brute force approach is simple. Loop through each element in the number as x and find if there is another value that equals to target targetNum – x.

class Solution {
public:
    vector<int> twoSum(vector<int>& number, int targetNum) {
        vector<int> res;
        int i = 0;
        while(i<number.size()){
            int j = number.size()-1;
            while(j>i && number[i]+number[j]!=targetNum)j--;
            if(number[i]+number[j]==targetNum && i!=j){
                res.push_back(i);
                res.push_back(j);
                return res;
            }
            i++;
        }
        return res;
    }
};

Run Time Complexity:

• Time complexity: O(n²). For each element, we try to find its complement by looping through the rest of the array which takes O(n) time. Therefore, the time complexity is O(n²).
• Space complexity: O(1).

Approach 2: One-pass Hash Table (C++)

To improve the runtime of the above algorithm we need to think about reducing the runtime complexity of the algorithm. To do so we need to maintain the difference of each element at someplace and compare the same existing difference at O(1) time.

To achieve this we need to use Hash Table. As hash table lookup time for any element is O(1) time as long as the hash function is chosen carefully. A simple implementation of this is to use one iteration. In each iteration, we will check if the target number is present in the hash table or not. If it is not present then we will add that number and index value to the hash table and continue the iteration.

If the value is found means we have our answer. Also, we need to take care that we are not comparing the value of the same index of the current number. Below is the implementation in C++.

class Solution {
public:
    vector<int> twoSum(vector<int>& number, int targetNum) {
        vector<int> res;
        unordered_map<int,int> hash;
        for(int i=0;i<number.size();i++){
            if(hash.find(number[i])==hash.end()) hash[targetNum-number[i]] = i;
            else{
                res.push_back(hash[number[i]]);
                res.push_back(i);
                return res;
            }
        }
        return res;
    }
};

Run Time Complexity:

• Time complexity: O(n)
• Space complexity: O(n), since we are using an extra hash table to store the array index value and value.

Two Sum Solution in Python – One Pass:

class Solution:
    def twoSum(self, number: List[int], targetNum: int) -> List[int]:
        index = 0
        diff_array = {}
        for num in number:
            difference = targetNum - num
            try:
                if diff_array[num] is not None:
                    return(index,diff_array[num])
            except KeyError as k:
                diff_array[difference] = index
                index+=1

If you liked the answer then please follow us on Facebook and Twitter. Let us know the questions and answer you want to cover in this blog.

Wanna read more interview-related questions? Check Top Interview Questions category.