Simple JavaScript O(n) using map


  • 0

    The most frequent prefix sum location crosses the fewest bricks:

    var leastBricks = function(wall) {
        const counts = {};
        let max = 0;
        for (let row of wall) {
            let sum = 0;
            for (let i = 0; i < row.length - 1; i++) {
                sum += row[i];
                counts[sum] = (counts[sum] || 0) + 1;
                max = Math.max(max, counts[sum]);
            }
        }
        return wall.length - max;
    };
    

    This is O(n) in the number of bricks.


Log in to reply
 

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