Maximize minimum of array generated by maximums of same indexed elements of two rows of a given Matrix
Given a matrix mat[][] of N rows and M columns, the task is to choose any two rows(i, j) (0 ? i, j ? N – 1) and construct a new array A[] of size M, where A[k] = max(mat[i][k], mat[j][k]) such that minimum of A[] is maximum possible.
Examples:
Input: mat[][] = {{5, 0, 3, 1, 2}, {1, 8, 9, 1, 3}, {1, 2, 3, 4, 5}, {9, 1, 0, 3, 7}, {2, 3, 0, 6, 3}, {6, 4, 1, 7, 0}}
Output: 3
Explanation:
Choose two rows i = 0 and j = 4. Then, A[] = {5, 3, 3, 6, 3} and min(A[]) is 3, which is maximum possible.Input: mat[][] = {{2, 13, 41, 5}, {91, 11, 10, 13}, {12, 3, 28, 6}}
Output: 13
Explanation:
Choose two rows i = 0 and j = 1. Then, A[] = {91, 13, 41, 13} and min(A[]) is 13, which is maximum possible.
Approach: Follow the steps below to solve the problem:
- Initialize a variable global_max with INT_MAX, which stores the maximum of a minimum of array constructed from any two rows of mat[][].
- Iterate through every possible combination of rows i and j, and find the minimum of array constructed from them as row_min.
- In each iteration, update global_max to the maximum of row_min and itself.
- After the above steps, print the value of global_max as the result.
Below is the implementation of the above approach:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function to find the maximum of // minimum of array constructed from // any two rows of the given matrix int getMaximum( int N, int M, vector<vector< int > > mat) { // Initialize global max as INT_MIN int global_max = INT_MIN; // Iterate through the rows for ( int i = 0; i < N; i++) { // Iterate through remaining rows for ( int j = i + 1; j < N; j++) { // Initialize row_min as INT_MAX int row_min = INT_MAX; // Iterate through the column // values of two rows for ( int k = 0; k < M; k++) { // Find max of two elements int m = max(mat[i][k], mat[j][k]); // Update the row_min row_min = min(row_min, m); } // Update the global_max global_max = max(global_max, row_min); } } // Print the global max return global_max; } // Driver Code int main() { // Given matrix mat[][] vector<vector< int > > mat = { { 5, 0, 3, 1, 2 }, { 1, 8, 9, 1, 3 }, { 1, 2, 3, 4, 5 }, { 9, 1, 0, 3, 7 }, { 2, 3, 0, 6, 3 }, { 6, 4, 1, 7, 0 } }; // Given number of rows and columns int N = 6, M = 5; // Function Call cout << getMaximum(N, M, mat); return 0; } |
Java
// Java program for the above approach import java.io.*; import java.util.*; class GFG{ // Function to find the maximum of // minimum of array constructed from // any two rows of the given matrix static int getMaximum( int N, int M, int [][] mat) { // Initialize global max as INT_MIN int global_max = Integer.MIN_VALUE; // Iterate through the rows for ( int i = 0 ; i < N; i++) { // Iterate through remaining rows for ( int j = i + 1 ; j < N; j++) { // Initialize row_min as INT_MAX int row_min = Integer.MAX_VALUE; // Iterate through the column // values of two rows for ( int k = 0 ; k < M; k++) { // Find max of two elements int m = Math.max(mat[i][k], mat[j][k]); // Update the row_min row_min = Math.min(row_min, m); } // Update the global_max global_max = Math.max(global_max, row_min); } } // Print the global max return global_max; } // Driver Code public static void main(String[] args) { // Given matrix mat[][] int [][] mat = { { 5 , 0 , 3 , 1 , 2 }, { 1 , 8 , 9 , 1 , 3 }, { 1 , 2 , 3 , 4 , 5 }, { 9 , 1 , 0 , 3 , 7 }, { 2 , 3 , 0 , 6 , 3 }, { 6 , 4 , 1 , 7 , 0 } }; // Given number of rows and columns int N = 6 , M = 5 ; // Function Call System.out.println(getMaximum(N, M, mat)); } } // This code is contributed by akhilsaini |
Python3
# Python3 program for the above approach import sys # Function to find the maximum of # minimum of array constructed from # any two rows of the given matrix def getMaximum(N, M, mat): # Initialize global max as INT_MIN global_max = - 1 * (sys.maxsize) # Iterate through the rows for i in range ( 0 , N): # Iterate through remaining rows for j in range (i + 1 , N): # Initialize row_min as INT_MAX row_min = sys.maxsize # Iterate through the column # values of two rows for k in range ( 0 , M): # Find max of two elements m = max (mat[i][k], mat[j][k]) # Update the row_min row_min = min (row_min, m) # Update the global_max global_max = max (global_max, row_min) # Print the global max return global_max # Driver Code if __name__ = = '__main__' : # Given matrix mat[][] mat = [ [ 5 , 0 , 3 , 1 , 2 ], [ 1 , 8 , 9 , 1 , 3 ], [ 1 , 2 , 3 , 4 , 5 ], [ 9 , 1 , 0 , 3 , 7 ], [ 2 , 3 , 0 , 6 , 3 ], [ 6 , 4 , 1 , 7 , 0 ] ] # Given number of rows and columns N = 6 M = 5 # Function Call print (getMaximum(N, M, mat)) # This code is contributed by akhilsaini |
C#
// C# program for the above approach using System; class GFG{ // Function to find the maximum of // minimum of array constructed from // any two rows of the given matrix static int getMaximum( int N, int M, int [,] mat) { // Initialize global max as INT_MIN int global_max = int .MinValue; // Iterate through the rows for ( int i = 0; i < N; i++) { // Iterate through remaining rows for ( int j = i + 1; j < N; j++) { // Initialize row_min as INT_MAX int row_min = int .MaxValue; // Iterate through the column // values of two rows for ( int k = 0; k < M; k++) { // Find max of two elements int m = Math.Max(mat[i, k], mat[j, k]); // Update the row_min row_min = Math.Min(row_min, m); } // Update the global_max global_max = Math.Max(global_max, row_min); } } // Print the global max return global_max; } // Driver Code public static void Main() { // Given matrix mat[][] int [,] mat = { { 5, 0, 3, 1, 2 }, { 1, 8, 9, 1, 3 }, { 1, 2, 3, 4, 5 }, { 9, 1, 0, 3, 7 }, { 2, 3, 0, 6, 3 }, { 6, 4, 1, 7, 0 } }; // Given number of rows and columns int N = 6, M = 5; // Function Call Console.WriteLine(getMaximum(N, M, mat)); } } // This code is contributed by akhilsaini |
Javascript
<script> // JavaScript program for the above approach // Function to find the maximum of // minimum of array constructed from // any two rows of the given matrix function getMaximum(N, M, mat) { // Initialize global max as let_MIN let global_max = Number.MIN_VALUE; // Iterate through the rows for (let i = 0; i < N; i++) { // Iterate through remaining rows for (let j = i + 1; j < N; j++) { // Initialize row_min as let_MAX let row_min = Number.MAX_VALUE; // Iterate through the column // values of two rows for (let k = 0; k < M; k++) { // Find max of two elements let m = Math.max(mat[i][k], mat[j][k]); // Update the row_min row_min = Math.min(row_min, m); } // Update the global_max global_max = Math.max(global_max, row_min); } } // Print the global max return global_max; } // Driver code // Given matrix mat[][] let mat = [ [ 5, 0, 3, 1, 2 ], [ 1, 8, 9, 1, 3 ], [ 1, 2, 3, 4, 5 ], [ 9, 1, 0, 3, 7 ], [ 2, 3, 0, 6, 3 ], [ 6, 4, 1, 7, 0 ] ]; // Given number of rows and columns let N = 6, M = 5; // Function Call document.write(getMaximum(N, M, mat)); // This code is contributed by avijitmondal1998 </script> |
3
Time Complexity: O(M*N2)
Auxiliary Space: O(1)
Contact Us