Register for our webinar

### How to Nail your next Technical Interview

1 hour
1
Enter details
2
Select webinar slot
*Invalid Name
*Invalid Name
Step 1
Step 2
Congratulations!
You have registered for our webinar
Oops! Something went wrong while submitting the form.
1
Enter details
2
Select webinar slot
*All webinar slots are in the Asia/Kolkata timezone
Step 1
Step 2
Confirmed
You are scheduled with Interview Kickstart.
Redirecting...
Oops! Something went wrong while submitting the form.

## You may be missing out on a 66.5% salary hike*

### Nick Camilleri

Head of Career Skills Development & Coaching
*Based on past data of successful IK students
Help us know you better!

## How many years of coding experience do you have?

Oops! Something went wrong while submitting the form.

## FREE course on 'Sorting Algorithms' by Omkar Deshpande (Stanford PhD, Head of Curriculum, IK)

Oops! Something went wrong while submitting the form.

# 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` <= 103
• 1 <= `c` <= 103
• 1 <= `q` <= 104
• -109 <= `numbers[i][j]` <= 109, for all `i` and `j`
• -109 <= `x` <= 109

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++){
}
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++){
}
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:

### Try yourself in the Editor

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

# 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` <= 103
• 1 <= `c` <= 103
• 1 <= `q` <= 104
• -109 <= `numbers[i][j]` <= 109, for all `i` and `j`
• -109 <= `x` <= 109

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++){
}
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++){
}
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: