Two Sum

Problem Source LeetCode
Companies: Google, Amazon, Apple, Microsoft, Adobe, Facebook, Oracle, Nvidia, SAP, Paypal, Walmart Labs, Samsung

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

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

Example 1:

Given nums = [3, 6, 12, 4], target = 15,

Because nums[0] + nums[2] = 3 + 12 = 15,
return [0, 2].

Solution:

This problem can be solved using Brute Force. In this, we have two go through each element x and then check if there exist an element which is equal to target - x. The time complexity of this implementation will be O(n²).

Another approach to solve this problem is use of Hash Tables. In this implementation mapping of the value of element with its index is done. We will iterate through the array and keep on inserting every element together-with, we will check if there exist a complement of the current element. If exist, we will return there indexes and break the loop, otherwise move forward and insert elements into the hash table.

public static class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> map = new HashMap();
        for (int i = 0; i < nums.length; i++) {
            if (map.containsKey(target - nums[i])) {
                return new int[]{map.get(target - nums[i]), i};
            } else {
                map.put(nums[i], i);
            }
        }
        return new int[]{-1, -1};
    }
}

#include <vector>
#include <unordered_map>
using namespace std;
class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int, int> m;
        vector<int> result;
        for(int i = 0; i < nums.size(); i++){
        // not found the second one
            if (m.find(nums[i]) == m.end() ) {
            // store the first one poisition into the second one's key
                m[target - nums[i]] = i;
            } else {
            // found the second one
                result.push_back(m[nums[i]]);
                result.push_back(i);
                break;
            }
        }
        return result;
    }
};

Python Implementation

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        two = {}
        for i, num in enumerate(nums):
            if target - num in two:
                return (two[target - num], i)
            two[num] = i

Complexity Analysis:

• Time Complexity: O(n).
• Space complexity: O(n)