How can I optimize for loop?

November 3, 2022

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 and target, output is true or false.

Here`s my code.

// pseudo code in js
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..

>Solution :

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;
}