Max increase to keep city skyline

I'm trying to solve "Max Increase to Keep City Skyline" LeetCode problem.

Testing the algorithm locally, I manage to find the "skyline" for the "horizontal" view correctly ("horizontal" = the view you'd see by looking at the matrix's columns).

Though, for the "vertical" view ("vertical" = the view you'd see by looking at the matrix's rows), my last 2 values in the verticalView array aren't the correct ones, and I don't understand why.

I added the println to display the variable's values.

I don't understand why when verticalView[2] = 8 (this happens when i = 0, j = 2), i = 2 and j = 2, verticalView[2] has become 0.

import java.util.Arrays;

class Solution {
    public static int maxIncreaseKeepingSkyline(int[][] grid) {
        int[] verticalView = new int[grid.length];
        int[] horizontalView =  new int[grid[0].length];

        for (int i = 0; i < grid.length; i++) {
            verticalView[i] = 0;
            horizontalView[i] = 0;
            for (int j = 0; j < grid[0].length; j++) {
                boolean b = grid[i][j] > verticalView[j];
                System.out.println("verticalView[" + j + "] = " + verticalView[j]);

                if (grid[i][j] > verticalView[j] /* b */) verticalView[j] = grid[i][j];
                if (grid[i][j] > horizontalView[i]) horizontalView[i] = grid[i][j];

                System.out.println("grid[" + i + "][" + j + "] > verticalView[" + j + "] = " + b);
                System.out.println("grid[" + i + "][" + j + "] = " + grid[i][j]);
                System.out.println("verticalView[" + j + "] = " + verticalView[j]);
                System.out.println();
            }
        }
        System.out.println("Vertical view: " + Arrays.toString(verticalView));
        System.out.println("Horizontal view: " + Arrays.toString(horizontalView));

//        int[] verticalView = {9,4,8,7};
//        int[] horizontalView = {8,7,9,3};
        int sum = 0;

        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                while (grid[i][j] < verticalView[j] & grid[i][j] < horizontalView[i]) {
                    grid[i][j]++;
                    sum++;
                }
            }
        }

//        for (int i = 0; i < grid.length; i++) {
//            for (int j = 0; j < grid[0].length; j++) {
//                System.out.print(grid[i][j] + " ");
//            }
//            System.out.println();
//        }
        return sum;
    }

    public static void main(String[] args) {

        int[][] n = {{3, 0, 8, 4}, {2, 4, 5, 7}, {9, 2, 6, 3},{0, 3, 1, 0}};

        System.out.println("Solution: " + maxIncreaseKeepingSkyline(n));
    }
}

The mistake in your code is in:

verticalView[i] = 0;
horizontalView[i] = 0;

The default values of the array are zero in java.

You are changing values to zero even if they are updated to something other than zero.

Simplified Solution to the Problem:

import java.util.Arrays;
class Solution {
public static int maxIncreaseKeepingSkyline(int[][] grid) {
int[] verticalView = new int[grid.length];
int[] horizontalView =  new int[grid[0].length];
for (int i = 0; i < grid.length; i++) {
for (int j = 0; j < grid[0].length; j++) {
if (grid[i][j] > verticalView[j]) verticalView[j] = grid[i][j];
if (grid[i][j] > horizontalView[i]) horizontalView[i] = grid[i][j];
}
}
int sum = 0;
for (int i = 0; i < grid.length; i++) {
for (int j = 0; j < grid[0].length; j++) {
while (grid[i][j] < verticalView[j] & grid[i][j] < horizontalView[i]) {
grid[i][j]++;
sum++;
}
}
}
return sum;
}
public static void main(String[] args) {
int[][] n = {{3, 0, 8, 4}, {2, 4, 5, 7}, {9, 2, 6, 3},{0, 3, 1, 0}};
System.out.println("Solution: " + maxIncreaseKeepingSkyline(n));
}
}

Looks good!

We can also use Math.max() for just simplifying it a bit, nothing major though:

public class Solution {
public static final int maxIncreaseKeepingSkyline(
final int[][] grid
) {
int[] rows = new int[grid.length];
int[] cols = new int[grid.length];
for (int row = 0; row < grid.length; row++) {
for (int col = 0; col < grid.length; col++) {
rows[row] = Math.max(rows[row], grid[row][col]);
cols[col] = Math.max(cols[col], grid[row][col]);
}
}
int maxIncrease = 0;
for (int row = 0; row < grid.length; row++) {
for (int col = 0; col < grid.length; col++) {
maxIncrease += Math.min(rows[row], cols[col]) - grid[row][col];
}
}
return maxIncrease;
}
}