Problem Explanation

This problem is related to a row-sorted binary matrix and we have to find and return the leftmost column index (0-indexed) that contains at least a 1. If no such column exists, return -1.

We have to interface with the BinaryMatrix in the following ways:

• BinaryMatrix.get(row, col) - returns the element of the matrix at index (row, col) (0-indexed).
• BinaryMatrix.dimensions() - returns a list of two elements, [rows, cols] indicating the dimension of the matrix.

The problem also specifies that any solution that makes more than 1000 calls to BinaryMatrix.get will be judged as Wrong Answer, and any attempts to circumvent the judge will result in disqualification.

Let's understand the problem better, with an example:

Example 1: Input: mat = [[0,0],[1,1]] Output: 0 In this example, the leftmost column index containing a 1 is column 0 (zero-indexed) of the second row, which contains a 1. Hence the output is 0.

Solution Walkthrough

By reading through the problem statement and looking at its constraints, binary search is a good candidate to solve this problem with the required efficiency.

The solution runs a binary search on the columns and checks whether the mid column contains a 1. If a 1 exists, it moves to the left (mid - 1) to check whether there are any 1s in that column. In doing so, it ensures that it covers the left side, giving you the left most column. If no 1s exist in the mid column, it moves to the next column (mid + 1).

With the binary search algorithm, it checks a lesser number of columns which makes it efficient against the problem's stringent constraints.

C++ Solution

1
2cpp
3class Solution {
4 public:
5  int leftMostColumnWithOne(BinaryMatrix& binaryMatrix) {
6    const vector<int> dimensions = binaryMatrix.dimensions();  // get dimensions of matrix
7    const int rows = dimensions[0];
8    const int cols = dimensions[1];
9    int low = 0;
10    int high = cols - 1;
11
12    while (low <= high) {
13      const int mid = (low + high) / 2;
14      if (existOne(binaryMatrix, rows, mid)) { 
15        high = mid - 1;  // 1 exists, moving left to find more 1s.
16      } else {
17        low = mid + 1;  // 1 doesn't exist in mid, moving right.
18      }
19    }
20
21    return high == -1 ? -1 : low;
22  }
23
24 private:
25  bool existOne(BinaryMatrix& binaryMatrix, int rows, int col) {
26    for (int i = 0; i < rows; ++i)
27      if (binaryMatrix.get(i, col) == 1)
28        return true;
29    return false;
30  }
31};

The solution will look very similar in other languages. Please note that this specific question can only be actually solved in C++ on the LeetCode platform due to the definition of the BinaryMatrix interface required by the problem in other languages.# Python pseudocode

The exact translation of the above mentioned C++ code cannot be done into Python, JavaScript or Java due to the constraints in the problem. However, if we were to solve this problem abstractly in Python, it might look something like the following:

Since we don't have actual BinaryMatrix class, let's consider a helper function existOne to use in our solution which takes an argument as the matrix.

1
2python
3def get_leftmost_one(matrix):
4  rows = len(matrix)
5  cols = len(matrix[0])
6  low, high = 0, cols - 1
7
8  while low <= high:
9    mid = (low + high) // 2  #Note that // is used for integer division in Python3
10    if existOne(matrix, rows, mid): 
11      high = mid - 1
12    else:
13      low = mid + 1
14      
15  return high if high != -1 else -1
16
17def existOne(matrix, rows, col):
18  for i in range(rows):
19    if matrix[i][col] == 1:
20      return True
21  return False

JavaScript Pseudocode

The same logic is used when written in Javascript:

1
2javascript
3function get_leftmost_one(matrix) {
4  let rows = matrix.length;
5  let cols = matrix[0].length;
6  let low = 0, high = cols - 1;
7
8  while (low <= high) {
9    let mid = Math.floor((low + high) / 2);
10    if (existOne(matrix, rows, mid)) 
11      high = mid - 1; 
12    else
13      low = mid + 1; 
14  }
15
16  return high != -1 ? high : -1;
17}
18
19function existOne(matrix, rows, col) {
20  for (let i = 0; i < rows; i++)
21    if (matrix[i][col] == 1)
22      return true;
23  return false;
24}

Java Pseudocode

Even if we were to solve this in java, we would follow the same basic logic:

1
2java
3public int get_leftmost_one(int[][] matrix) {
4  int rows = matrix.length;
5  int cols = matrix[0].length;
6  int low = 0, high = cols - 1;
7
8  while (low <= high) {
9    int mid = (low + high) / 2;
10    if (existOne(matrix, rows, mid)) 
11      high = mid - 1; 
12    else
13      low = mid + 1; 
14  }
15
16  return high != -1 ? high : -1;
17}
18
19private boolean existOne(int[][] matrix, int rows, int col) {
20  for (int i = 0; i < rows; i++)
21    if (matrix[i][col] == 1)
22      return true;
23  return false;
24}

Remember that although this logic works well for row sorted binary matrices, it cannot be applied as such in the given problem statement due to the constraint of the problem and the BinaryMatrix API as it is applicable only for C++.