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).