-
Notifications
You must be signed in to change notification settings - Fork 1
New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
[Leetcode] 807. Max Increase to Keep City Skyline #27
Comments
const grid = [[3, 0, 8, 4], [2, 4, 5, 7], [9, 2, 6, 3], [0, 3, 1, 0]];
let count = 0;
for (let i = 0; i < grid.length; i++) {
for (let j = 0; j < grid[i].length; j++) {
let skylineNumVertical = 0;
let skylineNumHorizantal = 0;
for (let y = 0; y < grid.length; y++) {
if (grid[y][j] > skylineNumVertical) {
skylineNumVertical = grid[y][j];
}
}
for (let x = 0; x < grid[i].length; x++) {
if (grid[i][x] > skylineNumHorizantal) {
skylineNumHorizantal = grid[i][x];
}
}
let skylineNum
if (skylineNumHorizantal > skylineNumVertical) {
skylineNum = skylineNumVertical
} else {
skylineNum = skylineNumHorizantal
}
if (grid[i][j] >= skylineNum) {
console.log('COOL')
} else {
count = count + (skylineNum - grid[i][j])
}
}
}
console.log(count); This is O(n^3). |
/**
* @param {number[][]} grid
* @return {number}
*/
var maxIncreaseKeepingSkyline = function (grid) {
const vertical = []
const horizantal = []
let count = 0
for (let i = 0; i < grid.length; i++) {
let skylineNumVertical = 0
let skylineNumHorizantal = 0
for (let y = 0; y < grid[i].length; y++) {
if (grid[i][y] > skylineNumVertical) {
skylineNumVertical = grid[i][y]
}
}
vertical.push(skylineNumVertical)
for (let x = 0; x < grid[i].length; x++) {
if (grid[x][i] > skylineNumHorizantal) {
skylineNumHorizantal = grid[x][i]
}
}
horizantal.push(skylineNumHorizantal)
}
for (let j = 0; j < grid.length; j++) {
for (let r = 0; r < grid[j].length; r++) {
let skylineNum
if (vertical[j] > horizantal[r]) {
skylineNum = horizantal[r]
} else {
skylineNum = vertical[j]
}
if (grid[j][r] >= skylineNum) {} else {
count = count + (skylineNum - grid[j][r])
}
}
}
return count
} This is O(n^2). My runtime on Leetcode is 96% faster than other solutions, so I'm very happy with this. |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Link: https://leetcode.com/problems/max-increase-to-keep-city-skyline/
In a 2 dimensional array grid, each value grid[i][j] represents the height of a building located there. We are allowed to increase the height of any number of buildings, by any amount (the amounts can be different for different buildings). Height 0 is considered to be a building as well.
At the end, the "skyline" when viewed from all four directions of the grid, i.e. top, bottom, left, and right, must be the same as the skyline of the original grid. A city's skyline is the outer contour of the rectangles formed by all the buildings when viewed from a distance. See the following example.
What is the maximum total sum that the height of the buildings can be increased?
The text was updated successfully, but these errors were encountered: