Search In A Grid

Moderate
0/80
Average time to solve is 15m
profile
Contributed by
19 upvotes
Asked in companies
ArcesiumSquadstackHashedIn

Problem statement

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.

Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1 :
2
2 2 4
1 2 
3 4
1 1 5
1
Sample Output 1:
True
False
Explanation for sample input 1:
For test case 1,
The element 4 is present at index (1,1) (0 based indexing).
For test case 2,
The element 4 is not present in grid.
Sample Input 2 :
1
3 3 6
2 4 6
7 8 9
10 11 12
Sample Output 2:
True
Hint

Check every cell of the grid.

Approaches (3)
Brute Force
  • 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’.
Time Complexity

O(N*M), where N is the number of rows of the grid and M is the number of columns of the grid.

 

As in the worst case, every element of the grid will be visited at most once. Hence, the time complexity will be O(N*M). 

Space Complexity

O(1), constant space is used.

Code Solution
(100% EXP penalty)
Search In A Grid
Full screen
Console