Last Updated: 24 Dec, 2020
Search In A Grid
Moderate
Asked in companies
You are given a grid ‘MAT’ of ‘N’ rows and ‘M’ columns with positive integers written in each cell.
The grid has the following properties-
• Integers in each row are sorted in ascending order from left to right.
• Integers in each column are sorted in ascending order from top to bottom.
You are also given a positive integer ‘target’. Your task is to find whether ‘target’ is present inside the grid or not.
Input Format
The first line of input contains an integer ‘T’ denoting the number of test cases to run. Then the test case follows.
The first line of each test case contains three space separated integers ‘N’ ‘M’ and ‘target’ denoting the number of rows and columns in the matrix and the target integer respectively.
The next ‘N’ lines of each test case contain ‘M’ space-separated integers each representing the rows of ‘MAT’
Output Format :
For each test case, print "True" if ‘target’ is present inside the grid, else print "False".
Note:
You do not need to print anything; it has already been taken care of. Just implement the given function.
Constraints:
1 <= T <= 50
1 <= N, M <= 500
1 <= MAT[i][j] <= 10^5
Where 'MAT[i][j]' is the element present at 'i'th row and 'j'th column of 'MAT'.
Time Limit: 1sec
Approaches
- We can traverse the whole grid with the help of two nested loops.
- If at any cell of the grid we find ‘target’, we will return ‘true’.
- If ‘target’ is not present in any cell, we will return ‘false’.
- Since, elements in each row are sorted we can use Binary Search to search for ‘target’ in each row.
- If in any row of the grid we find ‘target’, we will return ‘true’.
- If ‘target’ is not present in any row, we will return ‘false’.
Let MAT[i][j] denote an element in the grid ‘MAT’. The key observation here is that-
- If target > MAT[i][j], then we can discard the left of the current row.
- Similarly, if target < MAT[i][j], we can discard the lower part of the current column.
- We can do a linear search from the bottom left of the grid based on these observations.
The algorithm will be-
- Let ‘currRow’ and ‘currCol’ denote the row and column currently we are in the grid.
- Then, ‘currRow’ will be initialized to N - 1 and ‘currCol’ to 0.
- While (currRow >= 0 and currCol < M):
- If (MAT[currRow][currCol] == target), we return true.
- If (MAT[currRow][currCol] > target), we decrement ‘currRow’ by 1.
- If (MAT[currRow][currCol] < target), we increment ‘currCol’ by 1.
- If no such cell is found we return false.
Similar problems
Sorted Doubly Linked List to Balanced BST
Easy
Posted: 3 Nov, 2025
Largest Plus Sign
Hard
Posted: 8 Dec, 2025
Minimum Operations to Form Letter Y
Moderate
Posted: 8 Dec, 2025
Matrix Block Sum
Easy
Posted: 3 Jan, 2026
Minimized Maximum of Products Distributed to Any Store
Moderate
Posted: 22 Feb, 2026