Two Sum

There are countless ways to approach this problem and optimize your solution. In this article, we’ll explore various strategies to tackle this problem. Let’s see the problem statement first.

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.

Here, you’re given an array of integers and a target number, and your task is to find two numbers in the array that add up to the target. It may seem like a simple task, but as the size of the array grows, so does the complexity of the problem. So buckle up, grab your favourite coding beverage, and let’s dive in!

---

Approach 1: Brute Force

1. In this case, we use two nested loops to iterate the array from left to right and check every possible pair of elements in the input array.

2. If the sum of the pair matches the target sum, we return the indices of those elements.

// ES6 Arrow Function
const twoSum = (nums, target) => {
    for (let i = 0; i < nums.length; i++) {
      for (let j = i + 1; j < nums.length; j++) {

        if (nums[i] + nums[j] === target) return [i, j];

      }
    }

    return null; 
  };

Time Complexity: O(N²)

Space Complexity: O(1)

---

Note: We can also use a built-in function Array.indexOf() in JavaScript to solve this problem.

Approach 1.1

1. Iterate through the input array nums from left to right, using a for loop.

2. Declare a variable difference and store the value of the difference between the target and the current element nums[i].

3. Use the Array.indexOf method to find the index of the difference in the nums array. Start the search from the index i+1, to avoid using the same element twice.

4. If the indexOf method returns a valid index, return an array containing the current index i and the found index.

5. If the indexOf method does not return a valid index, continue the loop to the next iteration.

6. If no two elements are found, return null as the result.

// ES6 Arrow Function
const twoSum = (nums, target) => {
    for (let i = 0; i < nums.length; i++) {
        const diff = target - nums[i];

        const j = nums.indexOf(diff, i + 1);

        if (j !== -1) return [i, j];
      }

    return null;
  }

Time Complexity: O(N²)

Space Complexity: O(1)

---

Approach 2: Sorting and Two Pointers

1. In this solution, we first sort the input array in non-decreasing order.

2. Then, we use two pointers, one at the beginning and one at the end of the array. We add the values of the pointers and check if the sum is equal to the target sum.

3. If it is, we return the indices of the two pointers.

4. If the sum is less than the target sum, we move the left pointer to the right. If it’s greater, we move the right pointer to the left.

// ES6 Arrow Function
 const twoSum = (nums, target) => {
    const sorted = [...nums].sort((a, b) => a - b);

    let left = 0;
    let right = nums.length - 1;

    while (left < right) {
      const sum = sorted[left] + sorted[right];

      if (sum === target) {
        // Find the indices in nums array
        const i = nums.indexOf(sorted[left]);
        let j = nums.indexOf(sorted[right]);
        if (i === j) { 
        // The same number is used twice.
          j = nums.indexOf(sorted[right], i + 1);
        }

        return [i, j];
      } else if (sum < target) {
        left++;
      } else {
        right--;
      }
    }

    return null;
  };

Time Complexity: O(N* Log(N))

Space Complexity: O(N)

---

Approach 3: Using Map

1. Iterate through the array and for each element and check if the element exists in the Map.

2. If it does, we return the indices of the current element and the complement.

3. If it doesn’t, we insert the current element and its index into the Map.

// ES6 Arrow Function
const twoSum = (nums, target) => {
    const map = new Map();

    for (let i = 0; i < nums.length; i++) {
      const diff = target - nums[i];

      if (map.has(diff)) {
        return [map.get(diff), i];
      }

      map.set(nums[i], i);
    }

    return null;
};

Time Complexity: O(N)

Space Complexity: O(N)

---

Note: In JavaScript, objects can be used as hash tables.

Approach 3.1: Using Objects

We follow the exact same procedure as in Approach 3 to solve the problem.

// ES6 Arrow Function
const twoSum = (nums, target) => {
    const hash = {};

    for (let i = 0; i < nums.length; i++) {
      const diff = target - nums[i];

      if (hash[diff] !== undefined) return [hash[diff], i];

      hash[nums[i]] = i;
    }

    return null;
};

Time Complexity: O(N)

Space Complexity: O(N)

---

And there you have it guys! We’ve explored different approaches, optimized our solutions, and hopefully had some fun along the way. I hope this article has provided you with valuable insights and helped you better understand the different approaches to solving this problem. Happy coding!

Problem - Leetcode 1