Register for our webinar

1 hour

Step 1

Step 2

Congratulations!

You have registered for our webinar

Oops! Something went wrong while submitting the form.

Step 1

Step 2

Confirmed

You are scheduled with Interview Kickstart.

Redirecting...

Oops! Something went wrong while submitting the form.

Head of Career Skills Development & Coaching

*Based on past data of successful IK students

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.

```
{
"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.

```
{
"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.

Constraints:

- 1 <=
`r`

<= 10^{3} - 1 <=
`c`

<= 10^{3} - 1 <=
`q`

<= 10^{4} - -10
^{9}<=`numbers[i][j]`

<= 10^{9}, for all`i`

and`j`

- -10
^{9}<=`x`

<= 10^{9}

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`

.

A naive approach would be to iterate over the entire input array `numbers`

to check if `x`

is present or not.

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

O(1).

As we are not storing anything extra.

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

```
/*
* 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;
}
```

- Start with top right element
`numbers[0][c - 1]`

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

).

- If
- 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]`

.

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

O(1).

As we are not storing anything extra.

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

```
/*
* 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.

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

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.

```
{
"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.

```
{
"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.

Constraints:

- 1 <=
`r`

<= 10^{3} - 1 <=
`c`

<= 10^{3} - 1 <=
`q`

<= 10^{4} - -10
^{9}<=`numbers[i][j]`

<= 10^{9}, for all`i`

and`j`

- -10
^{9}<=`x`

<= 10^{9}

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`

.

A naive approach would be to iterate over the entire input array `numbers`

to check if `x`

is present or not.

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

O(1).

As we are not storing anything extra.

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

```
/*
* 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;
}
```

- Start with top right element
`numbers[0][c - 1]`

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

).

- If
- 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]`

.

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

O(1).

As we are not storing anything extra.

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

```
/*
* 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.

**Attend our free webinar to amp up your career and get the salary you deserve.**

Hosted By

Ryan Valles

Founder, Interview Kickstart