Find all matrix elements which are minimum in their row and maximum in their column
Given a matrix mat[][] of size M * N, the task is to find all matrix elements which are minimum in their respective row and maximum in their respective column. If no such element is present, print -1.
Examples:
Input: mat[][] = {{1, 10, 4}, {9, 3, 8}, {15, 16, 17}}
Output: 15
Explanation:
15 is the only element which is maximum in its column {1, 9, 15} and minimum in its row {15, 16, 17}.Input: m[][] = {{10, 41}, {3, 5}, {16, 2}}
Output: -1
Approach: Follow the steps below to solve the problem:
- Create an unordered_set and store the minimum element of each row of the matrix.
- Traverse the matrix and find the maximum element of each column. For every column, check if the maximum obtained is already present in the unordered_set or not.
- If found to be true, print that number. If no such matrix element is found, print -1.
Below is the implementation of the above approach:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Functionto find all the matrix elements // which are minimum in its row and maximum // in its column vector< int > minmaxNumbers(vector<vector< int > >& matrix, vector< int >& res) { // Initialize unordered set unordered_set< int > set; // Traverse the matrix for ( int i = 0; i < matrix.size(); i++) { int minr = INT_MAX; for ( int j = 0; j < matrix[i].size(); j++) { // Update the minimum // element of current row minr = min(minr, matrix[i][j]); } // Insert the minimum // element of the row set.insert(minr); } for ( int j = 0; j < matrix[0].size(); j++) { int maxc = INT_MIN; for ( int i = 0; i < matrix.size(); i++) { // Update the maximum // element of current column maxc = max(maxc, matrix[i][j]); } // Checking if it is already present // in the unordered_set or not if (set.find(maxc) != set.end()) { res.push_back(maxc); } } return res; } // Driver Code int main() { vector<vector< int > > mat = { { 1, 10, 4 }, { 9, 3, 8 }, { 15, 16, 17 } }; vector< int > ans; // Function call minmaxNumbers(mat, ans); // If no such matrix // element is found if (ans.size() == 0) cout << "-1" << endl; for ( int i = 0; i < ans.size(); i++) cout << ans[i] << endl; return 0; } |
Java
// Java program for the above approach import java.util.*; class GFG{ // Functionto find all the matrix elements // which are minimum in its row and maximum // in its column public static Vector<Integer>minmaxNumbers( int [][] matrix, Vector<Integer> res) { // Initialize unordered set Set<Integer> set = new HashSet<Integer>(); // Traverse the matrix for ( int i = 0 ; i < matrix.length; i++) { int minr = Integer.MAX_VALUE; for ( int j = 0 ; j < matrix[i].length; j++) { // Update the minimum // element of current row minr = Math.min(minr, matrix[i][j]); } // Insert the minimum // element of the row set.add(minr); } for ( int j = 0 ; j < matrix[ 0 ].length; j++) { int maxc = Integer.MIN_VALUE; for ( int i = 0 ; i < matrix.length; i++) { // Update the maximum // element of current column maxc = Math.max(maxc, matrix[i][j]); } // Checking if it is already present // in the unordered_set or not if (set.contains(maxc)) { res.add(maxc); } } return res; } // Driver code public static void main(String[] args) { int [][] mat = { { 1 , 10 , 4 }, { 9 , 3 , 8 }, { 15 , 16 , 17 } }; Vector<Integer> ans = new Vector<Integer>(); // Function call ans = minmaxNumbers(mat, ans); // If no such matrix // element is found if (ans.size() == 0 ) System.out.println( "-1" ); for ( int i = 0 ; i < ans.size(); i++) System.out.println(ans.get(i)); } } // This code is contributed by divyeshrabadiya07 |
Python3
# Python3 program for the above approach import sys # Functionto find all the matrix elements # which are minimum in its row and maximum # in its column def minmaxNumbers(matrix, res): # Initialize unordered set s = set () # Traverse the matrix for i in range ( 0 , len (matrix), 1 ): minr = sys.maxsize for j in range ( 0 , len (matrix[i]), 1 ): # Update the minimum # element of current row minr = min (minr, matrix[i][j]) # Insert the minimum # element of the row s.add(minr) for j in range ( 0 , len (matrix[ 0 ]), 1 ): maxc = - sys.maxsize - 1 for i in range ( 0 , len (matrix), 1 ): # Update the maximum # element of current column maxc = max (maxc, matrix[i][j]) # Checking if it is already present # in the unordered_set or not if (maxc in s): res.append(maxc) return res # Driver Code if __name__ = = '__main__' : mat = [ [ 1 , 10 , 4 ], [ 9 , 3 , 8 ], [ 15 , 16 , 17 ] ] ans = [] # Function call minmaxNumbers(mat, ans) # If no such matrix # element is found if ( len (ans) = = 0 ): print ( "-1" ) for i in range ( len (ans)): print (ans[i]) # This code is contributed by SURENDRA_GANGWAR |
C#
// C# program for // the above approach using System; using System.Collections.Generic; class GFG{ // Functionto find all // the matrix elements // which are minimum // in its row and // maximum in its column public static List< int > minmaxNumbers( int [,] matrix, List< int > res) { // Initialize unordered set HashSet< int > set = new HashSet< int >(); // Traverse the matrix for ( int i = 0; i < matrix.GetLength(0); i++) { int minr = int .MaxValue; for ( int j = 0; j < matrix.GetLength(1); j++) { // Update the minimum // element of current row minr = Math.Min(minr, matrix[i, j]); } // Insert the minimum // element of the row set .Add(minr); } for ( int j = 0; j < matrix.GetLength(0); j++) { int maxc = int .MinValue; for ( int i = 0; i < matrix.GetLength(1); i++) { // Update the maximum // element of current column maxc = Math.Max(maxc, matrix[i, j]); } // Checking if it is already present // in the unordered_set or not if ( set .Contains(maxc)) { res.Add(maxc); } } return res; } // Driver code public static void Main(String[] args) { int [,] mat = {{1, 10, 4}, {9, 3, 8}, {15, 16, 17}}; List< int > ans = new List< int >(); // Function call ans = minmaxNumbers(mat, ans); // If no such matrix // element is found if (ans.Count == 0) Console.WriteLine( "-1" ); for ( int i = 0; i < ans.Count; i++) Console.WriteLine(ans[i]); } } // This code is contributed by 29AjayKumar |
Javascript
<script> // Javascript program for the above approach // Functionto find all the matrix elements // which are minimum in its row and maximum // in its column function minmaxNumbers(matrix, res) { // Initialize unordered set var set = new Set(); // Traverse the matrix for ( var i = 0; i < matrix.length; i++) { var minr = 1000000000; for ( var j = 0; j < matrix[i].length; j++) { // Update the minimum // element of current row minr = Math.min(minr, matrix[i][j]); } // Insert the minimum // element of the row set.add(minr); } for ( var j = 0; j < matrix[0].length; j++) { var maxc = -1000000000; for ( var i = 0; i < matrix.length; i++) { // Update the maximum // element of current column maxc = Math.max(maxc, matrix[i][j]); } // Checking if it is already present // in the unordered_set or not if (set.has(maxc)) { res.push(maxc); } } return res; } // Driver Code var mat = [ [ 1, 10, 4 ], [ 9, 3, 8 ], [ 15, 16, 17 ] ]; var ans = []; // Function call minmaxNumbers(mat, ans); // If no such matrix // element is found if (ans.length == 0) document.write( "-1" ); for ( var i = 0; i < ans.length; i++) document.write( ans[i] + "<br>" ); // This code is contributed by rrrtnx. </script> |
Output:
15
Time Complexity: O(M * N)
Auxiliary Space: O(M + N)