loading...

re: Daily Coding Problem #1 VIEW POST

FULL DISCUSSION
 

ATM I see 2 proposals for JS, here's another one taking advantage of the fact that JS arrays are sparse:

function twoNumbersEqual(inList, k) {
const lookup = [];

    for (const item of inList) {
        if (lookup[k - item]) {
            return true;
        }
        lookup[item]=k - item;
    }
    return false;
}

console.log (twoNumbersEqual ([10, 15, 3, 7], 17));

No need for fancy hash structures (because arrays in javascript are already hashes).

 

Yes, you could,
but if you look into lookup array, and imagen k = -1,
you will create an array with a lot of empty

[empty × 3, 52, empty × 3, 48, empty × 2, 45, empty × 4, 40]

lookup.length === 16

now, for example, we have input some array with big numbers

lookup.length > max.number in inList

 

So… you are saying that having very big sequence of empty space is a problem.

Can you explain why is that a problem?

There no such a big problem now,
it just my opinion,

but as suggested my friend
anyway, it's better using new Map || new Set for better performance.

jsperf.com/hashtable-vs-array

Here is my O(N) solution using Set:

function doTwoNumbersSumUpToK(list, k) {
    const visitedNumbers = new Set();
    for (let number of list) {
        visitedNumbers.add(number);
        if (visitedNumbers.has(k-number)) {
            return true;
        }
    }
    return false;
}

You should move line:
visitedNumbers.add(number);

after the if clause (otherwise the sums like 4+4=8 will be counted)

A compare i made for the Set vs HashTable
jsperf.com/add-to-k

 

there was actually an article recently that touched on the subject mentioned by Serhii Sakal dev.to/_codingblocks/when-is-an-ar...
I was wondering, why not just use an object instead of an array?
let's take a simple example, where you have something like this

const a = [1, 2];
a[1000] = 1000;

console.log(a);

and look at the size of a.
even with your example, the created lookup array is bigger than the given array, so you're using more memory than needed.

Code of Conduct Report abuse