singularity

singularity 🔎

846. Hand of Straights

O(n log n)

The code first sorts the input array which takes O(n log n) time complexity. Then it iterates through the groups of size k, which would take O(n) time. Therefore, the overall time complexity is O(n log n).

see also

• [LC-1296-divide-array-in-sets-of-k-consecutive-numbers]

var isNStraightHand = function (hand, groupSize) {
    if (hand.length % groupSize) return false;

    let gp = Array.from({
        length: hand.length / groupSize
    }, () => []);

    let s = hand.sort((a, b) => a - b);

    for (g of gp) {
        while (g.length < groupSize) {
            if (!g.length) {
                g.push(s[0]);
                s.splice(0, 1);
            } else {
                let val = s.find(x => x > g[g.length - 1]);
                g.push(val);
                s.splice(s.indexOf(val), 1);
            }
        }
    }

    let check = true;

    for(g of gp){
        if(g.length!=groupSize){
            check = false;
        }

        for(let i = 1; i<g.length; i++){
            if(g[i] != g[i-1]+1){
                check = false;
            }
        }
    }

    return check;
};