Max Increase to Keep City Skyline - Practice Coding Problems

Max Increase to Keep City Skyline - Problem

There is a city composed of n x n blocks, where each block contains a single building shaped like a vertical square prism. You are given a 0-indexed n x n integer matrix grid where grid[r][c] represents the height of the building located in the block at row r and column c.

A city's skyline is the outer contour formed by all the buildings 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.

Input & Output

Example 1 — Basic 2x2 Grid

$ Input: grid = [[3,0],[2,4]]

› Output: 4

💡 Note: Row maximums: [3,4], Column maximums: [3,4]. Building at (0,1) can increase from 0 to 3 (+3), building at (1,0) can increase from 2 to 3 (+1). Total: 3+1 = 4.

Example 2 — Larger Grid

$ Input: grid = [[0,0,0],[0,0,0],[0,0,0]]

› Output: 0

💡 Note: All buildings have height 0, so row and column maximums are all 0. No increases possible while maintaining skyline.

Example 3 — Mixed Heights

$ Input: grid = [[1,2,3],[4,5,6],[7,8,9]]

› Output: 9

💡 Note: Row maximums: [3,6,9], Column maximums: [7,8,9]. Each building can increase to min of its row/column limits.

Constraints

n == grid.length
n == grid[i].length
1 ≤ n ≤ 50
0 ≤ grid[i][j] ≤ 100

Visualization

Tap to expand

Understanding the Visualization

Input Grid

2D matrix representing building heights

Skyline Limits

Row and column maximums define height constraints

Optimal Heights

Each building can grow to min(row_max, col_max)

Key Takeaway

🎯 Key Insight: Each building's maximum height is constrained by the minimum of its row and column skyline limits

Asked in

G Google 25 M Microsoft 18 a Amazon 15 f Facebook 12

The key insight is that each building's maximum height is constrained by both its row and column skylines. The greedy approach calculates row/column maximums and sets each building to min(row_max, col_max). Time: O(n²), Space: O(n)

Common Approaches

Approach	Time	Space	Notes
✓ Greedy - Row/Column Max Constraints	O(n²)	O(n)	Calculate row and column maximums, then set each building to minimum of its row/column limits
Brute Force - Try All Heights	O(n⁴)	O(1)	Try every possible height increase for each building and check skyline constraints

Greedy - Row/Column Max Constraints — Algorithm Steps

Step 1: Calculate maximum height in each row (row skyline)
Step 2: Calculate maximum height in each column (column skyline)
Step 3: For each building, increase to min(row_max, col_max) - current_height

Visualization

Tap to expand

Step-by-Step Walkthrough

Calculate Skylines

Find row and column maximum heights

Apply Constraints

Each building limited by min(row_max, col_max)

Sum Increases

Add all valid height increases

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int solution(int** grid, int gridSize, int* gridColSize) {
    int n = gridSize;
    
    // Calculate row maximums (skyline from west/east)
    int* rowMax = (int*)calloc(n, sizeof(int));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (grid[i][j] > rowMax[i]) {
                rowMax[i] = grid[i][j];
            }
        }
    }
    
    // Calculate column maximums (skyline from north/south)
    int* colMax = (int*)calloc(n, sizeof(int));
    for (int j = 0; j < n; j++) {
        for (int i = 0; i < n; i++) {
            if (grid[i][j] > colMax[j]) {
                colMax[j] = grid[i][j];
            }
        }
    }
    
    // Calculate total possible increase
    int totalIncrease = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            // Max height without changing skyline
            int maxPossibleHeight = (rowMax[i] < colMax[j]) ? rowMax[i] : colMax[j];
            int increase = maxPossibleHeight - grid[i][j];
            totalIncrease += increase;
        }
    }
    
    free(rowMax);
    free(colMax);
    return totalIncrease;
}

int main() {
    // Simple parsing for demo - in real implementation, parse JSON properly
    int n = 2;
    int** grid = (int**)malloc(n * sizeof(int*));
    int* gridColSize = (int*)malloc(n * sizeof(int));
    
    for (int i = 0; i < n; i++) {
        grid[i] = (int*)malloc(n * sizeof(int));
        gridColSize[i] = n;
        for (int j = 0; j < n; j++) {
            scanf("%d", &grid[i][j]);
        }
    }
    
    printf("%d\n", solution(grid, n, gridColSize));
    
    for (int i = 0; i < n; i++) {
        free(grid[i]);
    }
    free(grid);
    free(gridColSize);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n²)

Two passes through n×n grid to calculate max values and increases

⚠ Quadratic Growth

Space Complexity

O(n)

Arrays to store row and column maximum values

⚡ Linearithmic Space

35.4K Views

Medium Frequency

~15 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Greedy - Row/Column Max Constraints — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler