Solving Leetcode 807. Max Increase to Keep City Skyline (medium)
My algo club is rad. Comprised of mostly recent-ish Flatiron School Software Engineering graduates, we meet on zoom, Monday — Friday from 9:00–11:00 am, to solve algorithms. Some sessions we may leave feeling a bit beat up, spending our time staring at and talking around challenging problems, knowing what we want to do, but still not quite knowing how to do it. Leaving open tabs of unresolved problems while we move forward with our day, dipping back into those windows periodically to check a new burst of inspiration; which, frustrating as that is, it’s why we meet up every day, because practice makes perfect, or better, or sometimes just good enough.
But other sessions! Oh, they can be so satisfying. Like this week, as a group code along of this Leetcode medium difficulty problem starts to run past 11:00, but we can feel that we’re close. Then, slowly as folks drop off to return to their lives and responsibilities outside of this zoom room, we find our errors and rearrange our approach to attain victory over the machine.
So let’s walk through this problem together, just like we did in #algo-club did earlier this week.
807. Max Increase to Keep City Skyline (medium)
https://leetcode.com/problems/max-increase-to-keep-city-skyline/
There is a city composed of
n x nblocks, where each block contains a single building shaped like a vertical square prism. You are given a 0-indexedn x ninteger matrixgridwheregrid[r][c]represents the height of the building located in the block at rowrand columnc.A city’s skyline is the the outer contour formed by all the building when viewing the side of the city from a distance. The skyline from each cardinal direction north, east, south, and west may be different.
We are allowed to increase the height of any number of buildings by any amount (the amount can be different per building). The height of a
0-height building can also be increased. However, increasing the height of a building should not affect the city's skyline from any cardinal direction.Return the maximum total sum that the height of the buildings can be increased by without changing the city’s skyline from any cardinal direction.
Example 1:
Input: grid = [[3,0,8,4],[2,4,5,7],[9,2,6,3],[0,3,1,0]]
Output: 35
Explanation: The building heights are shown in the center of the above image.
The skylines when viewed from each cardinal direction are drawn in red.
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] ]
Example 2:
Input: grid = [[0,0,0],[0,0,0],[0,0,0]]
Output: 0
Explanation: Increasing the height of any building will result in the skyline changing.
Constraints:
n == grid.length
n == grid[r].length
2 <= n <= 50
0 <= grid[r][c] <= 100
The first and probably most important thing to do is to take a moment and figure out just what this problem is asking us.
The image they included was invaluable in determining the actual request. When looking at a skyline from any direction, how tall can they build up directly behind each other without changing what it looks like currently?
Looking at the setup as a group, we just accepted the fact that we would be writing nested loops, as we would be comparing a current array index to the minimum height between a row and column max height.
Our original approach started with trying to determine the maximum buildable height of each row and column and compare the current index to that determined max as we traversed through, all in one giant, and eventually convoluted nested for loop.
While that intention was good, in that we were trying to preserve some semblance of care for time complexity, it eventually became clear that what we really needed to do was just allow whatever loops we felt needed to happen, to happen. So we broke it up!
First we decided to create two arrays. Since we were given an array of arrays holding our grid, we could visualize the layout, and knew we would need to traverse through and determine our horizontal (row) maximum for each inner array, and also determine our vertical (column) maximum.
So let’s first get some declarations out of the way.
Especially when working through tough, or confusing problems with potential for confusing variables, I like to start with longer, but very clear variable and or function names so that while your mind is more likely to wander down rabbit holes of confusion or edge cases, at least you know what you’re working with. Eventually, these names would likely be simplified but, while I’m actively doing the work, the clearer the variable, the clearer my path.
So now that I know my first move, let’s go ahead and fill our arrays that will hold the max height of each row and column.
Determining the max height of our rows is easy peasy. Each row is an inner array, so as we traverse through our first loop we can just use the handy Math.max to grab the max height in each array and push it to our new array, all while in our outer loop.
Getting the column max height is a little trickier and I’ll often do a little bit of manual walk-through just to make sure all my i’s and j’s are referring to what I want them to.
Sweet, right?! It’s awesome how just switching the orders of your i's and j's can allow you to traverse horizontally and vertically in 2d arrays all at the same time! (We discovered this trick when we were working through a sudoku validation algo previously).
Now that we have these two arrays we can go through the grid and compare each number to the smallest of the maximums in their row and column, then add up the difference between the two and add that to our howTallCanWeGo to determine total potential build height from all angles. Let’s get it done.
We’ll need to nest some loops again. As we walk through each horizontal array we’ll find the smallest ( Math.min ) maximum height of the row (which will always be at index i), to the max height of each column (which will be index j because we’ll need to change the index as we step through each inner array). And we’ll add the difference between the minimum-maximum minus the current height.
Then finally we’ll return howTallCanWeGo without changing the current skyline from every direction.
Whoo! We did it. Lot’s of looping, lots of minding our i's and j's, and lots of satisfaction at the end of the day! If you feel good about this one, maybe try their sudoku validator problem next! There are some fun similarities between the two so that once you get the concept here, it’s easier to apply there. https://leetcode.com/problems/valid-sudoku/
Stay tuned for a video walkthrough of the valid-sudoku problem coming soon to my YouTube channel!
