Two Sum Problem | 2nd August LeetCode Challange 2021 | Javascript Solution

Two Sum – Probably It is the most asked question in a Technical interview for beginner level.   

Even It is the most asked question, there are many variants to this problem that could mess up a developer in an interview.

One constraint that could be used by an interviewer is to disallow sorting the input array. This constraint is a great way to check if a candidate has a deep understanding of data structures and their possible time complexities

What is Two Sum Problem? 

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

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

Solution

 For better understanding Let's break the question into steps-:

1. Given an array of integers.

2. Find the two numbers whose sum is equal to the integer input, and then return their indexes.

3. The return value should be an array with the indexes.

4. The same element at a given index cannot be used twice.

5. There exist one solution for the given array and target integer.

6. No sorting allowed.

Brute Force Solution

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function(nums, target) {
    let indexes = [];

    for(let i = 0; i < nums.length; i++){
       for(let j = i + 1; j < nums.length; j++){
          if (nums[i] + nums[j] === target) {
        indexes.push(i);
        indexes.push(j);
          }
       }
    }
    return indexes;
};

Time complexity:-

It works but if you look at code you’ll find it’s running a loop inside of a loop to find the target value. That puts us at a time complexity of O(n^2). slow !! . Not a big deal for a small input array and I could say the interviewer can expect an optimized solution for this type of problem and they will be looking for you to improve the time complexity.

 

Optimized solution using Hash Map

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function(array, target) {
  number = {};

  for (let i = 0; i < array.length; i += 1) {
    let difference = target - array[i];

    if (number[difference] !== undefined && number[difference] !== i) {
      return [i, number[difference]];
    } else {
      number[array[i]] = i;
    }
  }
};

Time Complexity-:

So while this one has two loops they’re not nested so the time complexity lands at O(n) power. Much better.

You can compare both code and their time Complexity.

you can also visit the below youTube link for solution

https://youtu.be/dRUpbt8vHpo