Find whether the given number is at the correct position in Sorted Matrix
Given 3 integers N, M, and X and a 2D sorted matrix mat[][] of size NxM, check if X is at its correct position or not, mat[][] is sorted in such a manner that in every row all elements are sorted in increasing order and the first element of the current row is greater than the last element of the previous row (if any).
Examples:
Input: N = 3, M = 4, mat[][] = {{1, 2, 3, 4}, {5, 6, 7, 8}, {9, 10, 11, 12}}, X = 7
Output: 7 is at the correct position
Explanation: The given matrix is already sorted so all numbers are at their sorted position including 7.Input: N = 3, M = 4, mat[][] = {{12,6,5,2},{7,8,1,4},{3,9,11,10}}, X = 3
Output: 3 is not at the correct position
Explanation: If we compare the given matrix with its sorted version then we can observe that 3 is not at its sorted position .
Approach: To solve the problem follow the below idea:
If we sort the matrix, it will cost lots of time and memory. Since we only need to check for a single element, so instead of sorting the matrix we will start traversing over the given matrix and count the number of elements which are smaller than X. Now divide the count by number of columns to get row of X and then find modulus of the count with number of columns to get the column of X. Now, check against the position in the original matrix to get the answer.
Steps to solve the problem:
- Maintain a variable cnt to count the frequency of number less than X
- Iterate through the input matrix mat[][] and for every element mat[i][j] check the following:
- if mat[i][j] < X, then increment cnt by 1
- if mat[i][j] == X, then store the row as currRow and column as currCol
- if mat[i][j] > X, move to the next element
- Check if currRow == cnt / M and currCol == cnt % M to see if X was at the correct position or not.
Below is the implementation of the above approach:
C++
// C++ code for the above approach: #include <bits/stdc++.h> using namespace std; // Function for checking whether current // element is at sorted position or not bool checkPosition(vector<vector< int > > arr, int X) { int N = arr.size(), M = arr[0].size(), cnt = 0, currRow, currCol; // Iterating over the matrix for ( int i = 0; i < N; i++) { for ( int j = 0; j < M; j++) { // If the element is smaller than X, // increment cnt by 1 if (arr[i][j] < X) cnt++; // If the element is equal to X, // store the row and column of // the element if (arr[i][j] == X) { currRow = i; currCol = j; } } } return (currRow == cnt / M) && (currCol == cnt % M); } // Driver code int main() { vector<vector< int > > arr = { { 1, 2, 3, 4 }, { 5, 6, 7, 8 }, { 9, 10, 11, 12 } }; int X = 5; // Function call if (checkPosition(arr, X)) { cout << X << " is at the correct position\n"; } else { cout << X << " is not at the correct position\n"; } return 0; } |
Java
import java.util.Arrays; public class Main { // Function for checking whether current // element is at sorted position or not public static boolean checkPosition( int [][] arr, int X) { int N = arr.length; int M = arr[ 0 ].length; int cnt = 0 ; int currRow = - 1 , currCol = - 1 ; // Iterating over the matrix for ( int i = 0 ; i < N; i++) { for ( int j = 0 ; j < M; j++) { // If the element is smaller than X, // increment cnt by 1 if (arr[i][j] < X) cnt++; // If the element is equal to X, // store the row and column of // the element if (arr[i][j] == X) { currRow = i; currCol = j; } } } return (currRow == cnt / M) && (currCol == cnt % M); } // Driver code public static void main(String[] args) { int [][] arr = { { 1 , 2 , 3 , 4 }, { 5 , 6 , 7 , 8 }, { 9 , 10 , 11 , 12 } }; int X = 5 ; // Function call if (checkPosition(arr, X)) { System.out.println(X + " is at the correct position" ); } else { System.out.println(X + " is not at the correct position" ); } } } |
Python3
# Python code for the above approach: def checkPosition(arr, X): N = len (arr) M = len (arr[ 0 ]) cnt = 0 currRow = 0 currCol = 0 # Iterating over the matrix for i in range (N): for j in range (M): # If the element is smaller than X, increment cnt by 1 if arr[i][j] < X: cnt + = 1 # If the element is equal to X, store the row and column of the element if arr[i][j] = = X: currRow = i currCol = j return currRow = = cnt / / M and currCol = = cnt % M # Driver code arr = [ [ 1 , 2 , 3 , 4 ], [ 5 , 6 , 7 , 8 ], [ 9 , 10 , 11 , 12 ] ] X = 5 # Function call if checkPosition(arr, X): print (f "{X} is at the correct position" ) else : print (f "{X} is not at the correct position" ) # this code is contributed by uttamdp_10 |
C#
// C# code for the above approach using System; using System.Collections.Generic; class GFG { // Function for checking whether current // element is at sorted position or not static bool CheckPosition(List<List< int >> arr, int X) { int N = arr.Count; int M = arr[0].Count; int cnt = 0; int currRow = 0; int currCol = 0; // Iterating over the matrix for ( int i = 0; i < N; i++) { for ( int j = 0; j < M; j++) { // If the element is smaller than X, // increment cnt by 1 if (arr[i][j] < X) { cnt++; } // If the element is equal to X, // store the row and column of // the element if (arr[i][j] == X) { currRow = i; currCol = j; } } } return (currRow == cnt / M) && (currCol == cnt % M); } // Driver code static void Main( string [] args) { List<List< int >> arr = new List<List< int >>() { new List< int >() { 1, 2, 3, 4 }, new List< int >() { 5, 6, 7, 8 }, new List< int >() { 9, 10, 11, 12 } }; int X = 5; // Function call if (CheckPosition(arr, X)) { Console.WriteLine(X + " is at the correct position" ); } else { Console.WriteLine(X + " is not at the correct position" ); } } } |
Javascript
// Function for checking whether the current element is at the sorted position or not function checkPosition(arr, X) { const N = arr.length; const M = arr[0].length; let cnt = 0; let currRow, currCol; // Iterating over the matrix for (let i = 0; i < N; i++) { for (let j = 0; j < M; j++) { // If the element is smaller than X, increment cnt by 1 if (arr[i][j] < X) { cnt++; } // If the element is equal to X, store the row and column of the element if (arr[i][j] === X) { currRow = i; currCol = j; } } } // Check if the current row and column match the expected position return currRow === Math.floor(cnt / M) && currCol === cnt % M; } // Driver code const arr = [ [1, 2, 3, 4], [5, 6, 7, 8], [9, 10, 11, 12] ]; const X = 5; // Function call if (checkPosition(arr, X)) { console.log(X + " is at the correct position" ); } else { console.log(X + " is not at the correct position" ); } |
5 is at the correct position
Time Complexity: O(N*M), where N is the number of rows and M is the number of columns.
Auxiliary Space: O(1)