Two-sum problem in js - How to solve efficiently? | FAANG Interview Guide

Two-sum problem in js – How to solve efficiently? | FAANG Interview Guide

Post author:ajayverma128
Post published:August 13, 2023
Post category:Top150FAANG

Hello Readers,

Welcome to the first problem two-sum problem in the FAANG Interview guide series – a series of top 150 problem which are most commonly asked in FAANG and other software companies for software engineering job. This article will show the intuition and approaches to solve the famous Two Sum problem.

I’ll advise to solve these series problem in any online platform not locally e.g GFG, Spoj, Leetcode, HackerRank, HackerEarth, Codechef etc. Solving on anyone of these is necessary as you can show the rank and your profile in your resume.

Among these, I personally like the leetcode platform, its User interface is clean and feels peaceful 🙂 so, if you want you can try.

Lets start with the problem statement –

Problem Statement

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

Example 2

				
					Input: nums = [3,2,5], target = 7
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

Note: Only one valid answer exists.

Intuition

The Two Sum problem asks us to find two numbers x and y in an array s.t

x + y == target.

We need to return the indices of these two numbers.

Approaches

1. Brute Force Approach

consider every pair of elements and check if their sum equals the target. This can be done using nested loops, where the outer loop iterates from the first element to the second-to-last element, and the inner loop iterates from the next element to the last element. However, this approach has a time complexity of O(n^2).

Code

				
					var twoSum = function(nums, target) {
      let n = nums.length;

      for (let i = 0; i < n - 1; i++) {
          for (let j = i + 1; j < n; j++) {
              if (nums[i] + nums[j] === target]) {
                  return [i, j];
              }
          }
      }

      return [];
  };

  TC: O(n^2)
  SC: O(1)

2. Optimal Approach

A more efficient approach is to use a map. We can iterate through the array, and for each element, check if the target minus the current element exists in the map. If it does, we have found a valid pair of numbers. If not, we add the current element to the hash map.

Code

				
					var twoSum = function(nums, target) {
      let map = {};

      for (let i = 0; i < nums.length; i++) {
          if (!map[target - nums[i]]) {
              map[nums[i]] = i + 1;
              continue;
          }

          return [i, map[target - nums[i]] - 1];
      }

      return [];
  };

  TC: O(n)
  SC: O(n)