1/30 Days of Data Structure and Algorithm

Day 1

Title: Finding index that sums to a target in JavaScript (Four Method)

Introduction

This post explains four approaches for solving the classic algorithm problem: finding two indexes in an array that add up to a given target. We'll cover methods for both unsorted and sorted arrays:

• Brute Force (Unsorted)
• Hash Map (Unsorted)
• Binary Search (Sorted)
• Two Pointers (Sorted)

We'll analyze their time complexities and discuss their suitability for different scenarios.

The Problem:

Given an array of numbers (numberList) and a target sum (target), write a function that returns the indices of two numbers within the array that add up totarget. There should be only one such pair, and the first index (index1) must be less than the second index (index2).

Method 1: Brute Force (Unsorted - O(n^2) Time Complexity)

The brute force approach iterates through each element in the array and compares it with every subsequent element. If the sum matches the target, we return the corresponding indices.

function SumOfTwo(numberList, target) {
  for (let i = 0; i < numberList.length - 1; i++) {
    for (let j = i + 1; j < numberList.length; j++) {
      if (numberList[i] + numberList[j] === target) {
        return [i, j];
      }
    }
  }
  return null; // No pair found
}

Time Complexity: O(n^2) The nested loop results in quadratic time complexity. This approach can be slow for larger datasets.

Method 2: Hash Map (Unsorted - O(n) Time Complexity)

The hash map approach leverages a Map object to store seen numbers and their indices efficiently. We iterate through the array, calculating the complement (x)for each element (the number needed to reach the target). If the complement exists in the map (meaning we've seen its pair already), we return the indices of that pair. Otherwise, we add the current element and its index to the map.

function SumOfTwoMap(numberList, target) {
  const mapObj = new Map();
  for (let i = 0; i < numberList.length; i++) {
    const x = target - numberList[i];
    if (mapObj.has(x)) {
      return [mapObj.get(x), i];
    }
    mapObj.set(numberList[i], i);
  }
  return null; // No pair found
}

Time Complexity: O(n). The loop iterates through the array once, and accessing/updating the map is typically constant time with a good implementation. This makes the hash map approach significantly faster for larger arrays.

Method 3: Binary Search (Sorted - O(n log n) Time Complexity)

This approach leverages binary search to efficiently find the complement (x) of the current element that would add up to the target. However, it requires the array to be sorted beforehand. Here's the implementation:

function binarySearch(arr, target, startIndex) {
    let left = startIndex;
    let right = arr.length - 1;
    while (left <= right) {
      const mid = Math.floor((left + right) / 2);
      if (arr[mid] === target) {
        return mid;
      } else if (arr[mid] < target) {
        left = mid + 1;
      } else {
        right = mid - 1;
      }
    }
    return -1; 
  }
function twoSumBinarySearch(numberList, target) {
    numberList.sort((a, b) => a - b); // Sort the array
    for (let i = 0; i < numberList.length; i++) {
      const num2 = target - numberList[i];
      const complementIndex = binarySearch(numberList, num2, i + 1); //to avoid the duplicate pass it one increment
      if (complementIndex !== -1) {
        return [i, complementIndex];
      }
    }
    return null; // No pair found
}

Time Complexity: O(n log n) due to the binary search This can be efficient for large sorted arrays, else it adds the cost of sorting.

Method 4: Two Pointers (Sorted - O(n) Time Complexity)

This method exploits the sorted nature of the array by using two pointers, one at the beginning (i) and another at the end (j). We iterate while i is less than j:

• If numberList[i] + numberList[j] is equal to target, we return the indices.
• If the sum is less than target, we move the left pointer (i) forward to increase the sum.
• If the sum is greater than target, we move the right pointer (j) backward to decrease the sum.

function twoSumPointers(numberList, target) {
  let i = 0;
  let j = numberList.length - 1;
  while (i < j) {
    const sum = numberList[i] + numberList[j];
    if (sum === target) {
      return [i, j];
    } else if (sum < target) {
      i++;
    } else {
      j--;
    }
  }
  return null; // No pair found
}

Time Complexity: O(n). This approach leverages the sorted nature of the array and has a linear time complexity, making it very efficient for sorted arrays.

Example :

console.log(SumOfTwo([3, 9, 10, 12], 12)); // Output: [0, 1]
console.log(SumOfTwoMap([2, 11, 31, 50], 42)); // Output: [1, 2]
console.log(twoSumBinarySearch([2,7,11,15],22)) // Output : [1,3]
console.log(twoSumPointers([2,7,11,15],22)) // Output : [1,3]

Additional Considerations:

• Error handling: You can add checks to handle cases where no pair is found or the input is invalid.
• Optimization: For specific use cases, you might consider more advanced data structures or algorithms.