LeetCode — Two Sums — aadimator.com

LeetCode — Two Sums

This problem was taken from LeetCode — 1. Two Sum. This post first appeared on https://aadimator.com/leetcode-two-sums/

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

Given nums = [2, 7, 11, 15], target = 9,
Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

Solution

Here, we’ll look at two solutions. One is the obvious but brute-force algorithm, while the other one is somewhat harder to get but more efficient, comparatively.

Brute-force Solution

Here, we compare each and every number with the other in the list and see if they add up to the target number. If they do add up, we return their indices. Although this works, still it’s an inefficient solution, O(n²). Its runtime at LeetCode site was 4512 ms when I submitted it.

class Solution:
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        for i in range(len(nums)):
            for j in range(i+1, len(nums)):
                if nums[i] + nums[j] == target:
                    return [i, j]

Better Solution

We create a dictionary to store the data such that the key is the number and the value is the index at which it was present. We then traverse over the list once and see if the complement of the current number is present in the dictionary already. If it is present, we return its index, stored in the dictionary, along with the current index. If it is not present in the dictionary already, we add the current number and its index to the dictionary. Its runtime at LeetCode site was 24 ms when I submitted it. You can clearly see how much optimized it is as compared to the previous one.

class Solution(object):
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        dict = {}
        for i in range(len(nums)):
            complement = target - nums[i]
            if complement in dict:
                return dict[complement], i
            dict[nums[i]]=i

I would welcome any queries or suggestions to improve this algorithm. Feel free to reach out to me.