Matrix Flashcards
Print a given matrix in spiral form
Given a 2D array, print it in spiral form. See the following examples.
Examples:
Input: 1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16
Output: 1 2 3 4 8 12 16 15 14 13 9 5 6 7 11 10
Explanation: The output is matrix in spiral format.
Input: 1 2 3 4 5 6
7 8 9 10 11 12
13 14 15 16 17 18
Output: 1 2 3 4 5 6 12 18 17 16 15 14 13 7 8 9 10 11
Explanation :The output is matrix in spiral format.
Method 1: This is a simple method to solve the following problem.
Approach: The problem can be solved by dividing the matrix into loops or squares or boundaries. It can be seen that the elements of the outer loop are printed first in a clockwise manner then the elements of the inner loop is printed. So printing the elements of a loop can be solved using four loops which prints all the elements. Every ‘for’ loop defines a single direction movement along with the matrix. The first for loop represents the movement from left to right, whereas the second crawl represents the movement from top to bottom, the third represents the movement from the right to left, and the fourth represents the movement from bottom to up.
Algorithm: Create and initialize variables k – starting row index, m – ending row index, l – starting column index, n – ending column index Run a loop until all the squares of loops are printed. In each outer loop traversal print the elements of a square in a clockwise manner. Print the top row, i.e. Print the elements of the kth row from column index l to n, and increase the count of k. Print the right column, i.e. Print the last column or n-1th column from row index k to m and decrease the count of n. Print the bottom row, i.e. if k < m, then print the elements of m-1th row from column n-1 to l and decrease the count of m Print the left column, i.e. if l < n, then print the elements of lth column from m-1th row to k and increase the count of l. Below is the implementation of the above algorithm: // C++ Program to print a matrix spirally
#include (bits/stdc++.h> using namespace std; #define R 3 #define C 6
void spiralPrint(int m, int n, int a[R][C])
{
int i, k = 0, l = 0;
/* k - starting row index m - ending row index l - starting column index n - ending column index i - iterator */
while (k ( m && l ( n) {
/* Print the first row from
the remaining rows */
for (i = l; i ( n; ++i) {
cout (( a[k][i] (( " ";
}
k++;
/* Print the last column
from the remaining columns */
for (i = k; i ( m; ++i) {
cout (( a[i][n - 1] (( " ";
}
n--;
/* Print the last row from
the remaining rows */
if (k ( m) {
for (i = n - 1; i >= l; --i) {
cout (( a[m - 1][i] (( " ";
}
m--;
}
/* Print the first column from
the remaining columns */
if (l ( n) {
for (i = m - 1; i >= k; --i) {
cout (( a[i][l] (( " ";
}
l++;
}
}
}
/* Driver Code */
int main()
{
int a[R][C] = { { 1, 2, 3, 4, 5, 6 },
{ 7, 8, 9, 10, 11, 12 },
{ 13, 14, 15, 16, 17, 18 } };
// Function Call spiralPrint(R, C, a); return 0; }
// This is code is contributed by rathbhupendra
Output
1 2 3 4 5 6 12 18 17 16 15 14 13 7 8 9 10 11
Complexity Analysis:
Time Complexity: O(mn).
To traverse the matrix O(mn) time is required.
Space Complexity: O(1).
No extra space is required.
Best Optimized Method 1: (Simulation Approach)
Intuition:
Draw the path that the spiral makes. We know that the path should turn clockwise whenever it would go out of bounds or into a cell that was previously visited.
Algorithm:
Let the array have R rows and C columns. seen[r] denotes that the cell on the r-th row and c-th column was previously visited. Our current position is (r, c), facing direction di, and we want to visit R x C total cells.
As we move through the matrix, our candidate’s next position is (cr, cc). If the candidate is in the bounds of the matrix and unseen, then it becomes our next position; otherwise, our next position is the one after performing a clockwise turn.
#include (bits/stdc++.h> using namespace std;
vector(int> spiralOrder(vector(vector(int> >& matrix)
{
vector(int> ans;
if (matrix.size() == 0)
return ans;
int R = matrix.size(), C = matrix[0].size();
vector(vector(bool> > seen(R, vector(bool>(C, false));
int dr[] = { 0, 1, 0, -1 };
int dc[] = { 1, 0, -1, 0 };
int r = 0, c = 0, di = 0;
// Iterate from 0 to R * C - 1
for (int i = 0; i ( R * C; i++) {
ans.push_back(matrix[r]);
seen[r] = true;
int cr = r + dr[di];
int cc = c + dc[di];
if (0 (= cr && cr ( R && 0 (= cc && cc ( C
&& !seen[cr][cc]) {
r = cr;
c = cc;
}
else {
di = (di + 1) % 4;
r += dr[di];
c += dc[di];
}
}
return ans;
}
// Driver code
int main()
{
vector(vector(int> > a{ { 1, 2, 3, 4 },
{ 5, 6, 7, 8 },
{ 9, 10, 11, 12 },
{ 13, 14, 15, 16 } };
for (int x : spiralOrder(a)) {
cout (( x (( " ";
}
return 0;
}
Output
1 2 3 4 8 12 16 15 14 13 9 5 6 7 11 10
Complexity Analysis:
Time Complexity: O(N), where N is the total number of elements in the input matrix. We add every element in the matrix to our final answer.
Space Complexity: O(N), the information stored in seen and in ans.
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)
#include using namespace std;
vector> sortedMatrix(int N, vector> Mat) {
int k = 0;
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());
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
Mat[i][j] = v[k++];
}
}
return Mat;
}
int main() {
return 0;
}
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; }
Max rectangle
Given a binary matrix M of size n X m. Find the maximum area of a rectangle formed only of 1s in the given matrix.
Example 1:
Input:
n = 4, m = 4
M[][] = {{0 1 1 0},
{1 1 1 1},
{1 1 1 1},
{1 1 0 0}}
Output: 8
Explanation: For the above test case the
matrix will look like
0 1 1 0
1 1 1 1
1 1 1 1
1 1 0 0
the max size rectangle is
1 1 1 1
1 1 1 1
and area is 4 *2 = 8.
Your Task:
Your task is to complete the function maxArea which returns the maximum size rectangle area in a binary-sub-matrix with all 1’s. The function takes 3 arguments the first argument is the Matrix M[ ] [ ] and the next two are two integers n and m which denotes the size of the matrix M.
Expected Time Complexity : O(n*m)
Expected Auixiliary Space : O(m)
Use the approach of finding maximum rectangle in a histogram.
The idea is to update each column of a given row with corresponding column of previous row and find largest histogram area for that row.
Step 1: Find maximum area for row[0]
Step 2:
for each row in 1 to N - 1
for each column in that row
if A[row][column] == 1
update A[row][column] with
A[row][column] += A[row - 1][column]
find area for that row
and update maximum area so far
class Solution{
public:
int mhist(int row[], int m1) {
stack result;
int top_val;
int max_area = 0;
int area = 0;
int i = 0;
for (i = 0; i < m1;) {
if (result.empty() || row[result.top()] <= row[i])
result.push(i++);
else {
top_val = row[result.top()];
result.pop();
area = top_val * i;
if (!result.empty()) area = top_val * (i - result.top() - 1);
max_area = max(area, max_area);
}
}
while (!result.empty()) {
top_val = row[result.top()];
result.pop();
area = top_val * i;
if (!result.empty()) area = top_val * (i - result.top() - 1);
max_area = max(area, max_area);
}
return max_area;
}
int kewl(int M[MAX][MAX], int n, int m) {
int res = mhist(M[0], m);
for (int i = 1; i < n; i++) {
for (int j = 0; j < m; j++) {
if (M[i][j]) M[i][j] += M[i - 1][j];
}
res = max(res, mhist(M[i], m));
}
return res;
}
int maxArea(int M[MAX][MAX], int n, int m) {
return kewl(M, n, m);
}
};
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; }
