Discussion on: Daily Coding Problem #1

View post

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).

Serhii Sakal • Nov 25 '18

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

mæghith | Ramón FSM • Nov 25 '18

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

Can you explain why is that a problem?

Serhii Sakal • Nov 26 '18

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

Tiago Romero Garcia • Dec 4 '18 • Edited

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

Adi biton • Mar 17 '19

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

Minja Davidović • Nov 28 '18

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.