In this article we are going to solve two sum leetcode problem. Below is the two sum problem fully explained.

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 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,4], target = 6
Output: [1,2]

Example 3:

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

Constraints:

• 2 <= nums.length <= 10⁴
• -10⁹ <= nums[i] <= 10⁹
• -10⁹ <= target <= 10⁹
• Only one valid answer exists.

Now we know what our problem is, so we can think about the ways in which we can solve two sum problem.

First way in which we can solve two sum problem is using brute force, basically in this way we will be using two loops, one inside another so with this we can check all indexes one by one, but the time complexity of this approach will be O(n²) but this approach will consume less memory if we compare it two second approach which is mentioned below.

In second approach we will be using a HashMap to find our two sum problem solution, so basically by using HashMap we can easily check for the remaining number we want to check for, and this approach will consume a little bit extra memory because we’re using one extra data structure, but for large array input this approach works faster than approach one(brute force) because the time complexity of this approach is O(n).

Two sum leetcode solutions

1. Brute force

Algorithm

Below is the step by step process mentioned for brute force approach:

• Create a function, function will have two arguments array and target value.
• Iterate a loop on the array.
• Iterate second loop inside first loop on the array.
• Check if array[i] + array[j] == target.
• If condition is true then return [i, j].

Code

const BruteForce = (arr, target) => {
  for (let i = 0; i < arr.length; i++) {
    for (let j = i + 1; j < arr.length; j++) {
      if (arr[i] + arr[j] == target) {
        return [i, j]
      }
    }
  }
}

Explanation

Our BruteForce function is taking two arguments first: a unsorted array and a target, and inside our BruteForce function we’re iterating our first loop till the length of the array and in second loop we’re doing the same but our second loop is starting from the one step ahead of our first loop i+1, and inside second loop we’re doing the checking so we can identify the sum of both elements is equal to target or not and returning accordingly.

2. HashMap

HashMap is a key and value pair object in which you can store values to their corresponding key and also extract the value with the help of the key as well, so we are going to use the following data structure so we can make our code faster than the approach one.

Algorithm

Below is the step by step process we are going to follow for this approach

• Create a function, and it’ll be having two arguments: arr, target.
• Declare a variable hashMap of type new Map(), hashMap = new Map().
• Iterate over the array.
• Declare and initialize variable, diff = target – arr[i].
• Check if map have any diff key.
• True return back both indexes, return [hashMap[diff], i]
• False add key and value into map.

Code

const HashMap = (arr, target) => {
  let hashmap = new Map();
  for (let i = 0; i < arr.length; i++) {
    const diff = target - arr[i];
    if (hashmap.has(diff)) {
      return [hashmap.get(diff), i];
    }
    hashmap.set(arr[i], i);
  }
}

Explanation

In this two sum leetcode approach we’re using new data-structure so we can use the already processed information to check if that difference which we are looking for in the iteration exists inside our map or not if the difference exists then our HashMap function will returning back the indexes, and if key difference isn’t yet in the map then we’ll add the difference in our map so we can check again for same.

It’s like this we have [2,7,8,0] array and a target 9: In first iteration 9-2 = 7, at first there is no data in our map yet so it’ll set the 2 as key and 0 as value, Second iteration 9 – 7 = 2 , condition will check for key 2 inside our map and it will find the key inside our map so condition is true and will return indexes accordingly.

You can modify the code as per your need to make it more faster in terms of memory use because i mentioned in the starting of the article that first approach is slow but consuming less memory while second approach is faster but using little bit extra memory.

your comments are appreciated and if you wants to see your articles on this platform then please shoot a mail at this address kusingh@programmingeeksclub.com

Thanks for reading