Update appNew update is available. Click here to update.
sidenav-btnClose
Topic list
Search In A Row Wise And Column Wise Sorted Matrix
MEDIUM
15 mins
37 upvotes
Matrices (2D Arrays)
Sorting
Binary Search
Topics (Covered in this problem)
Problem solved
Badge
Skill meter
Matrices (2D Arrays)
-
-
Sorting
-
-
Binary Search
-
-
Other topics
Problem solved
Badge
Skill meter
Strings
-
-
Linked List
-
-
Stacks & Queues
-
-
Trees
-
-
Graph
-
-
Dynamic Programming
-
-
Greedy
-
-
Tries
-
-
Arrays
-
-
SQL
-
-
Binary Search Trees
-
-
Heap
-
-
Bit Manipulation
-
-
Solve problems & track your progress
Checkout your overall progress in every topic here
Become
userLevel
Sensei
in DSA topics
Open the topic and solve more problems associated with it to improve your skills
Check out the skill meter for every topic
See how many problems you are left with to solve for cracking any stage. Score more than zero to get your progress counted.

Search In A Row Wise And Column Wise Sorted Matrix

Contributed by
Sounak Majumder
Medium
yellow-spark
0/80
Avg time to solve 15 mins
Success Rate 80 %
Share
37 upvotes

Problem Statement

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}

For example: 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.
Detailed explanation ( Input/output format, Notes, Constraints, Images )
Sample Input 1:
2
3 4
1 2 5
3 4 9
6 7 10
2 5
4 5
8 6
Sample Output 1:
1 1
0 1
Explanation of Input 1:
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}.
Sample Input 2:
2
3 16
2 4 8
3 6 9
4 7 16
1 10
4
Sample Output 2
2 2
-1 -1
Reset Code
Full screen
Auto
copy-code
Console