Find pair with target sum in given array

0 / 330
Target Sum

Problem Statement

 

Given an array of sorted numbers and a target sum, find a pair in the array whose sum is equal to the given target.

Write a function to return the indices of the two numbers (i.e. the pair) such that they add up to the given target.

  Example 1:   Input: [1, 2, 3, 4, 6], target=6 Output: [1, 3]

Explanation: The numbers at index 1 and 3 add up to 6: 2+4=6

  Example 2:   Input: [2, 5, 9, 11], target=11 Output: [0, 2]

Explanation: The numbers at index 0 and 2 add up to 11: 2+9=11

 

Solution:

One way to solve this problem is to generate a map of array elements and their indices then loop through the array and check if the difference between target sum and current array element is present in the map. If found, push the difference which is found in the map, which essentially is the element present in the array and the current array element in the output array and return that output array.

 

Javascript code below:-

 
<script>

function const pair_with_targetsum (arr, target_sum) {
  // TODO: Write your code here
  var map = {};

  for (var index = 0; index < arr.length; index++) {
    if (typeof map[arr[index]] === 'undefined') {
      map[arr[index]] = index;
    }
  }

  for (var i = 0; i < arr.length; i++) {
    var remainder = target_sum - arr[i];
    if (map[remainder]) {
      return [i, map[remainder]];
    }
  }

  return [-1, -1];
}

document.write(pair_with_target_sum([1, 2, 3, 4, 6], 6)+'<br/>');
document.write(pair_with_target_sum([2, 5, 9, 11], 11)+'<br/>');

</script>
 

Time Complexity

 

The time complexity of the above algorithm will be O(N), where ‘N’ is the total number of elements in the given array.

 

Space Complexity

 

The space complexity will also be O(N), as, in the worst case, we will be pushing ‘N’ numbers in the Map.

 
 

Alternative solution

This approach is better in a sense that it doesn’t expect the array to be sorted. There is one more approach which we can use as below. 

The below solution uses binary search (2 pointers approach), given that array is sorted. If the array is not sorted, then we can sort the array first and use this approach.

We will start with one pointer pointing to the beginning of the array and another pointing at the end. At every step, we will see if the numbers pointed by the two pointers add up to the target sum. If they do, we have found our pair; otherwise, we will do one of two things:

  • If the sum of the two numbers pointed by the two pointers is greater than the target sum, this means that we need a pair with a smaller sum. So, to try more pairs, we can decrement the end-pointer.
 
  • If the sum of the two numbers pointed by the two pointers is smaller than the target sum, this means that we need a pair with a larger sum. So, to try more pairs, we can increment the start-pointer.
 

Here is the visual representation of this algorithm for Example-1:

Target Sum

Target sum in array

    Here is what our algorithm will look like for the above 2 pointers approach using Javascript:-   
<script>

function pair_with_target_sum(arr, targetSum) {
  let left = 0,
    right = arr.length - 1;

  while (left < right) {
    const currentSum = arr[left] + arr[right];
    if (currentSum === targetSum) {
      return [left, right];
    }

    if (targetSum > currentSum) {
      left += 1; // we need a pair with a bigger sum
    } else {
      right -= 1; // we need a pair with a smaller sum
    }
  }
  return [-1, -1];
}


document.write(pair_with_target_sum([1, 2, 3, 4, 6], 6)+'<br/>');
document.write(pair_with_target_sum([2, 5, 9, 11], 11)+'<br/>');

</script>
   

Time Complexity

 

The time complexity of the above algorithm will be O(N), where ‘N’ is the total number of elements in the given array.

 

Space Complexity

 

The algorithm runs in constant space O(1).

 

Comments

comments


An avid reader, responsible for generating creative content ideas for golibrary.co. His interests include algorithms and programming languages. Blogging is a hobby and passion.

Tags :

Related Posts