Given a 0-based n x n integer matrix where grid[x][y] represents the height of the blocks in row x and column y. You can increase the height of any block (different per block), but the increased height of a block should not change the contour formed. Contour is the view of blocks from a distance in any direction, the task is to print the matrix after increasing the heights of the blocks without disturbing the contour.
Examples:
Input: grid = { { 4, 0, 9, 2 }, { 7, 6, 1, 8 }, { 9, 10, 3, 4 }, { 3, 2, 1, 8 } }
Output:
9 9 9 8
8 8 8 8
9 10 9 8
8 8 8 8
Explanation: The blocks viewed from top or bottom is: [9, 10, 9, 8]
The blocks viewed from left or right is: [9, 8, 10, 8]Input: grid = { { 0, 0, 1, 2 }, { 1, 1, 1, 1 }, { 0, 0, 0, 1 }, { 1, 1, 1, 0 } }
Output:
1 1 1 2
1 1 1 1
1 1 1 1
1 1 1 1
Explanation: The blocks viewed from top or bottom is: [1, 1, 1, 2]
The blocks viewed from left or right is: [2, 1, 1, 1]
Approach: To solve the problem follow the below idea:
For grid[i][j], it can’t be higher than the maximum of its row nor the maximum of its column. So the maximum increasing height for a block at (i, j) is min row[i], col[j]).
Below are the steps for the above approach:
- Initialize a resultant matrix say result[][] with the given matrix initially, to store the result.
- Initialize arrays say, row and col to store the maximum for each row and column.
- Iterate the matrix and store the maximum and minimum of each row and column in arrays row[] and col[]
- row[i] = max(row[i], grid[i][j])
- col[j] = max(col[j], grid[i][j])
- Run a loop till i = 0 to i < n and a nested loop till j = 0 to j < n and update result[i][j] = min(row[i], col[j]).
- Print the result matrix.
Below is the implementation of the above idea:
C++
#include <bits/stdc++.h>using namespace std;void inc_heights(vector<vector<int> >& grid){ int n = grid.size(); vector<int> col(n), row(n); vector<vector<int> > result(n, vector<int>(n)); for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { result[i][j] = grid[i][j]; } } for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { // Maximum for every row // and every column row[i] = max(row[i], grid[i][j]); col[j] = max(col[j], grid[i][j]); } } for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { result[i][j] = min(row[i], col[j]); } } for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { cout << result[i][j] << " "; } cout << endl; }}// Drivers codeint main(){ vector<vector<int> > grids = { { 4, 0, 9, 2 }, { 7, 6, 1, 8 }, { 9, 10, 3, 4 }, { 3, 2, 1, 8 } }; inc_heights(grids); return 0;}// This code is contributed by prasad264 |
Java
import java.io.*;public class GFG { public static void inc_heights(int[][] grid) { int n = grid.length; int[] col = new int[n], row = new int[n]; int[][] result = new int[n][n]; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { result[i][j] = grid[i][j]; } } for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { // Maximum for every row // and every column row[i] = Math.max(row[i], grid[i][j]); col[j] = Math.max(col[j], grid[i][j]); } } int res = 0; for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) result[i][j] = Math.min(row[i], col[j]); for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { System.out.print(result[i][j] + " "); } System.out.println(); } } // Drivers code public static void main(String[] args) { int grids[][] = { { 4, 0, 9, 2 }, { 7, 6, 1, 8 }, { 9, 10, 3, 4 }, { 3, 2, 1, 8 } }; inc_heights(grids); }} |
Python3
# Python3 code for the approach# Function to increment heights of the given griddef inc_heights(grid): n = len(grid) # Initialize arrays to store maximum values of rows and columns col = [0]*n row = [0]*n # Initialize the resulting grid result = [[0]*n for i in range(n)] # Copy the values of the original grid to the result for i in range(n): for j in range(n): result[i][j] = grid[i][j] # Find maximum value for every row and column for i in range(n): for j in range(n): row[i] = max(row[i], grid[i][j]) col[j] = max(col[j], grid[i][j]) # Set each element of the result grid to the minimum of corresponding row and column maximum for i in range(n): for j in range(n): result[i][j] = min(row[i], col[j]) # Print the resulting grid for i in range(n): for j in range(n): print(result[i][j], end=' ') print() # Driver codeif __name__ == '__main__': grids = [[4, 0, 9, 2], [7, 6, 1, 8], [9, 10, 3, 4], [3, 2, 1, 8]] inc_heights(grids) |
C#
using System;public class GFG { public static void inc_heights(int[, ] grid) { int n = grid.GetLength(0); int[] col = new int[n], row = new int[n]; int[, ] result = new int[n, n]; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { result[i, j] = grid[i, j]; } } for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { // Maximum for every row // and every column row[i] = Math.Max(row[i], grid[i, j]); col[j] = Math.Max(col[j], grid[i, j]); } } int res = 0; for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) result[i, j] = Math.Min(row[i], col[j]); for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { Console.Write(result[i, j] + " "); } Console.WriteLine(); } } // Drivers code public static void Main(string[] args) { int[, ] grids = { { 4, 0, 9, 2 }, { 7, 6, 1, 8 }, { 9, 10, 3, 4 }, { 3, 2, 1, 8 } }; inc_heights(grids); }}// This code is contributed by Prajwal Kandekar |
Javascript
// JavaScript code for the approach// Function to increment heights of the given gridfunction incHeights(grid) { const n = grid.length; // Initialize arrays to store maximum values of rows and columns const col = new Array(n).fill(0); const row = new Array(n).fill(0); // Initialize the resulting grid const result = new Array(n).fill(null).map(() => new Array(n).fill(null)); // Copy the values of the original grid to the result for (let i = 0; i < n; i++) { for (let j = 0; j < n; j++) { result[i][j] = grid[i][j]; } } // Find maximum value for every row and column for (let i = 0; i < n; i++) { for (let j = 0; j < n; j++) { row[i] = Math.max(row[i], grid[i][j]); col[j] = Math.max(col[j], grid[i][j]); } } // Set each element of the result grid to the minimum of corresponding row and column maximum for (let i = 0; i < n; i++) { for (let j = 0; j < n; j++) { result[i][j] = Math.min(row[i], col[j]); } } // Print the resulting grid for (let i = 0; i < n; i++) { console.log(result[i].join(" ")); }}// Driver codeconst grids = [ [4, 0, 9, 2], [7, 6, 1, 8], [9, 10, 3, 4], [3, 2, 1, 8]];// Function CallincHeights(grids); |
Output
9 9 9 8 8 8 8 8 9 10 9 8 8 8 8 8
Time Complexity: O(N2)
Auxiliary Space: O(N2)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Share your thoughts in the comments
