Leetcode: Two Sum

This is part of a series of Leetcode and other curated solution explanations (index).
If you liked this solution or found it useful, please like this post.

Leetcode Problem #1 (Easy): Two Sum

1. Two Sum

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

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 = 9
Output: [0,1]
Output: Because nums[0] + nums[1] == 9, we return [0, 1].

Example 2:

Input: nums = [3,2,4], target = 6
Output: [1,2]

Example 3:

Input: nums = [3,3], target = 6
Output: [0,1]

Constraints:

2 <= nums.length <= 104
-109 <= nums[i] <= 109
-109 <= target <= 109
Only one valid answer exists.

Pre-Requisite

Let's not waste time to thing a two loops solution is even worthy of consideration! Runtime: O(n^2)

Also, you have to understand that the solution requires you to return the index of the values needed to get this sum, so you can't sort the input to move left or right.

So, can you think of another way!

Solution

There can be multiple solutions but one approach can give you a O(n) runtime complexity. And that is with using hashmap's!

So how does it work?
say you store indexes of all the numbers from the array as a map, so that the numbers become the key of the hashmap and the indexes become value.

How will that help?

• simply loop over the array again, find the required second number and check if it exists in the hashmap or not! If you found it, find the index and return the index of first number and second number.

This solution is really elegant and works really well, the only downside is that you need a O(n) space complexity as well.

Implementation

• For some problems python really provides a concise solution

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        dictionary = {}

        for index, value in enumerate(nums):
            dictionary[value] = index


        for i in range(len(nums)):
            second_number = target - nums[i]
            if second_number in dictionary.keys():
                second_index = nums.index(second_number)

                if i != second_index:
                    return sorted([i, second_index])

The result

** NOTE - the interviewer might ask you, why did you create two for loops instead of 1 - and yes you can do it more concisely - but i guess you understand the solution better with O(n) loop.

• in java

int[] twoSum(int[] nums, int target) {

        final Map<Integer, Integer> map = IntStream.range(0, nums.length)
                .boxed()
                .collect(Collectors.toMap(i -> nums[i],
                        i -> i,
                        (a, b) -> b));

        for (int i = 0; i < nums.length; i++) {
            int secondNumber = target - nums[i];

            if (map.containsKey(secondNumber)) {
                int secondNumberIndex = map.get(secondNumber);

                if (secondNumberIndex != i) {
                    return new int[]{i, secondNumberIndex};
                }
            }

        }

        return new int[]{};
    }