package com.fishercoder.solutions;

import com.fishercoder.common.utils.CommonUtils;

/**
 * 807. Max Increase to Keep City Skyline
 *
 * In a 2 dimensional array grid, each value grid[i][j] represents the height of a building located there.
 * We are allowed to increase the height of any number of buildings,
 * by any amount (the amounts can be different for different buildings). Height 0 is considered to be a building as well.
 * At the end, the "skyline" when viewed from all four directions of the grid, i.e. top, bottom, left, and right,
 * must be the same as the skyline of the original grid. A city's skyline is the outer contour of the rectangles
 * formed by all the buildings when viewed from a distance. See the following example.
 * What is the maximum total sum that the height of the buildings can be increased?
 *
 * Example:
 * Input: grid = [[3,0,8,4],[2,4,5,7],[9,2,6,3],[0,3,1,0]]
 * Output: 35
 * Explanation:
 * The grid is:
 * [ [3, 0, 8, 4],
 *   [2, 4, 5, 7],
 *   [9, 2, 6, 3],
 *   [0, 3, 1, 0] ]
 *
 * The skyline viewed from top or bottom is: [9, 4, 8, 7]
 * The skyline viewed from left or right is: [8, 7, 9, 3]
 * The grid after increasing the height of buildings without affecting skylines is:
 * gridNew = [ [8, 4, 8, 7],
 *             [7, 4, 7, 7],
 *             [9, 4, 8, 7],
 *             [3, 3, 3, 3] ]
 *
 * Notes:
 * 1 < grid.length = grid[0].length <= 50.
 * All heights grid[i][j] are in the range [0, 100].
 * All buildings in grid[i][j] occupy the entire grid cell: that is, they are a 1 x 1 x grid[i][j] rectangular prism.
 * */
public class _807 {
    public static class Solution1 {
        public int maxIncreaseKeepingSkyline(int[][] grid) {
            int size = grid.length;
            int[] horizontalLimits = new int[size];
            int[] verticalLimits = new int[size];
            for (int i = 0; i < size; i++) {
                int horizontalLimit = grid[i][0];
                for (int j = 1; j < size; j++) {
                    horizontalLimit = Math.max(horizontalLimit, grid[i][j]);
                }
                horizontalLimits[i] = horizontalLimit;
            }
            for (int j = 0; j < size; j++) {
                int verticalLimit = grid[0][j];
                for (int i = 1; i < size; i++) {
                    verticalLimit = Math.max(verticalLimit, grid[i][j]);
                }
                verticalLimits[j] = verticalLimit;
            }
            int increases = 0;
            for (int i = 0; i < size; i++) {
                for (int j = 0; j < size; j++) {
                    if (grid[i][j] != horizontalLimits[i] && grid[i][j] != verticalLimits[j]) {
                        increases += Math.min(horizontalLimits[i], verticalLimits[j]) - grid[i][j];
                    }
                }
            }
            return increases;
        }
    }
}

@@ -33,1553 +33,8 @@
 s;%0A%0A
-import com.fishercoder.common.utils.CommonUtils;%0A%0A/**%0A * 807. Max Increase to Keep City Skyline%0A *%0A * In a 2 dimensional array grid, each value grid%5Bi%5D%5Bj%5D represents the height of a building located there.%0A * We are allowed to increase the height of any number of buildings,%0A * by any amount (the amounts can be different for different buildings). Height 0 is considered to be a building as well.%0A * At the end, the %22skyline%22 when viewed from all four directions of the grid, i.e. top, bottom, left, and right,%0A * must be the same as the skyline of the original grid. A city's skyline is the outer contour of the rectangles%0A * formed by all the buildings when viewed from a distance. See the following example.%0A * What is the maximum total sum that the height of the buildings can be increased?%0A *%0A * Example:%0A * Input: grid = %5B%5B3,0,8,4%5D,%5B2,4,5,7%5D,%5B9,2,6,3%5D,%5B0,3,1,0%5D%5D%0A * Output: 35%0A * Explanation:%0A * The grid is:%0A * %5B %5B3, 0, 8, 4%5D,%0A *   %5B2, 4, 5, 7%5D,%0A *   %5B9, 2, 6, 3%5D,%0A *   %5B0, 3, 1, 0%5D %5D%0A *%0A * The skyline viewed from top or bottom is: %5B9, 4, 8, 7%5D%0A * The skyline viewed from left or right is: %5B8, 7, 9, 3%5D%0A * The grid after increasing the height of buildings without affecting skylines is:%0A * gridNew = %5B %5B8, 4, 8, 7%5D,%0A *             %5B7, 4, 7, 7%5D,%0A *             %5B9, 4, 8, 7%5D,%0A *             %5B3, 3, 3, 3%5D %5D%0A *%0A * Notes:%0A * 1 %3C grid.length = grid%5B0%5D.length %3C= 50.%0A * All heights grid%5Bi%5D%5Bj%5D are in the range %5B0, 100%5D.%0A * All buildings in grid%5Bi%5D%5Bj%5D occupy the entire grid cell: that is, they are a 1 x 1 x grid%5Bi%5D%5Bj%5D rectangular prism.%0A * */%0A
 publ

refactor 807