Matrix Flashcards
Search in a row wise and column wise sorted matrix
Given an n x n matrix and a number x, find the position of x in the matrix if it is present in it. Otherwise, print “Not Found”. In the given matrix, every row and column is sorted in increasing order. The designed algorithm should have linear time complexity.
Example:
Input: mat[4][4] = { {10, 20, 30, 40},
{15, 25, 35, 45},
{27, 29, 37, 48},
{32, 33, 39, 50}};
x = 29
Output: Found at (2, 1)
Explanation: Element at (2,1) is 29
Input : mat[4][4] = { {10, 20, 30, 40},
{15, 25, 35, 45},
{27, 29, 37, 48},
{32, 33, 39, 50}};
x = 100
Output : Element not found
Explanation: Element 100 is not found
Simple Solution
Approach: The simple idea is to traverse the array and to search elements one by one.
Algorithm:
Run a nested loop, outer loop for row and inner loop for the column
Check every element with x and if the element is found then print “element found”
If the element is not found, then print “element not found”.
Implementation:
// C++ program to search an element in row-wise // and column-wise sorted matrix #include (bits/stdc++.h>
using namespace std;
/* Searches the element x in mat[][]. If the
element is found, then prints its position
and returns true, otherwise prints "not found"
and returns false */
int search(int mat[4][4], int n, int x)
{
if (n == 0)
return -1;
//traverse through the matrix
for(int i = 0; i ( n; i++)
{
for(int j = 0; j ( n; j++)
//if the element is found
if(mat[i][j] == x)
{
cout(("Element found at ("((
i (( ", " (( j (( ")\n";
return 1;
}
}
cout (( "n Element not found"; return 0; }
// Driver code
int main()
{
int mat[4][4] = { { 10, 20, 30, 40 },
{ 15, 25, 35, 45 },
{ 27, 29, 37, 48 },
{ 32, 33, 39, 50 } };
search(mat, 4, 29);
return 0; } Output Element found at (2, 1)
Efficient Solution
Approach: The simple idea is to remove a row or column in each comparison until an element is found. Start searching from the top-right corner of the matrix. There are three possible cases.
The given number is greater than the current number: This will ensure that all the elements in the current row are smaller than the given number as the pointer is already at the right-most elements and the row is sorted. Thus, the entire row gets eliminated and continues the search for the next row. Here, elimination means that a row needs not be searched.
The given number is smaller than the current number: This will ensure that all the elements in the current column are greater than the given number. Thus, the entire column gets eliminated and continues the search for the previous column, i.e. the column on the immediate left.
The given number is equal to the current number: This will end the search.
Algorithm:
Let the given element be x, create two variable i = 0, j = n-1 as index of row and column
Run a loop until i = n
Check if the current element is greater than x then decrease the count of j. Exclude the current column.
Check if the current element is less than x then increase the count of i. Exclude the current row.
If the element is equal, then print the position and end.
Thanks to devendraiiit for suggesting the approach below.
Implementation:
// C++ program to search an element in row-wise // and column-wise sorted matrix #include (bits/stdc++.h>
using namespace std;
/* Searches the element x in mat[][]. If the
element is found, then prints its position
and returns true, otherwise prints "not found"
and returns false */
int search(int mat[4][4], int n, int x)
{
if (n == 0)
return -1;
int smallest = mat[0][0], largest = mat[n - 1][n - 1]; if (x ( smallest || x > largest) return -1;
// set indexes for top right element
int i = 0, j = n - 1;
while (i ( n && j >= 0)
{
if (mat[i][j] == x)
{
cout (( "n Found at "
(( i (( ", " (( j;
return 1;
}
if (mat[i][j] > x)
j--;
// Check if mat[i][j] ( x else i++; } cout (( "n Element not found"; return 0; }
// Driver code
int main()
{
int mat[4][4] = { { 10, 20, 30, 40 },
{ 15, 25, 35, 45 },
{ 27, 29, 37, 48 },
{ 32, 33, 39, 50 } };
search(mat, 4, 29);
return 0; }
Output
n Found at 2, 1
Time Complexity: O(n).
Only one traversal is needed, i.e, i from 0 to n and j from n-1 to 0 with at most 2*n steps.
The above approach will also work for m x n matrix (not only for n x n). Complexity would be O(m + n).
Space Complexity: O(1).
No extra space is required.
Find median in row wise sorted matrix, solve with naive approach
Median in a row-wise sorted Matrix
Given a row wise sorted matrix of size RxC where R and C are always odd, find the median of the matrix.
Example 1:
Input:
R = 3, C = 3
M = [[1, 3, 5],
[2, 6, 9],
[3, 6, 9]]
Output: 5
Explanation:
Sorting matrix elements gives us
{1,2,3,3,5,6,6,9,9}. Hence, 5 is median.
Example 2:
Input:
R = 3, C = 1
M = [[1], [2], [3]]
Output: 2
Your Task:
You don’t need to read input or print anything. Your task is to complete the function median() which takes the integers R and C along with the 2D matrix as input parameters and returns the median of the matrix.
Expected Time Complexity: O(32 * R * log(C))
Expected Auxiliary Space: O(1)
The key insight is that since we’re looking for the median of all elements, we can first collect all elements into a single array, sort them, and then find the middle element. Since we’re guaranteed that both rows and columns are odd, we’ll always have an odd total number of elements, making the median calculation straightforward.
Here’s the solution with detailed explanations:
class Solution {
public int findMedian(int[][] matrix) {
// First, let's get the dimensions of the matrix
int rows = matrix.length;
int cols = matrix[0].length;
// Calculate total number of elements
int totalElements = rows * cols;
// Create a 1D array to store all elements
int[] allElements = new int[totalElements];
// Copy all elements from the 2D matrix to the 1D array
int index = 0;
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
allElements[index++] = matrix[i][j];
}
}
// Sort the array in ascending order
Arrays.sort(allElements);
// Since we know total elements is odd (rows and cols are odd),
// median will be the middle element
// For example, if there are 9 elements, median is at index 4 (0-based)
int medianIndex = totalElements / 2;
return allElements[medianIndex];
}
}
Let’s understand how this solution works:
- First, we get the dimensions of the matrix (rows and columns).
- We calculate the total number of elements (rows × columns). For example, in a 3×3 matrix, we’ll have 9 elements.
- We create a new 1D array to store all elements from the matrix. This makes it easier to sort and find the median.
- We copy all elements from the 2D matrix to our 1D array using nested loops.
- We use Arrays.sort() to sort all elements in ascending order.
- Since we know the total number of elements is odd (both rows and columns are odd), the median will be the middle element.
- For example, if we have 9 elements (indices 0 to 8), the median is at index 4
- We can calculate this using totalElements / 2
Time Complexity: O(nm * log(nm)) where n is the number of rows and m is the number of columns. This is dominated by the sorting step.
Space Complexity: O(n*m) to store all elements in the auxiliary array.
Let’s verify with your example:
~~~
Input: mat[][] = [[1 3 5],
[2 6 9],
[3 6 9]]
After copying to 1D array: [1, 3, 5, 2, 6, 9, 3, 6, 9]
After sorting: [1, 2, 3, 3, 5, 6, 6, 9, 9]
Total elements = 9, so median index = 4
Therefore, median = 5
~~~
While this solution is not the most efficient possible (there are more optimal solutions using binary search), it’s straightforward to understand and implement.
Find median in row wise sorted matrix, solve with optimized approach
Median in a row-wise sorted Matrix
Given a row wise sorted matrix of size RxC where R and C are always odd, find the median of the matrix.
Example 1:
Input:
R = 3, C = 3
M = [[1, 3, 5],
[2, 6, 9],
[3, 6, 9]]
Output: 5
Explanation:
Sorting matrix elements gives us
{1,2,3,3,5,6,6,9,9}. Hence, 5 is median.
Example 2:
Input:
R = 3, C = 1
M = [[1], [2], [3]]
Output: 2
Your Task:
You don’t need to read input or print anything. Your task is to complete the function median() which takes the integers R and C along with the 2D matrix as input parameters and returns the median of the matrix.
Expected Time Complexity: O(32 * R * log(C))
Expected Auxiliary Space: O(1)
I’ll explain the more efficient binary search approach to finding the median in a row-wise sorted matrix. This solution is particularly interesting because it takes advantage of the matrix’s properties to achieve better performance.
Let’s understand the intuition first:
- In a matrix with n rows and m columns, the median will be the (n*m)/2 th element (0-based) in the sorted array.
- Since each row is sorted, we can use binary search effectively.
- For any number x, we can count how many elements in the matrix are less than or equal to x very efficiently.
Here’s the solution with detailed explanations:
class Solution {
public int findMedian(int[][] matrix) {
int rows = matrix.length;
int cols = matrix[0].length;
// Find the minimum and maximum elements in the matrix
// Since rows are sorted, min will be the first element of some row
// and max will be the last element of some row
int min = Integer.MAX_VALUE;
int max = Integer.MIN_VALUE;
for (int i = 0; i < rows; i++) {
min = Math.min(min, matrix[i][0]); // First element of each row
max = Math.max(max, matrix[i][cols-1]); // Last element of each row
}
// The median position we're looking for
// For a 3x3 matrix, this would be 4 (0-based)
int medianPosition = (rows * cols) / 2;
// Binary search between min and max
while (min < max) {
int mid = min + (max - min) / 2;
// Count numbers less than or equal to mid
int count = 0;
for (int i = 0; i < rows; i++) {
// For each row, find position of elements <= mid
count += countSmallerOrEqual(matrix[i], mid);
}
// If count is less than or equal to median position,
// we need to look in the right half
if (count <= medianPosition) {
min = mid + 1;
} else {
max = mid;
}
}
return min;
}
// Binary search in a row to find count of elements <= target
private int countSmallerOrEqual(int[] row, int target) {
int left = 0;
int right = row.length;
while (left < right) {
int mid = left + (right - left) / 2;
if (row[mid] <= target) {
left = mid + 1;
} else {
right = mid;
}
}
return left;
}
}
Let’s break down how this more sophisticated approach works:
-
Finding Range:
- Since each row is sorted, the minimum element must be the first element of some row.
- Similarly, the maximum element must be the last element of some row.
- We find these to establish our binary search range.
-
Binary Search on Answer Space:
- Instead of sorting all elements, we binary search on the possible values.
- For each middle value we guess, we count how many elements are less than or equal to it.
- This count helps us determine if our guess is too high or too low.
-
Counting Elements:
- For each row, we use binary search to count elements <= mid.
- This is efficient because each row is already sorted.
- We sum up these counts to get the total count.
-
Adjusting Search Space:
- If count <= medianPosition, our guess is too low.
- If count > medianPosition, our guess might be the answer or too high.
Let’s analyze the time complexity:
- The outer binary search runs O(log(max-min)) times
- For each iteration, we check each row using binary search: O(n * log(m))
- Total: O(n * log(m) * log(max-min)) where max-min is the range of numbers
This is significantly better than the sorting approach which took O(nm * log(nm)) time.
Let’s see it work with an example:
~~~
Matrix: [[1 3 5],
[2 6 9],
[3 6 9]]
min = 1, max = 9
medianPosition = 4 (0-based)
First iteration:
mid = 5
count of elements <= 5: 5 (1,2,3,3,5)
count <= medianPosition, so look right
Second iteration:
mid = 7
count of elements <= 7: 7 (1,2,3,3,5,6,6)
count > medianPosition, so look left
And so on…
~~~
This solution is more complex but much more efficient, especially for larger matrices. The key insight is that we don’t need to actually sort the elements - we just need to find the value that would be in the median position if the matrix were sorted.
Would you like me to explain any part of this solution in more detail?
Given a boolean 2D array, where each row is sorted. Find the row with the maximum number of 1s.
Example:
Input matrix 0 1 1 1 0 0 1 1 1 1 1 1 // this row has maximum 1s 0 0 0 0
Output: 2
A simple method is to do a row wise traversal of the matrix, count the number of 1s in each row and compare the count with max. Finally, return the index of row with maximum 1s. The time complexity of this method is O(m*n) where m is number of rows and n is number of columns in matrix.
Implementation of Simple Approach: // CPP program to find the row // with maximum number of 1s #include (bits/stdc++.h> using namespace std; #define R 4 #define C 4
// Function that returns index of row
// with maximum number of 1s.
int rowWithMax1s(bool mat[R][C]) {
// code here
int rowIndex = -1 ;
int maxCount = 0 ;
for(int i = 0 ; i ( R ; i++){
int count = 0 ;
for(int j = 0 ; j ( C ; j++ ){
if(mat[i][j] == 1){
count++ ;
}
}
if(count > maxCount){
maxCount = count ;
rowIndex = i ;
}
}
return rowIndex ; }
// Driver Code
int main()
{
bool mat[R][C] = { {0, 0, 0, 1},
{0, 1, 1, 1},
{1, 1, 1, 1},
{0, 0, 0, 0}};
cout (( "Index of row with maximum 1s is " (( rowWithMax1s(mat);
return 0; } Output Index of row with maximum 1s is 2 Time Complexity: O(m*n) Space Complexity: O(1)
We can do better. Since each row is sorted, we can use Binary Search to count of 1s in each row. We find the index of first instance of 1 in each row. The count of 1s will be equal to total number of columns minus the index of first 1.
See the following code for implementation of the above approach.
// CPP program to find the row // with maximum number of 1s #include (bits/stdc++.h> using namespace std; #define R 4 #define C 4
// Function to find the index of first index
// of 1 in a boolean array arr[]
int first(bool arr[], int low, int high)
{
if(high >= low)
{
// Get the middle index
int mid = low + (high - low)/2;
// Check if the element at middle index is first 1 if ( ( mid == 0 || arr[mid-1] == 0) && arr[mid] == 1) return mid;
// If the element is 0, recur for right side else if (arr[mid] == 0) return first(arr, (mid + 1), high);
// If element is not first 1, recur for left side else return first(arr, low, (mid -1)); } return -1; }
// Function that returns index of row
// with maximum number of 1s.
int rowWithMax1s(bool mat[R][C])
{
// Initialize max values
int max_row_index = 0, max = -1;
// Traverse for each row and count number of 1s
// by finding the index of first 1
int i, index;
for (i = 0; i ( R; i++)
{
index = first (mat[i], 0, C-1);
if (index != -1 && C-index > max)
{
max = C - index;
max_row_index = i;
}
}
return max_row_index; }
// Driver Code
int main()
{
bool mat[R][C] = { {0, 0, 0, 1},
{0, 1, 1, 1},
{1, 1, 1, 1},
{0, 0, 0, 0}};
cout (( "Index of row with maximum 1s is " (( rowWithMax1s(mat); return 0; }
Output
Index of row with maximum 1s is 2
Time Complexity: O(mLogn) where m is number of rows and n is number of columns in matrix.
Given an NxN matrix Mat. Sort all elements of the matrix.
Example 1:
Input: N=4 Mat=[[10,20,30,40], [15,25,35,45] [27,29,37,48] [32,33,39,50]] Output: 10 15 20 25 27 29 30 32 33 35 37 39 40 45 48 50 Explanation: Sorting the matrix gives this result. Example 2:
Input: N=3 Mat=[[1,5,3],[2,8,7],[4,6,9]] Output: 1 2 3 4 5 6 7 8 9 Explanation: Sorting the matrix gives this result. Your Task: You don't need to read input or print anything. Your task is to complete the function sortedMatrix() which takes the integer N and the matrix Mat as input parameters and returns the sorted matrix.
Expected Time Complexity:O(N2LogN)
Expected Auxillary Space:O(N2)
I’ll create a solution to sort all elements in an NxN matrix.
public class MatrixSorter {
public static void sortMatrix(int[][] mat) {
int n = mat.length;
// Convert 2D matrix to 1D array
int[] temp = new int[n * n];
int index = 0;
// Copy elements to 1D array
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
temp[index++] = mat[i][j];
}
}
// Sort the 1D array
Arrays.sort(temp);
// Copy back sorted elements to matrix
index = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
mat[i][j] = temp[index++];
}
}
}
// Utility method to print matrix
public static void printMatrix(int[][] mat) {
for (int[] row : mat) {
for (int num : row) {
System.out.print(num + " ");
}
System.out.println();
}
}
public static void main(String[] args) {
// Example usage
int[][] matrix = {
{5, 4, 7},
{1, 3, 8},
{2, 9, 6}
};
System.out.println("Original Matrix:");
printMatrix(matrix);
sortMatrix(matrix);
System.out.println("\nSorted Matrix:");
printMatrix(matrix);
}
}
This solution:
1. Takes an NxN matrix as input
2. Converts the 2D matrix into a 1D array
3. Sorts the 1D array using Java’s built-in Arrays.sort()
4. Copies the sorted elements back to the original matrix
The time complexity is O(n² log n²) where n is the size of the matrix, mainly due to the sorting operation.
When you run the program with the example matrix:
~~~
Original Matrix:
5 4 7
1 3 8
2 9 6
Sorted Matrix:
1 2 3
4 5 6
7 8 9
~~~
Find a specific pair in Matrix
Given an n x n matrix mat[n][n] of integers, find the maximum value of mat(c, d) – mat(a, b) over all choices of indexes such that both c > a and d > b.
Example:
Input:
mat[N][N] = {{ 1, 2, -1, -4, -20 },
{ -8, -3, 4, 2, 1 },
{ 3, 8, 6, 1, 3 },
{ -4, -1, 1, 7, -6 },
{ 0, -4, 10, -5, 1 }};
Output: 18
The maximum value is 18 as mat[4][2]
- mat[1][0] = 18 has maximum difference.
The program should do only ONE traversal of the matrix. i.e. expected time complexity is O(n2) A simple solution would be to apply Brute-Force. For all values mat(a, b) in the matrix, we find mat(c, d) that has maximum value such that c > a and d > b and keeps on updating maximum value found so far. We finally return the maximum value. Below is its implementation. // A Naive method to find maximum value of mat[d][e] // - ma[a][b] such that d > a and e > b #include (bits/stdc++.h> using namespace std; #define N 5
// The function returns maximum value A(d,e) - A(a,b)
// over all choices of indexes such that both d > a
// and e > b.
int findMaxValue(int mat[][N])
{
// stores maximum value
int maxValue = INT_MIN;
// Consider all possible pairs mat[a][b] and // mat[d][e] for (int a = 0; a ( N - 1; a++) for (int b = 0; b ( N - 1; b++) for (int d = a + 1; d ( N; d++) for (int e = b + 1; e ( N; e++) if (maxValue ( (mat[d][e] - mat[a][b])) maxValue = mat[d][e] - mat[a][b];
return maxValue; }
// Driver program to test above function
int main()
{
int mat[N][N] = {
{ 1, 2, -1, -4, -20 },
{ -8, -3, 4, 2, 1 },
{ 3, 8, 6, 1, 3 },
{ -4, -1, 1, 7, -6 },
{ 0, -4, 10, -5, 1 }
};
cout (( "Maximum Value is "
(( findMaxValue(mat);
return 0; }
Output:
Maximum Value is 18
The above program runs in O(n^4) time which is nowhere close to expected time complexity of O(n^2)
An efficient solution uses extra space. We pre-process the matrix such that index(i, j) stores max of elements in matrix from (i, j) to (N-1, N-1) and in the process keeps on updating maximum value found so far. We finally return the maximum value.
// An efficient method to find maximum value of mat[d] // - ma[a][b] such that c > a and d > b #include (bits/stdc++.h> using namespace std; #define N 5
// The function returns maximum value A(c,d) - A(a,b)
// over all choices of indexes such that both c > a
// and d > b.
int findMaxValue(int mat[][N])
{
//stores maximum value
int maxValue = INT_MIN;
// maxArr[i][j] stores max of elements in matrix // from (i, j) to (N-1, N-1) int maxArr[N][N];
// last element of maxArr will be same's as of // the input matrix maxArr[N-1][N-1] = mat[N-1][N-1];
// preprocess last row
int maxv = mat[N-1][N-1]; // Initialize max
for (int j = N - 2; j >= 0; j--)
{
if (mat[N-1][j] > maxv)
maxv = mat[N - 1][j];
maxArr[N-1][j] = maxv;
}
// preprocess last column
maxv = mat[N - 1][N - 1]; // Initialize max
for (int i = N - 2; i >= 0; i--)
{
if (mat[i][N - 1] > maxv)
maxv = mat[i][N - 1];
maxArr[i][N - 1] = maxv;
}
// preprocess rest of the matrix from bottom
for (int i = N-2; i >= 0; i--)
{
for (int j = N-2; j >= 0; j--)
{
// Update maxValue
if (maxArr[i+1][j+1] - mat[i][j] >
maxValue)
maxValue = maxArr[i + 1][j + 1] - mat[i][j];
// set maxArr (i, j) maxArr[i][j] = max(mat[i][j], max(maxArr[i][j + 1], maxArr[i + 1][j]) ); } }
return maxValue; }
// Driver program to test above function
int main()
{
int mat[N][N] = {
{ 1, 2, -1, -4, -20 },
{ -8, -3, 4, 2, 1 },
{ 3, 8, 6, 1, 3 },
{ -4, -1, 1, 7, -6 },
{ 0, -4, 10, -5, 1 }
};
cout (( "Maximum Value is "
(( findMaxValue(mat);
return 0; }
85. Maximal Rectangle
Given a rows x cols binary matrix filled with 0’s and 1’s, find the largest rectangle containing only 1’s and return its area.
Example 1:
Input: matrix = [[“1”,”0”,”1”,”0”,”0”],[“1”,”0”,”1”,”1”,”1”],[“1”,”1”,”1”,”1”,”1”],[“1”,”0”,”0”,”1”,”0”]]
Output: 6
Explanation: The maximal rectangle is shown in the above picture.
Example 2:
Input: matrix = [[“0”]]
Output: 0
Example 3:
Input: matrix = [[“1”]]
Output: 1
Constraints:
rows == matrix.length
cols == matrix[i].length
1 <= row, cols <= 200
matrix[i][j] is ‘0’ or ‘1’.
I’ll help you solve this challenging problem of finding the largest rectangle containing only 1’s in a binary matrix. This is a classic dynamic programming problem that can be solved by cleverly using the concept of “histogram area calculation.”
Let’s break it down step by step:
- First, let’s understand the approach:
- We’ll convert this 2D problem into a series of 1D problems using histograms
- For each row, we’ll calculate heights of consecutive 1’s above it
- Then for each of these histogram representations, we’ll find the largest rectangle
- The maximum among all these will be our answer
class Solution {
public int maximalRectangle(char[][] matrix) {
if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
return 0;
}
int rows = matrix.length;
int cols = matrix[0].length;
// Heights array represents the histogram heights for current row
int[] heights = new int[cols];
int maxArea = 0;
// Process each row
for (int i = 0; i < rows; i++) {
// Update heights array for current row
for (int j = 0; j < cols; j++) {
if (matrix[i][j] == '1') {
// Add 1 to previous height
heights[j] += 1;
} else {
// Reset height to 0 if we encounter '0'
heights[j] = 0;
}
}
// Calculate maximum rectangle area for current histogram
maxArea = Math.max(maxArea, calculateLargestRectangleInHistogram(heights));
}
return maxArea;
}
// Helper method to calculate largest rectangle in histogram
private int calculateLargestRectangleInHistogram(int[] heights) {
int n = heights.length;
Stack<Integer> stack = new Stack<>();
int maxArea = 0;
// Process all bars in histogram
for (int i = 0; i <= n; i++) {
// Current height (use 0 for last iteration to clear stack)
int h = (i == n) ? 0 : heights[i];
// If stack is empty or current height is larger than top of stack,
// push current index onto stack
if (stack.isEmpty() || h >= heights[stack.peek()]) {
stack.push(i);
} else {
// Pop stack and calculate areas until we find a smaller height
while (!stack.isEmpty() && h < heights[stack.peek()]) {
int height = heights[stack.pop()];
// Calculate width based on stack state
int width = stack.isEmpty() ? i : i - stack.peek() - 1;
// Update maximum area if current area is larger
maxArea = Math.max(maxArea, height * width);
}
stack.push(i);
}
}
return maxArea;
}
}
Let me explain how this solution works:
- The main algorithm converts the 2D problem into a series of 1D histogram problems:
- We maintain a heights array that represents the histogram at each row
- When we encounter a ‘1’, we add 1 to the previous height
- When we encounter a ‘0’, we reset the height to 0
- For calculating the largest rectangle in each histogram, we use a stack-based approach:
- We maintain a stack of indices where heights are in increasing order
- When we find a smaller height, we pop the stack and calculate areas
- The width for each rectangle is determined by the distance between indices
- Time and Space Complexity:
- Time Complexity: O(rows × cols)
- We process each cell once to build histograms
- For each row, we process the histogram in O(cols) time
- Space Complexity: O(cols)
- We use a heights array and a stack, both of size cols
- Time Complexity: O(rows × cols)
- Key insights:
- Converting 2D to 1D makes the problem more manageable
- Using a stack helps us find the “boundaries” of each potential rectangle
- The histogram approach automatically handles all possible rectangle shapes
Rotate the matrix by 90 degrees
Another Approach:
- Reverse every individual row
- Perform Transpose
// C++ program to rotate a matrix // by 90 degrees #include #define N 4 using namespace std;
void displayMatrix(int mat[N][N]);
// An Inplace function to
// rotate a N x N matrix
// by 90 degrees in
// anti-clockwise direction
void rotateMatrix(int mat[][N])
{ // REVERSE every row
for (int i = 0; i < N; i++)
reverse(mat[i], mat[i] + N);
// Performing Transpose
for (int i = 0; i < N; i++) {
for (int j = i; j < N; j++)
swap(mat[i][j], mat[j][i]);
}
}
// Function to print the matrix
void displayMatrix(int mat[N][N])
{
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++)
printf("%2d ", mat[i][j]);
printf("\n");
}
printf("\n"); }
/* Driver program to test above functions */
int main()
{
// Test Case 1
int mat[N][N] = { { 1, 2, 3, 4 },
{ 5, 6, 7, 8 },
{ 9, 10, 11, 12 },
{ 13, 14, 15, 16 } };
// Test Case 2
/* int mat[N][N] = {
{1, 2, 3},
{4, 5, 6},
{7, 8, 9}
};
*/
// Test Case 3
/*int mat[N][N] = {
{1, 2},
{4, 5}
};*/
// displayMatrix(mat); rotateMatrix(mat);
// Print rotated matrix displayMatrix(mat);
return 0; }
Solve by brute force method
Kth element in Matrix
Given a N x N matrix, where every row and column is sorted in non-decreasing order. Find the kth smallest element in the matrix.
Example 1:
Input:
N = 4
mat[][] = {{16, 28, 60, 64},
{22, 41, 63, 91},
{27, 50, 87, 93},
{36, 78, 87, 94 }}
K = 3
Output: 27
Explanation: 27 is the 3rd smallest element.
Example 2:
Input:
N = 4
mat[][] = {{10, 20, 30, 40}
{15, 25, 35, 45}
{24, 29, 37, 48}
{32, 33, 39, 50}}
K = 7
Output: 30
Explanation: 30 is the 7th smallest element.
Your Task:
You don’t need to read input or print anything. Complete the function kthsmallest() which takes the mat, N and K as input parameters and returns the kth smallest element in the matrix.
Expected Time Complexity: O(K*Log(N))
Expected Auxiliary Space: O(N)
int kthSmallest(int mat[MAX][MAX], int n, int k)
{
//Your code here
vector v;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++)
v.push_back(mat[i][j]);
}
sort(v.begin(), v.end());
return v[k - 1];
}Solve by optimized approach
Kth element in Matrix
Given a N x N matrix, where every row and column is sorted in non-decreasing order. Find the kth smallest element in the matrix.
Example 1:
Input:
N = 4
mat[][] = {{16, 28, 60, 64},
{22, 41, 63, 91},
{27, 50, 87, 93},
{36, 78, 87, 94 }}
K = 3
Output: 27
Explanation: 27 is the 3rd smallest element.
Example 2:
Input:
N = 4
mat[][] = {{10, 20, 30, 40}
{15, 25, 35, 45}
{24, 29, 37, 48}
{32, 33, 39, 50}}
K = 7
Output: 30
Explanation: 30 is the 7th smallest element.
Your Task:
You don’t need to read input or print anything. Complete the function kthsmallest() which takes the mat, N and K as input parameters and returns the kth smallest element in the matrix.
Expected Time Complexity: O(K*Log(N))
Expected Auxiliary Space: O(N)
// A structure to store an entry of heap. The entry contains a value from 2D array, row and column numbers of the value
struct HeapNode {
int val; // value to be stored
int r; // Row number of value in 2D array
int c; // Column number of value in 2D array
};
// A utility function to swap two HeapNode items.
void swap(HeapNode *x, HeapNode *y) {
HeapNode z = *x;
*x = *y;
*y = z;
}
// A utility function to minheapify the node harr[i] of a heap stored in harr[]
void minHeapify(HeapNode harr[], int i, int heap_size)
{
int l = i2 + 1;
int r = i2 + 2;
int smallest = i;
if (l < heap_size && harr[l].val < harr[i].val)
smallest = l;
if (r < heap_size && harr[r].val < harr[smallest].val)
smallest = r;
if (smallest != i)
{
swap(&harr[i], &harr[smallest]);
minHeapify(harr, smallest, heap_size);
}
}
// A utility function to convert harr[] to a min heap
void buildHeap(HeapNode harr[], int n)
{
int i = (n - 1)/2;
while (i >= 0)
{
minHeapify(harr, i, n);
i--;
}
}
Common elements in all rows of a given matrix
Given an m x n matrix, find all common elements present in all rows in O(mn) time and one traversal of matrix.
Example:
Input:
mat[4][5] = {{1, 2, 1, 4, 8},
{3, 7, 8, 5, 1},
{8, 7, 7, 3, 1},
{8, 1, 2, 7, 9},
};
Output:
1 8 or 8 1
8 and 1 are present in all rows.
A simple solution is to consider every element and check if it is present in all rows. If present, then print it.
A better solution is to sort all rows in the matrix and use similar approach as discussed here. Sorting will take O(mnlogn) time and finding common elements will take O(mn) time. So overall time complexity of this solution is O(mnlogn)
Can we do better than O(mnlogn)?
The idea is to use maps. We initially insert all elements of the first row in an map. For every other element in remaining rows, we check if it is present in the map. If it is present in the map and is not duplicated in current row, we increment count of the element in map by 1, else we ignore the element. If the currently traversed row is the last row, we print the element if it has appeared m-1 times before.
Below is the implementation of the idea:
// A Program to prints common element in all // rows of matrix #include using namespace std;
// Specify number of rows and columns #define M 4 #define N 5
// prints common element in all rows of matrix
void printCommonElements(int mat[M][N])
{
unordered_map mp;
// initialize 1st row elements with value 1 for (int j = 0; j < N; j++) mp[mat[0][j]] = 1;
// traverse the matrix
for (int i = 1; i < M; i++)
{
for (int j = 0; j < N; j++)
{
// If element is present in the map and
// is not duplicated in current row.
if (mp[mat[i][j]] == i)
{
// we increment count of the element
// in map by 1
mp[mat[i][j]] = i + 1;
// If this is last row if (i==M-1 && mp[mat[i][j]]==M) cout << mat[i][j] << " "; } } } }
// driver program to test above function
int main()
{
int mat[M][N] =
{
{1, 2, 1, 4, 8},
{3, 7, 8, 5, 1},
{8, 7, 7, 3, 1},
{8, 1, 2, 7, 9},
};
printCommonElements(mat); return 0; }
