brick-wall.js

/**
 * Brick Wall
 *
 * There is a brick wall in front of you. The wall is rectangular and has several rows of bricks.
 * The bricks have the same height but different width. You want to draw a vertical line from the
 * top to the bottom and cross the least bricks.
 *
 * The brick wall is represented by a list of rows. Each row is a list of integers representing the
 * width of each brick in this row from left to right.
 *
 * If your line go through the edge of a brick, then the brick is not considered as crossed. You need
 * to find out how to draw the line to cross the least bricks and return the number of crossed bricks.
 *
 * You cannot draw a line just along one of the two vertical edges of the wall, in which case the line
 * will obviously cross no bricks.
 *
 * Example:
 *
 * Input:
 * [[1,2,2,1],
 *  [3,1,2],
 *  [1,3,2],
 *  [2,4],
 *  [3,1,2],
 *  [1,3,1,1]]
 * Output: 2
 */

/**
 * @param {number[][]} wall
 * @return {number}
 */
const leastBricks = wall => {
  const map = {};
  let count = 0;

  for (let i = 0; i < wall.length; i++) {
    for (let j = 0, sum = 0; j < wall[i].length - 1; j++) {
      sum += wall[i][j];
      map[sum] = ~~map[sum] + 1;
      count = Math.max(count, map[sum]);
    }
  }

  return wall.length - count;
};

export { leastBricks };