skip to Main Content

In javascript, I want to have a function with this declaration:
function sumOfTwoItemExist(arr:number[],total:number)=>boolean

the first parameter would be an array of numbers and the 2nd would be a number, now I want to return true if the sum of any pair of numbers in the passed array is equal to the passed number.
for example:
sumOfTwoItemExist([1,2,3,4],5) => true //1+4=5
sumOfTwoItemExist([1,2,3,4],8)=> false

what is the best and most optimized way to implement this array?
simply I tried to implement the function with a tow loop like this:

function sumOfTwoItemExist(arr,total) {
  for (let i = 0; i < arr.length - 1; i++) {
    for (let j = i + 1; j < arr.length - 1; j++) {
      if (arr[i] + arr[j] === total) {
        return true;
      }
    }
  }
  return false;
}
console.log(sumOfTwoItemExist([1, 2, 3, 4], 5)) // => true 1+4=5 
console.log(sumOfTwoItemExist([1, 2, 3, 4], 8)) // false

but I’m not sure it’s the most optimized way.
please share your suggestions.

2

Answers


  1. You can use 2-pointer algorithm here:

    If array is already sorted then you can skip sorting, this algo takes O(n) time complexity and O(1) space complexity.

    else it O(n log n) if it is not sorted

    function sumOfTowItemExist(arr: number[], total: number): boolean {
      const sortArr = arr.sort((a, b) => a - b);
      let leftPtr = 0,
        rightPtr = sortArr.length - 1;
    
      while (leftPtr < rightPtr) {
        let sum = sortArr[leftPtr] + sortArr[rightPtr];
        if (sum === total) return true;
        if (sum < total) leftPtr++;
        else rightPtr++;
      }
    
      return false;
    }
    
    
    const result = sumOfTowItemExist([1, 2, 3, 4], 5) // => true //1+4=5 
    
    console.log(result);
    Login or Signup to reply.
  2. An alternative solution to the previous answer is to create a mapping object which holds every number and their indexes from the array as key value pairs.

    Now with each iteration we check if the difference between the sum and the current number exists in the map, if it does that means that we have found our pair and we can return true, else return false.

    Here is the implementation:

    const sumOfTwoItemExist = function(nums, target) {
      const map = {}
    
      for (let i = 0, len = nums.length; i < len; i++) {
        const temp = target - nums[i]
        if (typeof map[temp] !== 'undefined') {
          return true;
        } else {
          map[nums[i]] = i
        }
      }
      return false
    }
    
    console.log(sumOfTwoItemExist([1, 2, 3, 4], 5)) // => true 1+4=5 
    console.log(sumOfTwoItemExist([1, 2, 3, 4], 8)) // false
    Login or Signup to reply.
Please signup or login to give your own answer.
Back To Top
Search