Max Increase to Keep City Skyline


  • 0

    Click here to see the full article post


  • 0
    B

    class Solution {
    public int maxIncreaseKeepingSkyline(int[][] grid) {
    int[] v = new int[grid.length];
    int[] h = new int[grid[0].length];
    int increase = 0;
    for(int i=0; i<grid.length; i++) {
    for(int j=0; j<grid[0].length; j++) {
    v[i] = Math.max(v[i], grid[i][j]);
    h[j] = Math.max(h[j], grid[i][j]);
    }
    }
    for(int i=0; i<grid.length; i++) {
    for(int j=0; j<grid[0].length; j++) {
    increase += Math.min(v[i], h[j])-grid[i][j];
    }
    }
    return increase;
    }
    }


  • 0
    H

    Maybe MxN, it did not say it has to be a square. "same as the skyline of the original grid", not "same from all four perspectives"


  • 0
    P

    Here is a JS Node version that outputs the newGrid for a sanity check:

    var http = require("http");
    var pageContent = "SkyLine
    ";

    var server = http.createServer().listen(8081);
    console.log("server running on 8081");

    var grid = [
    [3, 0, 8, 4],
    [2, 4, 5, 7],
    [9, 2, 6, 3],
    [0, 3, 1, 0]
    ]

    server.on('request', function (request, response) {

    response.writeHead(200, {'Content-Type': 'text/html'});
    response.write(pageContent)
    response.end();
    

    });

    var maxIncreaseKeepingSkyline = function(grid) {
    var size = grid[0].length
    var totInc = 0

      var colMaxes= [] //array or vertical max's
      var rowMaxes = []  //array or horizontal max's
      for (let i=0;i< size; i++) {
            colMaxes[i] = 0
            rowMaxes[i] = 0
      }
    
      var newGrid = []
       for (let row=0;row< size; row++) {
              newGrid[row] = []
         for (let col =0; col<size; col++) {
              newGrid[row][col]=0
          }
       }
    
    
      //figure out the maxes grid
          for (let row=0;row< size; row++) {
                   for (let col =0; col<size; col++) {
                        colMaxes[col] = Math.max(colMaxes[col], grid[row][col])
                        rowMaxes[row] = Math.max(rowMaxes[row], grid[row][col])
                   }
           }
    
      pageContent += "ColMaxes:  "+colMaxes.toString()+"<br>"
      pageContent += "RowMaxes:  "+rowMaxes.toString()+"<br>"
      //************
    
      pageContent += ("*******  LETS CALC NewGrid *******<br>")
    
      for (let row=0;row< size; row++) {
               for (let col =0; col<size; col++) {
                    let increase = Math.min(rowMaxes[row],colMaxes[col])-grid[row][col];
                    newGrid [row][col] = grid[row][col]+increase
                    totInc += increase
               }
    
              pageContent += "Row: "+row+":  "+newGrid[row]+"<br>"
              pageContent += "Partial newGrid: <br>"+printArray(newGrid)+"<br>"
      }  // next row
    
      //print new grid
      pageContent += "Total increase: "+totInc;
      return totInc;
    

    }; //close function

    function printArray(xgrid) {
    let printGrid = "";
    let size = xgrid[0].length
    for (let r=0;r< size; r++) {
    //console.log("Here is row "+row+": "+grid[row])
    printGrid += "row "+r+": "+xgrid[r]+"
    "
    }
    return printGrid
    }

    maxIncreaseKeepingSkyline(grid)


Log in to reply
 

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