Our June 2021 cohorts are filling up quickly. Join our free webinar to Uplevel your career # 2D Array Search Problem

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]

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

##### Example One

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 and x=7 is present at arr. Hence, "present" returned for them, while

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

##### Example Two

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.

##### Notes

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

• 1

• 1

• -10^9

• -10^9

#### Solution

We provided three solutions.

#### 1) brute_force_solution.java

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

##### Time Complexity:

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

##### Auxiliary Space Used:

O(1).

As we are not storing anything extra.

##### Space Complexity:

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

``````
// -------- START --------
static String isPresent(int[][] arr, int x) {
int r = arr.length;
int c = arr.length;
// Iterate over entire input array to check if x is present or not
for (int i = 0; i < r; i++) {
for (int j = 0; j < c; j++) {
if (arr[i][j] == x) {
return "present";
}
}
}
return "not present";
}

// -------- END --------
``````

#### 2) optimal_solution.java

1) Start with top right element arr[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].

##### Time Complexity:

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

##### Auxiliary Space Used:

O(1).

As we are not storing anything extra.

##### Space Complexity:

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

``````
// -------- START --------
static String isPresent(int arr[][], int x) {
int r = arr.length;
int c = arr.length;
int rowIndex = 0;
int colIndex = c - 1;
// Starting from 0th row, find first element from right in current row, let say a[l][m], such
// that a[l][m] <= x.
while(rowIndex <= (r-1) && colIndex >= 0){
// arr[rowIndex][colIndex] is the first element from right in current row rowIndex.
if (arr[rowIndex][colIndex] == x){
return "present";
}

// As arr is sorted row wise and column wise in increasing order,
// we can say that x can't be present at arr[l][m], rowIndexrowIndex and m>colIndex
if (arr[rowIndex][colIndex] < x){
rowIndex++;
}
// As arr is sorted row wise and column wise in increasing order,
// we can say that if x < arr[rowIndex][colIndex] means x can be present
// on left side of colIndex in same row rowIndex.
else if(arr[rowIndex][colIndex] > x){
colIndex--;
}
}
return "not present";
}
// -------- END --------
``````

### Try yourself in the Editor

Note: Input and Output will already be taken care of.

All Posts