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.
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)
Simple Method: The simplest method to solve this problem is to store all the elements of the given matrix in an array of size rc. Then we can either sort the array and find the median element in O(rclog(rc)) or we can use the approach discussed here to find the median in O(rc). Auxiliary space required will be O(r*c) in both cases.
An efficient approach for this problem is to use a binary search algorithm. The idea is that for a number to be median there should be exactly (n/2) numbers which are less than this number. So, we try to find the count of numbers less than all the numbers. Below is the step by step algorithm for this approach:
Algorithm:
First, we find the minimum and maximum elements in the matrix. The minimum element can be easily found by comparing the first element of each row, and similarly, the maximum element can be found by comparing the last element of each row.
Then we use binary search on our range of numbers from minimum to maximum, we find the mid of the min and max and get a count of numbers less than or equal to our mid. And accordingly change the min or max.
For a number to be median, there should be (r*c)/2 numbers smaller than that number. So for every number, we get the count of numbers less than that by using upper_bound() in each row of the matrix, if it is less than the required count, the median must be greater than the selected number, else the median must be less than or equal to the selected number.
Below is the implementation of the above approach:
// C++ program to find median of a matrix // sorted row wise #include(bits/stdc++.h> using namespace std;
const int MAX = 100;
// function to find median in the matrix
int binaryMedian(int m[][MAX], int r ,int c)
{
int min = INT_MAX, max = INT_MIN;
for (int i=0; i(r; i++)
{
// Finding the minimum element
if (m[i][0] ( min)
min = m[i][0];
// Finding the maximum element if (m[i][c-1] > max) max = m[i][c-1]; }
int desired = (r * c + 1) / 2;
while (min ( max)
{
int mid = min + (max - min) / 2;
int place = 0;
// Find count of elements smaller than mid for (int i = 0; i ( r; ++i) place += upper_bound(m[i], m[i]+c, mid) - m[i]; if (place ( desired) min = mid + 1; else max = mid; } return min; }
// driver program to check above functions
int main()
{
int r = 3, c = 3;
int m[][MAX]= { {1,3,5}, {2,6,9}, {3,6,9} };
cout (( "Median is " (( binaryMedian(m, r, c) (( endl;
return 0;
}
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; }
