You are given a sorted two-dimensional integer array arr of size r * c, where all the numbers are in non-decreasing order from left to right and top to bottom. I.e. arr[i][j] <= arr[i+1][j] and arr[i][j] <= arr[i][j+1] for all i = 0,1,...,(r - 2) and j = 0,1,...,(c - 2).

Check if a given number x exists in arr or not. Given an arr, you have to answer q such queries.

Input: arr = [[1, 2, 3, 12], [4, 5, 6, 45], [7, 8, 9, 78]], queries = [6, 7, 23]

Output: [“present”, “present”, “not present”]

Given number x=6 is present at arr[1][2] and x=7 is present at arr[2][0]. Hence, "present" returned for them, while

x=23 is not present in arr, hence "not present" returned

Input: arr = [[3, 4], [5, 10]], queries = [12, 32]

Output: [“not present”, “not present”]

Given number x=12 and x=32 are not present in arr. Hence, "not present" returned for both of the queries.

Input Parameters: There are two arguments, arr and x, denoting input 2D array and a number to be searched as mentioned in problem statement respectively

Output: Return string "present" if x is present in arr, string "not present" otherwise.

• 1 <= r <= 10^3

• 1 <= c <= 10^3

• 1 <= q <= 10^4

• -10^9 <= arr[i][j] <= 10^9, (i = 0,1,...,(r - 1) and j = 0,1,...,(c - 1))

• -10^9 <= x <= 10^9

We provided three solutions.

A naive approach would be to iterate over the entire input array arr to check if x is present or not.

O(r*c*q) where r denotes number of rows of arr, c denotes number of columns of arr and q denotes number of queries.

As we are iterating over entire array for each query, time complexity will be O(r*c) (for each query) and as there are q queries so total time complexity will be O(r*c*q).

O(1).

As we are not storing anything extra.

O(r*c) where r denotes number of rows of arr and c denotes number of columns of arr.

To store input, it would take O(r*c), auxiliary space used is O(1).

So, total space complexity will be O(r*c).

1) Start with top right element arr[0][c-1]

2) Loop: compare this element arr[i][j] with x

-> If arr[i][j] == x, then return "present"

-> If arr[i][j] < x then move to next row (i.e. arr[i+1][j])

-> If arr[i][j] > x then move to column to its left (i.e. arr[i][j-1])

3) repeat the steps in #2 till you find element and return "present" OR if out of bound of matrix then break and return "not present"

Let say x is not present in the first i-1 rows.

Let's say in i-th row, arr[i][j] is the largest number smaller than or equal to x.

-> If it is equal to x, then problem solved, directly return “present”.

-> If arr[i][j] < x, it can be implied that x cannot be present at arr[l][m], i < l and j < m as array is row wise and column wise sorted (ascending). So, moving on to the next row, i+1-th row, we can start checking from j-th column (i.e. arr[i+1][j]).

-> If arr[i][j] > x, means element x can be present in the left side of column jth as row and column are sorted in ascending order. So, we start checking it with arr[i][j-1].

O((r+c)*q) where r denotes number of rows of arr, c denotes number of columns of arr and q denotes number of queries.

As for each query maximum iteration over array can be of O(r+c) and as there can be q queries so, total complexity will be O((r+c)*q).

O(1).

As we are not storing anything extra.

O(r*c) where r denotes number of rows of arr and c denotes number of columns of arr.

To store input, it would take O(r*c), auxiliary space used is O(1).

So, total space complexity will be O(r*c).