Leetcode 825 Solution

This article provides solution to leetcode question 825 (max-increase-to-keep-city-skyline)
Categories:
Tags:
Access this page by simply typing in "lcs 825" in your browser address bar if you have bunnylol configured.

https://leetcode.com/problems/max-increase-to-keep-city-skyline

Solution

class Solution {
public:
    int maxIncreaseKeepingSkyline(vector<vector<int>>& grid) {
        int m = grid.size();
        int n = grid[0].size();

        vector<int> a1(m);
        vector<int> a2(n);

        for (int i = 0; i < m; i++)
        {
            int high = 0;
            for (int j = 0; j < n; j++)
                high = max(high, grid[i][j]);
            a1[i] = high;
        }

        for (int j = 0; j < n; j++)
        {
            int high = 0;
            for (int i = 0; i < m; i++)
                high = max(high, grid[i][j]);
            a2[j] = high;
        }

        int ans = 0;
        for (int i = 0; i < m; i++)
        {
            for (int j = 0; j < n; j++)
            {
                int high = min(a1[i], a2[j]);
                ans += max(0, high - grid[i][j]);
            }
        }

        return ans;
    }
};