Given a matrix with N rows and M columns, find the minimum element and maximum element present in the matrix.
Example 1
Input: mat = [[1, 2, 3], [4, 5, 6]]
Output: Minimum = 1, Maximum = 6
Explanation: Smallest value in the matrix is 1, and largest value in the matrix is 6.
Example 2
Input: mat = [[10, -2], [3, 40], [-5, 6]]
Output: Minimum = -5, Maximum = 40
Explanation: Negative values are also compared, so -5 becomes the minimum and 40 becomes the maximum.
Approach
This approach scans every element of the matrix exactly once. The minimum and maximum values are initialized with the first element, and each remaining element is compared to update them whenever a smaller or larger value is found.
Algorithm
Initialize the minimum and maximum with the first element of the matrix.
Traverse every row using an outer loop.
For each row, traverse all columns using an inner loop.
Update the minimum and maximum by comparing the current element.
Return the final minimum and maximum values after all elements have been processed.
Dry Run
min max of matrix
Solution
#include <bits/stdc++.h>using namespace std;class Solution {public: // Function to find minimum and maximum elements in a matrix. pair<int, int> findMinMax(vector<vector<int>>& mat) { // Initialize minimum and maximum from the first cell. int minimum = mat[0][0]; int maximum = mat[0][0]; // Traverse every row from top to bottom. for (int row = 0; row < (int)mat.size(); row++) { // Traverse every column from left to right. for (int col = 0; col < (int)mat[row].size(); col++) { // Store the current matrix element. int value = mat[row][col]; // Update minimum when a smaller value appears. if (value < minimum) { minimum = value; } // Update maximum when a larger value appears. if (value > maximum) { maximum = value; } } } // Return minimum and maximum together. return {minimum, maximum}; }};// Driver code.int main() { vector<vector<int>> mat = {{10, -2}, {3, 40}, {-5, 6}}; Solution sol; pair<int, int> ans = sol.findMinMax(mat); cout << "Minimum = " << ans.first << ", Maximum = " << ans.second << "\n"; return 0;}Complexity Analysis
Time Complexity: O(N × M), traversal visits every matrix cell exactly once.
Space Complexity: O(1), only two variables store the running minimum and maximum.
Interview follow-up Questions
Yes. Every cell must be checked because any cell can contain the smallest or largest value.
Be the first to add a comment.