Max increase to keep city skyline

user_11629630 0
Viewed 139

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));
    }
}
algorithm java
2 Answers

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));
    }
}
user_136519780

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;
    }
}
user_65533280
Related