-1

Problem: Return true if the sum of two different elements of the array equals the target, otherwise return false
I want to optimize the time complexity of this code. Now, code has O(n^2) complexity. How can I reduce complexity? input is unsorted array(number[]) and target(number), output is true or false.

Here`s my code.

function find(arr, target) {
    for(let i = 0; i < arr.length; i++){
        for(let j = i + 1; j < arr.length; j++){
            if(target === (arr[i]+arr[j])){
                return true;
            }
        }
    }
    return false;
}

I think hint is unsorted array. And I don`t know at all..

chogyejin
  • 3
  • 4

2 Answers2

3

I don't think your particular implementation can be simplified, however if you first sort the array you can take a two-pointer approach to figure out if the target can be found, resulting in O(n log n) complexity.

function find(arr, target) {
    arr.sort();
    let start = 0;
    let end = arr.length - 1;
    while(start < end) {
        if(arr[start] + arr[end] > target) {
            end--;
        } else if(arr[start] + arr[end] < target) {
            start++;
        } else {
            return true;
        }
    }
    return false;
}
Marko Durasinovic
  • 94
  • 6
1

Actually you don't need to sort the array which takes O(nlogn), but you can solve it in linear runtime O(n+n).

Idea:

  1. First build a dictionary from array so later you can search for a key in O(1) time.
  2. then iterate through your array and find out reminder is in dictionary or not, if the reminder is found that's the answer.

for example: arr = [1, 5, 6] and target = 6;

so when you are on 0th position then

let reminder = target - arr[0];
let reminder = 6 - 1 = 5

so you just need to look your array has 5 or not, that's why you need to build a dictionary for looking up in O(1).

const find = (arr, dict, target) => { // then iterating through array which takes O(n)
  let found = false;
  for (let i = 0; i < arr.length; ++i) {
    const reminder = target - arr[i]; //just need to find out reminder is already in array or not
    if (reminder in dict && dict[reminder] != i) {
      found = true;
      break;
    }
  }

  return found;
}

const arr = [-3, 1, 10, 9, 15, 100];

const refDict = arr.reduce((currDict, val, i) => { //first create a dictionary which takes O(n)
  return {
    ...currDict,
    [val]: i
  };
}, {});

const isFound = find(arr, refDict, 20);
console.log(isFound);

Hope it helps!

Asraf
  • 1,322
  • 2
  • 12
  • That`s faster than two pointer patterns! But I have a some question. When arr is `[-3,1,10,9,15,100]` and target is `20`, I think `find` returns false but return true. How do you think this case? – chogyejin Nov 03 '22 at 21:13
  • 2
    Thanks for pointing it out it's rather easy, I forgot to handle this case and it doesn't make sense to use the same element twice. so we just need to add an extra guard here as`if (reminder in dict && dict[reminder] != i)`. – Asraf Nov 03 '22 at 23:28