2D Array Search Problem Statement

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

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

Example One

{
"numbers": [
[1, 2, 3, 12],
[4, 5, 6, 45],
[7, 8, 9, 78]
],
"queries": [6, 7, 23]
}

Output:

[1, 1, 0]

Given number x = 6 is present at numbers[1][2] and x = 7 is present at numbers[2][0]. Hence, 1 returned for them, while x = 23 is not present in numbers, hence 0 returned.

Example Two

{
"numbers": [
[3, 4],
[5, 10]
],
"queries" = [12, 32]
}

Output:

[0, 0]

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

Notes

Constraints:

• 1 <= r <= 10³
• 1 <= c <= 10³
• 1 <= q <= 10⁴
• -10⁹ <= numbers[i][j] <= 10⁹, for all i and j
• -10⁹ <= x <= 10⁹

We provided three solutions.

Let us denote number of rows in numbers as r , number of columns in numbers as c and number of queries as q.

2D Array Search Solution 1: Brute Force

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

Time Complexity

O(r * c * q).

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

Space used for input: O((r * c) + q).

Auxiliary space used: O(1).

Space used for output: O(q).

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

Code For 2D Array Search Solution 1: Brute Force

    /*
    * Asymptotic complexity in terms of number of rows \`r\`, number of columns \`c\` and number of queries \`q\`:
    * Time: O((r * c) * q).
    * Auxiliary space: O(1).
    * Total space: O(r * c + q).
    */

    static Boolean process_query(ArrayList<ArrayList<Integer>> numbers, Integer x) {
        int r = numbers.size();
        int c = numbers.get(0).size();
        // Iterate over input numbers to check if x is present or not
        for (int i = 0; i < r; i++) {
            for (int j = 0; j < c; j++) {
                if (numbers.get(i).get(j).intValue() == x.intValue()) {
                    return true;
                }
            }
        }
        return false;
    }

    static ArrayList<Boolean> search(ArrayList<ArrayList<Integer>> numbers, ArrayList<Integer> queries) {
        ArrayList<Boolean> result = new ArrayList<Boolean>();
        for(int i = 0; i < queries.size(); i++){
            result.add(process_query(numbers, queries.get(i)));
        }
        return result;
    }

2D Array Search Solution 2: Optimal

1. Start with top right element numbers[0][c - 1].
2. Loop: compare this element numbers[i][j] with x
   • If numbers[i][j] == x, then return 1.
   • If numbers[i][j] < x, then move to next row (i.e. numbers[i + 1][j]).
   • If numbers[i][j] > x, then move to column to its left (i.e. numbers[i][j - 1]).
3. repeat the steps in #2 till you find element and return 1 OR if out of bound of matrix then break and return 0.

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

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

• If it is equal to x, then problem solved, directly return 1.
• If numbers[i][j] < x, it can be implied that x cannot be present at numbers[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. numbers[i + 1][j]).
• If numbers[i][j] > x, means element x can be present in the left side of column j-th as row and column are sorted in ascending order. So, we start checking it with numbers[i][j - 1].

Time Complexity

O((r + c) * q).

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

Space used for input: O((r * c) + q).

Auxiliary space used: O(1).

Space used for output: O(q).

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

Code For 2D Array Search Solution 2: Optimal

    /*
    * Asymptotic complexity in terms of number of rows \`r\`, number of columns \`c\` and number of queries \`q\`:
    * Time: O((r + c) * q).
    * Auxiliary space: O(1).
    * Total space: O(r * c + q).
    */

    static Boolean process_query(ArrayList<ArrayList<Integer>> numbers, Integer x) {
        int r = numbers.size();
        int c = numbers.get(0).size();
        int rowIndex = 0;
        int colIndex = c - 1;
        // Starting from 0th row, find first element from right in current row, let us say a[l][m], such
        // that a[l][m] <= x.
        while(rowIndex <= (r - 1) && colIndex >= 0){
            // numbers[rowIndex][colIndex] is the first element from right in current row rowIndex.
            if (numbers.get(rowIndex).get(colIndex).intValue() == x.intValue()){
                return true;
            }

            // As numbers is sorted row wise and column wise in increasing order,
            // we can say that x can't be present at numbers[l][m], rowIndex < l and colIndex < m
            // Also, in current row rowIndex, x can't be present as numbers[rowIndex][colIndex] < x and
            // all elements to its left are even smaller than numbers[rowIndex][colIndex] and
            // we have already checked all elements to its right. So moving on to next row.
            // Notice that you can start to check at current column j (stored in colIndex) in next row as x can't
            // be present at numbers[l][m], l > rowIndex and m > colIndex
            if (numbers.get(rowIndex).get(colIndex).intValue() < x.intValue()){
                rowIndex++;
            }
            // As numbers is sorted row wise and column wise in increasing order,
            // we can say that if x < numbers[rowIndex][colIndex] means x can be present
            // on left side of colIndex in same row rowIndex.
            else if(numbers.get(rowIndex).get(colIndex).intValue() > x.intValue()){
                colIndex--;
            }
        }
        return false;
    }

    static ArrayList<Boolean> search(ArrayList<ArrayList<Integer>> numbers, ArrayList<Integer> queries) {
        ArrayList<Boolean> result = new ArrayList<Boolean>();
        for(int i = 0; i < queries.size(); i++){
            result.add(process_query(numbers, queries.get(i)));
        }
        return result;
    }

We hope that these solutions to searching a number in a matrix have helped you level up your coding skills. You can expect problems like these at top tech companies like Amazon and Google.

If you are preparing for a tech interview at FAANG or any other Tier-1 tech company, register for Interview Kickstart’s FREE webinar to understand the best way to prepare.

Interview Kickstart offers interview preparation courses taught by FAANG+ tech leads and seasoned hiring managers. Our programs include a comprehensive curriculum, unmatched teaching methods, and career coaching to help you nail your next tech interview.

We offer 18 interview preparation courses, each tailored to a specific engineering domain or role, including the most in-demand and highest-paying domains and roles, such as:

• Back-end Engineering Interview Course
• Front-end Engineering Interview Course
• Full Stack Developer Interview Course

‍To learn more, register for the FREE webinar.