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] <= 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. 

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[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

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.

Constraints:

• 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

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[0].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[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].

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[0].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 --------