Short JavaScript O(n) solution using join, split, and reduce


  • 0
    var canPlaceFlowers = function(flowerbed, n) {
        const zeroes = flowerbed.join('').split('1');
        return zeroes.reduce((sum, p, i) => {
            if (i === 0 && i === zeroes.length - 1) {
                return (p.length + p.length % 2) / 2;
            }
            if (i === 0 || i === zeroes.length - 1) {
                return sum + (p.length - p.length % 2) / 2;
            }
            return sum + ((p.length || 2) - p.length % 2 - !(p.length % 2) * 2) / 2;
        }, 0) >= n;
    };
    
    • If the flowerbed is empty we can plant half of its even ceiling.
    • If an empty cluster is on an edge, we can plant half of its even floor.
    • If an empty cluster is not on an edge, we can plant half of its largest even less than itself.

    Here's a shorter and arguably less clear version:

    var canPlaceFlowers = function(flowerbed, n) {
        const zeroes = flowerbed.join('').split('1');
        return zeroes.reduce((sum, p, i) => {
            const l = i === 0, r = i === zeroes.length - 1, len = p.length;
            if (l | r) return sum + (len + len % 2 * Math.pow(-1, l ^ r)) / 2;
            return sum + ((len || 2) - len % 2 - !(len % 2) * 2) / 2;
        }, 0) >= n;
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.