1. Two Sum

LeetCode Problems

Next →

In this tutorial we will solve 1. Two Sum problem from leetcode.

Table of Content

Reference
Problem Statement
Approach
Code
Complexity

Reference: 1. Two Sum

Problem statement

In this problem we have an input integer array nums and we have an integer target. We have to find the indices of two numbers in the given array that add up to target and we cannot use the number at a given index more than once. We are also told in the problem statement that the input would always have exactly one solution.

Example from leetcode.

Example 1:
Input: nums = [2,7,11,15], target = 9
Output: [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 <= 10^4
-10^9 <= nums[i] <= 10^9
-10^9 <= target <= 10^9

In example 1, we can see number at index 0 and 1 adds up to 9.

In example 2, we can see number at index 1 and 2 adds up to 6.

And in example 3, we have number at index 0 and 1 adding up to 6.

Approach

To solve this problem we can take help of hash map and save the number and its index as we traverse the input array.

Input: nums = [2,7,11,15], target = 9

hashmap = {}

index =  0   1   2    3
nums  = [2,  7,  11,  15]
         ^

neededNumber = target - currentNumber
= 9 - 2
= 7

7 is not present in the hashmap, add current number 2 and its index 0.
hashmap = {
  2: 0
}

index =  0   1   2    3
nums  = [2,  7,  11,  15]
             ^

neededNumber = target - currentNumber
= 9 - 7
= 2

2 is present in the hashmap, fetch the index of 2 and return the result.

Code

JavaScript

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function(nums, target) {
  let hm = new Map();
  for(let i = 0; i < nums.length; i++) {
    const currentNumber = nums[i];
    const neededNumber = target - currentNumber;
    const indexOfNeededNumberIfExists = hm.get(neededNumber);
    if (indexOfNeededNumberIfExists !== undefined) {
        return [indexOfNeededNumberIfExists, i];
    }
    hm.set(currentNumber, i);
  }
};

Complexity

Time complexity: O(n)

In the worst case, we will traverse the whole array and if there are n elements then our time complexity will be O(n).

Space complexity: O(n)

In the worst case, our hash map will save n elements. Thus the space complexity will be O(n).

Next →

Array, Hash map and Set

Two Pointers