Given a square matrix of size N*N using numbers 1 to N^2, the task is to find the maximum of minimums of each layer of the matrix.
The layers of the matrix are the boundary elements of the sub-matrix starting at (i, i) and ending at (N – i + 1, N – i + 1), where 1<= i<= ceil(N/2).
Examples:
Input: Below is the given matrix:
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16
Output: 6
Explanation: The layers are {1, 2, 3, 4, 8, 12, 16, 15, 14, 13, 9, 5} with minimum 1 and {6, 7, 10, 11} with minimum 6. The maximum of 1 and 6 is 6.Input: Below is the given matrix:
1 2 3
4 30 5
1 2 3
Output: 30
Explanation: The layers are {1, 2, 3, 5, 3, 2, 1, 4, 1} with minimum 1 and {30} with minimum 30. The maximum of 1 and 30 is 30.
Approach: The idea is to observe carefully, for the ith layer, the elements of the top, left, right and bottom boundary are at indexes:
- top boundary is at indexes (i, j)
- left boundary is at indexes (j, i)
- right boundary is at indexes (j, n – i + 1)
- bottom boundary is at indexes (n – i + 1, j), where i <= j <= n – i + 1
Thus, find the minimums of each layer and store the maximum of these minimums.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include<bits/stdc++.h>using namespace std;// Function to return the minimum// of the boundary elementsint getBoundaryMin(int a[][4], int n, int index){ int min1 = INT_MAX; for(int i = index; i < n - index; i++) { // Top boundary min1 = min(min1, a[index][i]); // Left boundary min1 = min(min1, a[i][index]); // Right boundary min1 = min(min1, a[i][n - index - 1]); // Bottom boundary min1 = min(min1, a[n - index - 1][i]); } return min1;}// Function to find the maximum of// minimums of all layersvoid MaximumOfMinimum(int a[][4], int n){ // Calculate the layers int layers = n / 2 + n % 2; int max1 = INT_MIN; // Iterate for all the layers for(int i = 0; i < layers; i++) { // Find maximum max1 = max(max1, getBoundaryMin(a, n, i)); } // Print the answer cout << (max1);}// Driver Codeint main(){ // Initialize the matrix int a[][4] = { { 1, 2, 3, 4 }, { 5, 6, 7, 8 }, { 9, 10, 11, 12 }, { 13, 14, 15, 16 } }; int n = sizeof(a) / sizeof(a[0]); // Function call MaximumOfMinimum(a, n);}// This code is contributed by chitranayal |
Java
// Java Program for the above approachclass GFG { // Function to return the minimum // of the boundary elements static int getBoundaryMin(int a[][], int n, int index) { int min = Integer.MAX_VALUE; for (int i = index; i < n - index; i++) { // Top boundary min = Math.min( min, a[index][i]); // Left boundary min = Math.min( min, a[i][index]); // Right boundary min = Math.min( min, a[i][n - index - 1]); // Bottom boundary min = Math.min( min, a[n - index - 1][i]); } return min; } // Function to find the maximum of // minimums of all layers static void MaximumOfMinimum( int a[][], int n) { // Calculate the layers int layers = n / 2 + n % 2; int max = Integer.MIN_VALUE; // Iterate for all the layers for (int i = 0; i < layers; i++) { // Find maximum max = Math.max( max, getBoundaryMin(a, n, i)); } // Print the answer System.out.print(max); } // Driver Code public static void main(String[] args) { // Initialize the matrix int a[][] = { { 1, 2, 3, 4 }, { 5, 6, 7, 8 }, { 9, 10, 11, 12 }, { 13, 14, 15, 16 } }; int n = a.length; // Function call MaximumOfMinimum(a, n); }} |
Python3
# Python3 program for the above approachimport sys# Function to return the minimum# of the boundary elementsdef getBoundaryMin(a, n, index): min1 = sys.maxsize for i in range(index, n - index): # Top boundary min1 = min(min1, a[index][i]) # Left boundary min1 = min(min1, a[i][index]) # Right boundary min1 = min(min1, a[i][n - index - 1]) # Bottom boundary min1 = min(min1, a[n - index - 1][i]) return min1# Function to find the maximum of# minimums of all layersdef MaximumOfMinimum(a, n): # Calculate the layers layers = n // 2 + n % 2 max1 = -sys.maxsize - 1 # Iterate for all the layers for i in range(0, layers): # Find maximum max1 = max(max1, getBoundaryMin(a, n, i)) # Print the answer print(max1)# Driver Code # Initialize the matrixa = [ [ 1, 2, 3, 4 ], [ 5, 6, 7, 8 ], [ 9, 10, 11, 12 ] , [ 13, 14, 15, 16 ] ] n = len(a)# Function callMaximumOfMinimum(a, n)# This code is contributed by sanjoy_62 |
C#
// C# program for the above approachusing System;class GFG{// Function to return the minimum// of the boundary elementsstatic int getBoundaryMin(int[,]a, int n, int index){ int min = int.MaxValue; for(int i = index; i < n - index; i++) { // Top boundary min = Math.Min(min, a[index, i]); // Left boundary min = Math.Min(min, a[i, index]); // Right boundary min = Math.Min(min, a[i, n - index - 1]); // Bottom boundary min = Math.Min(min, a[n - index - 1, i]); } return min;}// Function to find the maximum of// minimums of all layersstatic void MaximumOfMinimum(int[,]a, int n){ // Calculate the layers int layers = n / 2 + n % 2; int max = int.MinValue; // Iterate for all the layers for(int i = 0; i < layers; i++) { // Find maximum max = Math.Max(max, getBoundaryMin(a, n, i)); } // Print the answer Console.Write(max);}// Driver Codepublic static void Main(String[] args){ // Initialize the matrix int[,]a = { { 1, 2, 3, 4 }, { 5, 6, 7, 8 }, { 9, 10, 11, 12 }, { 13, 14, 15, 16 } }; int n = a.GetLength(0); // Function call MaximumOfMinimum(a, n);}}// This code is contributed by 29AjayKumar |
Javascript
<script>// Javascript program for the above approach// Function to return the minimum// of the boundary elementsfunction getBoundaryMin(a, n, index){ min1 = 1000000000; for(var i = index; i < n - index; i++) { // Top boundary min1 = Math.min(min1, a[index][i]); // Left boundary min1 = Math.min(min1, a[i][index]); // Right boundary min1 = Math.min(min1, a[i][n - index - 1]); // Bottom boundary min1 = Math.min(min1, a[n - index - 1][i]); } return min1;} // Function to find the maximum of// minimums of all layersfunction MaximumOfMinimum(a, n){ // Calculate the layers var layers = parseInt(n / 2) + n % 2; var max1 = -1000000000; // Iterate for all the layers for(var i = 0; i < layers; i++) { // Find maximum max1 = Math.max(max1, getBoundaryMin(a, n, i)); } // Print the answer document.write(max1);}// Driver Code// Initialize the matrixvar a = [ [ 1, 2, 3, 4 ], [ 5, 6, 7, 8 ], [ 9, 10, 11, 12 ], [ 13, 14, 15, 16 ] ];var n = a.length;// Function callMaximumOfMinimum(a, n);// This code is contributed by itsok</script> |
Output:
6
Time Complexity: O(N2)
Auxiliary Space: O(1)
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!