algoadvance

Leetcode 807. Max Increase to Keep City Skyline

Problem Statement

You are given a n x n grid representing the height of buildings in a city. The heights of the buildings are represented by integers in the grid. The goal is to determine the maximum total sum that the height of the buildings can be increased without changing the city’s skyline from any viewpoint (north, south, east, or west).

Example:

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

Explanation: The skyline viewed from north and south is [9, 4, 8, 7], and the skyline viewed from east and west is [8, 7, 9, 3]. The grid after increasing the height of the buildings without affecting the skyline is:

gridNew = [[8, 4, 8, 7],
           [7, 4, 7, 7],
           [9, 4, 8, 7],
           [3, 3, 3, 3]]

The sum of the returned new grid is 35.

Clarifying Questions

  1. Can the grid contain negative values or is it guaranteed to have non-negative values?
  2. Is the grid always square, or can it be rectangular?

Code

Let’s start by writing the code to solve this problem in C++.

#include <vector>
#include <algorithm>
using namespace std;

class Solution {
public:
    int maxIncreaseKeepingSkyline(vector<vector<int>>& grid) {
        int n = grid.size();
        
        // Create two vectors to store the max heights of rows and columns
        vector<int> rowMax(n, 0);
        vector<int> colMax(n, 0);

        // Compute the max heights for each row and column
        for(int i = 0; i < n; ++i) {
            for(int j = 0; j < n; ++j) {
                rowMax[i] = max(rowMax[i], grid[i][j]);
                colMax[j] = max(colMax[j], grid[i][j]);
            }
        }

        // Calculate the maximum increase while maintaining the skyline
        int totalIncrease = 0;
        for(int i = 0; i < n; ++i) {
            for(int j = 0; j < n; ++j) {
                totalIncrease += min(rowMax[i], colMax[j]) - grid[i][j];
            }
        }

        return totalIncrease;
    }
};

Strategy

  1. Identify Max Heights: Create two vectors rowMax and colMax to identify the maximum height in each row and each column of the grid.
  2. Calculate Potential Increases: Iterate through each cell in the grid and determine the maximum increase it can sustain by taking the minimum of the corresponding maximum row height and column height.
  3. Sum the Increases: Sum up all the potential increases to get the answer.
  4. Return the Total Increase: Return the total sum of the increases.

Time Complexity

The time complexity of this solution is (O(n^2) ), where ( n ) is the dimension of the grid. This is because we have to traverse all the elements of the grid twice:

  1. First traversal to identify the rowMax and colMax.
  2. Second traversal to compute the potential increases for each element.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI