You are given an 'N * N' matrix of integers where each row and each column is sorted in increasing order. You are given a target integer 'X'.
Find the position of 'X' in the matrix. If it exists then return the pair {i, j} where 'i' represents the row and 'j' represents the column of the array, otherwise return {-1,-1}
If the given matrix is:
[ [1, 2, 5],
[3, 4, 9],
[6, 7, 10]]
We have to find the position of 4. We will return {1,1} since A[1][1] = 4.
The first line of input contains a single integer 'T', representing the number of test cases or queries to be run.
Then the 'T' test cases follow.
The first line of each test case contains two space-separated integers 'N' and 'X', representing the size of the matrix and the target element respectively.
Each of the next 'N' lines contains 'N' space-separated integers representing the elements of the matrix.
For each test case, print the position of 'X', if it exists, otherwise print “-1 -1”.
Note:
It is guaranteed that the matrix contains distinct elements.
You are not required to print the expected output, it has already been taken care of. Just implement the function.
2
3 4
1 2 5
3 4 9
6 7 10
2 5
4 5
8 6
1 1
0 1
1 ≤ T ≤ 10
1 ≤ N ≤ 10^3
1 ≤ X ≤ 10^6
1 ≤ Aij ≤ 10^6
where 'T' is the number of test cases, 'N' is the number of rows and columns, 'X' is the target value, and Aij is the elements of the matrix.
Time Limit : 1 sec
The first test case is already explained in the problem statement.
The second test case, the given matrix is:
[[4, 5],
[5, 6]]
We have to find the position of 5. So we return {0,1}.
2
3 16
2 4 8
3 6 9
4 7 16
1 10
4
2 2
-1 -1
Can we check each element to find a match?
O(N ^ 2), where ‘N’ is the number of rows or columns in the matrix.
There are a total of N * N elements and we are checking each element for a match. Hence, the overall time complexity is O(N ^ 2).
O(1).
Since only constant extra space is required.
All tags
Sort by
Interview problems
Easy Java Solution
public class Solution {
public static Pair search(int [][] matrix, int x) {
// Write your code here.
int l=0,h=matrix[l].length-1;
while(l<matrix.length && h>=0){
if(matrix[l][h]==x) return new Pair(l,h);
if(x<matrix[l][h]) h--;
else l++;
}
return new Pair(-1,-1);
}
}
Interview problems
C++ | O(logn) approach
#include <bits/stdc++.h>
pair<int, int> search(vector<vector<int>> matrix, int x)
{
int n = matrix.size();
int start = 0;
int end = n*n - 1;
while(start <= end){
int mid = start + (end - start) / 2;
int element = matrix[mid/n][mid%n];
if(element == x){
return {mid/n, mid%n};
}
else if(element < x){
start = mid + 1;
}
else{
end = mid - 1;
}
}
return {-1, -1};
}
Interview problems
Both solution Better & Optimal Code
Better
#include <bits/stdc++.h>
pair<int, int> search(vector<vector<int>> matrix, int x)
{
// Write your code here.
pair <int,int> p;
p.first=-1;
p.second=-1;
int i=0;
int n=matrix.size();
int j=n-1;
while(i<n &&j >= 0){
if(x==matrix[i][j]){
p.first=i;
p.second=j;
return p;
}
else if(x>matrix[i][j]) i++;
else j--;
}
return p;
}
Optimal
#include <bits/stdc++.h>
pair<int, int> search(vector<vector<int>> matrix, int x)
{
// Write your code here.
pair <int,int> p;
p.first=-1;
p.second=-1;
int low=0;
int n=matrix.size();
int high=n*n-1;
while(low<=high ){
int mid=(low+high)/2;
if(x==matrix[mid/n][mid%n]){
p.first=mid/n;
p.second=mid%n;
return p;
}
else if(x>matrix[mid/n][mid%n]) low=mid+1;
else high=mid-1;
}
return p;
}Interview problems
Easy Java Solution
public class Solution {
public static Pair search(int [][] matrix, int x) {
int i = 0;
int j = matrix[0].length - 1;
while(i<matrix.length && j >=0){
int temp = matrix[i][j];
if (x == temp){
return new Pair(i,j);
} else if (temp > x){
j--;
} else{
i++;
}
}
return new Pair(-1,-1);
}
}
Interview problems
C++ Easiest Solution | 10 Lines
#include <bits/stdc++.h>
pair<int, int> search(vector<vector<int>> matrix, int x)
{
int n = matrix.size();
int m = matrix[0].size();
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
if(matrix[i][j] == x){
return {i, j};
}
}
}
return {-1,-1};
}Interview problems
Java Solution TC:-O(logn)
public class Solution {
public static Pair search(int [][] matrix, int x) {
// Write your code here.
int i =0;
int j = matrix.length-1;
while(i < matrix.length && j >= 0){
if(matrix[i][j] == x)return new Pair(i,j);
else if(matrix[i][j] > x)j--;
else i++;
}
return new Pair(-1,-1);
}
}Interview problems
Easiest Java Solutions
public static Pair search(int[][] matrix, int x) {
int row = matrix.length;
int column = matrix[0].length;
// Easy solution
// for (int i = 0; i < row; i++) {
// for(int j = 0; j < column; j++){
// if(matrix[i][j] == x){
// return new Pair(i, j);
// }
// }
// }
// return new Pair(-1, -1);
// Alternative solution with less space and time complexity
int i = 0, j = column-1;
while (i < row && j >= 0) {
if(matrix[i][j] == x){
return new Pair(i, j);
}
else if(matrix[i][j] > x) {
j--;
}
else {
i++;
}
}
return new Pair(-1, -1);
}
Interview problems
Easiest CPP approach
#include <bits/stdc++.h>
pair<int, int> search(vector<vector<int>> matrix, int x)
{
// Write your code here.
int row = matrix.size();
int col = matrix[0].size();
int rowInd = 0;
int colInd = col-1;
while(rowInd < row && colInd >= 0){
int element = matrix[rowInd][colInd];
if(element == x){
return {rowInd,colInd};
}
if(element < x){
rowInd++;
}
else{
colInd--;
}
}
return {-1,-1};
}
Interview problems
Search In A Row Wise And Column Wise Sorted Matrix C++ Solution
#include <bits/stdc++.h>
pair<int, int> search(vector<vector<int>> matrix, int x)
{
int row = matrix.size();
int col = matrix[0].size();
int rowIndex = 0, colIndex = col-1;
while(rowIndex < row && colIndex >=0) {
int element = matrix[rowIndex][colIndex];
if(element == x) {
return {rowIndex, colIndex};
}
else if(element < x) {
rowIndex++;
}
else {
colIndex--;
}
}
return {-1, -1};
}
Interview problems
Easy to Understand Efficient Search Algorithm for Sorted Matrices in Java
Input Parameters: The function search takes a 2D matrix (matrix) and an integer (x) as input.
Initialization: The variables len, i, and j are initialized. len represents the length of one side of the square matrix (assuming it's a square matrix). i is initialized to the last index of the matrix (bottom-left corner), and j is initialized to 0 (bottom-left corner).
Search Loop: The code uses a while loop to iterate through the matrix until either i goes below 0 or j exceeds the matrix size.
Inside the loop, it checks if the current element at position (i, j) is equal to the target value x. If true, it creates a Pair object with the indices (i, j) and returns it. If the current element is greater than x, it means the target value may be in the upper row, so it decrements i.
If the current element is less than or equal to x, it means the target value may be in the right column, so it increments j.
Result: If the loop exits without finding the target value, it returns a Pair with indices (-1, -1), indicating that the value was not found in the matrix.
Output: The function returns a Pair representing the indices of the found element or (-1, -1) if the element is not present.
import java.util.*;
import java.io.*;
/*************************************
*
* Following is the Pair Class structure.
*
* class Pair{
* int x; int y;
*
* Pair(int x, int y){
* this.x = x;
* this.y = y;
* }
* }
*
*************************************/
public class Solution {
public static Pair search(int[][] matrix, int x) {
int len = matrix.length - 1;
int i = len;
int j = 0;
while (i > -1 && j <= len) {
if (matrix[i][j] == x) {
return new Pair(i, j);
}
if (matrix[i][j] > x) {
--i;
} else {
j++;
}
}
return new Pair(-1, -1);
}
}
