Arrays - Two Sum

Classic interview questions on Arrays

Leetcode Link: https://leetcode.com/problems/two-sum/

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.

Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

Method 1: Brute Force

As with any problem, we always start off with the brute force technique. What is the simplest way to get the answer out, without any concern about the time complexity etc.?

We can simply use 2 for-loops and find out the indices:

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        results = []
        for num1 in nums:
            for num2 in nums:
                if(num1 + num2 == target):
                    results.append(num1)
                    results.append(num2)

        return results

This will give us the right results, but such a method will be a poor solution for a huge array. Though space complexity is in constant time of O(1), with 2 for-loops we have a time complexity of O(n2).

Method 2: Hashing

To optimise our solution, we simply use a hashtable or dictionary. We trade space for time.

We store the numbers in the array as the keys, with the indices as the corresponding values. Each time we check if a number's complement (i.e. target - number) exists in the hashtable. If yes, we have found a pair! Else, we add it to the hashtable.

The code will look like this:

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        num_map = {}
        for i in range(len(nums)):
            complement = target - nums[i]
            if(complement in num_map):
                return [i, num_map[complement]]
            else:
                num_map[nums[i]] = i
        return []

This has a time complexity of just O(n) since we run through the list only once. A space complexity of O(n) exists since we need a hashtable to store the numbers.

Avatar
Harish V
Software Engineer + Tech Enthusiast

I code.

comments powered by Disqus

Related