As some of you may know, it is hiring season so I decided that it’s time to start leetcoding. And for those who are nearing graduation, you are all aware that we should be doing as many problems as we can, right? Seeing more problems means seeing more perspectives and ideas. Or so I thought, simply doing more problems is good, but we also need to practice the explanation of how we solve our problems. I will now try my best in doing just that.
The problem I will be discussing is #807. Max Increase to Keep City Skyline. The problem is set in a city that is composed of n x n (1-indexed) blocks, where each block is a vertical column with a certain height that is represented in an integer matrix of n x n that we will call the grid. This is a square city that has the cardinal directions of North, East, South, West. A city’s skyline is the outer contour formed by all the buildings(blocks) when the city is viewed from any direction e.g. North, South. The skyline for each side may be different. Our goal is to maximize the height of each building without changing the skyline.
To begin to solve the problem, let’s take a look at how we find the skyline. Suppose I am standing north and I face south. I see a building with a maximum height of 9 in column 1. This is the skyline. Alternatively, this means the skyline is the same if I’m standing South because 9 is the tallest building in column 1. With that same thinking, I can now also find the skyline for each column and each row in the city.
Let’s begin by thinking about 1 row. To maximize the height of one row, all the other buildings in that row will be increased up to the max height/skyline of the row. Similarly this can be done for columns as well. Let’s now pivot to how we can find the height of each city block.
Let’s try some scenarios to find the answer. Suppose I am at row 1, col 1 and the maximum height in row 1 is 8 and the maximum height in col 1 is 9. If we increase, the city height’s block to 9. We will have now changed the maximum height in row 1 and thus the skyline from east/west is changed. This is a violation of the requirements. So 8 is the maximum that we can increase the city block. From that, we can see that the height of each city block is determined by the minimum of the maximums of the rows and columns.
To code it, we only need to find the max of each row and column. The most obvious way would be to iterate through the city once to find the max of each row. Then, iterate through the city again. If you’ll notice, we iterated through the city two times to find the maximums for each. But, it is actually possible to record the maximum of each row and column simultaneously. To explain the details and the rest of the solution, it would require too many words so I will end it here.
I hope that wasn’t too much of a bore. I am always open to feedback.
Hi, this is a comment.
To get started with moderating, editing, and deleting comments, please visit the Comments screen in the dashboard.
Commenter avatars come from Gravatar.