Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding
Ninjas X Naukri.com

Last Updated: 24 Feb, 2021

Moderate

```
We are following 0-based indexing for this problem. The get method should be called for a max of 2000 times, and the dimensions method should be called only once. Submissions making more than 2000 calls to the get method and more than one call to the dimensions will be judged as the wrong answers.
```

```
If the BinaryMatrix has 2 rows and 3 columns and the matrix is {{0, 0, 0}, {0, 1, 1}}. Then, both the second and the third columns contain a 1, but the second column is the leftmost column. Hence, the answer is 1 (0-based indexing).
```

```
Note that, here, the BinaryMatrix is given as an example. In the actual problem, you have to access the elements of the matrix by using the BinaryMatrix.get() method.
```

```
The first line contains an integer 'T', which denotes the number of test cases or queries to be run. Then, the T test cases follow.
The first line of each test case contains two space-separated integers M and N, denoting the number of rows and the number of columns in the matrix, respectively.
Then M lines follow. Each line contains N space-separated integers denoting elements of the matrix.
Note that the input is given for reference. You can’t access the elements of the matrix directly. You have to use the get method to do so.
```

```
For each test case, print the leftmost index (0-based indexing) of the column such that it contains at least one 1. If such a column doesn’t exist in the matrix, then return -1.
Output for each test case will be printed in a separate line.
If the program calls the get method more than 2000 times or the dimensions function more than once, then it will be judged as a wrong answer, and the program stops instantly.
```

```
You do not need to print anything. It has already been taken care of. Just implement the given function.
```

```
1 <= T <= 5
1 <= M <= 1000
1 <= N <= 1000
0 <= BinaryMatrix[i][j] <= 1
Time limit: 1 second
```

The idea here is to access all the elements of the matrix column-wise, i.e., access all the elements of the 0-th column first, then the first column, and so on until we find a 1.

Since the get method will be called for more than 2000 times in matrices having more than 2000 elements, so this approach will be judged as wrong answers in those cases.

- Call
**dimensions()**and store the rows and columns of the matrix in two variables named**M**and**N,**respectively. - Run a loop from
**i**= 0 to**N**and do:- Run a loop from
**j**= 0 to**M**and do:- If
**get(j, i)**== 1, then return**i**.

- If

- Run a loop from
- Finally, return -1.

We can improve the previous approach by using the fact that the binary matrix is row-wise sorted. So, we can apply a binary search on each row of the matrix to find the leftmost column that contains 1. Then, we keep a “leftMost” variable to store the leftmost column across all the rows.

In this approach, the get method will be called for M log N times. So, for a matrix having M = 1000 and N = 1000, the number of calls will be more than 2000. So this approach will be judged as wrong answers in such cases.

- Call
**dimensions()**and store the rows and columns of the matrix in two variables named**M**and**N,**respectively. - Create a
**leftMost**variable and initialize it to**N**. - Run a loop from
**i**= 0 to**M**and do:- Call the function
**binarySearch(i, N)**to find the leftmost column containing the 1 in the**i**-th row and store it in a variable, say**currColumn**. - Make
**leftMost**= min(**leftMost**, currColumn).

- Call the function
- If
**leftMost**==**N**, that means there is no 1 present in the matrix. So, we return -1. Else, return**leftMost**.

- Take two variables
**left**and**right**and initialize them to 0 and**N**respectively. - While
**left**<**right**do:- Create a
**mid**variable and make**mid**=**left**+ (**right**-**left**) / 2. - If
**get(row, mid)**!= 1, then make**left**=**mid**+ 1. - Else make
**right**=**mid**.

- Create a
- Finally, return
**left**.

We will follow a two-pointer approach. We first access the element present at the last index of the first column. So, we take two pointers, i and j, initializing them to 0 and N - 1, respectively. Now, there are two options, i.e., either the current element is 1 or it is 0.

- If the current element is 1, then we can decrement the column index (denoted by j here) by 1. As we already find a 1 in the current column, so we don’t need to search in the same column again.
- If the current element is 0, then we can increment the row index (denoted by i here) by 1. Since the matrix is row-wise sorted, so if the current element is 0, all the previous elements in the same row will be 0 as well.

In this approach, the get method will be called for M + N times.

- Call
**dimensions()**and store the rows and columns of the matrix in two variables named**M**and**N**respectively. - Create a
**leftMost**variable and initialize it to -1. - Take two pointers named
**i**and**j**. Initially,**i**points to 0, and**j**points to**N**- 1. - While
**i**<**M**and**j**>= 0 do:- If
**get(i, j)**== 1, then make**leftMost**=**j**and decrement**j**by 1. - Else, increment
**i**by 1.

- If
- Finally, return
**leftMost**.

Similar problems