LeetCode — Two Sum O(n) solution

Solution of leetcode first problem

TL;DR

If you just want the O(n) solution, click here

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

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

1. O(n²) Solution

To kick start, we calculate all the possible outcome by adding nums[i] and nums[j].

i starts from 0 and ends at nums.length-1

j starts from i+1 and ends at nums.length

e.g. i =1, j loops from 2 to 3

We get 22 when i = 1, j = 3

Javascript code:

var twoSum = function(nums, target) {
    for (let i = 0; i< nums.length-1; i++){
      for (let j=i+1;j<nums.length;j++){
        if (nums[i]+nums[j]===target){
          return [i, j]
        }
      }
    }
};

But the performance is not good comparing with other submitted solution.

Only beats 40.33% of js submission…

2. O(n) solution

Beats 94.84% of js submission!

To beat at least 80% of leetcoders, we want a O(n) solution.

In real world, we want to avoid any nested loop in our code, the performance is horrible when array.length grows!

To do this, we need to make use of the data structure — map.

The map is a key-value store providing us a thunder fast solution to get the value using a key.

Below are the ideas to solve this problem:

nums[i] will be the second value, we have got [ ?, i ] as the answer now, we use map to find the first value

Calculate the difference(first value) between target and nums[i](second value)

Put key: nums[i], value: i into map while looping through nums, so that when we call map.get(difference), we get the first index

If we can get the difference in the map, that means we have already travelled the first value previously, early return the result: [ map.get(difference), i ]

Javascript code:

var twoSum = function(nums, target) {
  let map = new Map();
  
  for (let i = 0; i < nums.length; i++){
    const diff = target - nums[i];
    if (map.get(diff)!==undefined){
      return [map.get(diff), i];
    }
    map.set(nums[i], i);
  }
  
  return [-1, -1];
};