Leftmost Column with at Least a One

/*
A binary matrix means that all elements are 0 or 1.
For each individual row of the matrix, this row is sorted in non-decreasing order.

Given a row-sorted binary matrix binaryMatrix, return leftmost column index(0-indexed) with at least a 1 in it.
If such index doesn't exist, return -1.

You can't access the Binary Matrix directly.  You may only access the matrix using a BinaryMatrix interface:
  BinaryMatrix.get(x, y) returns the element of the matrix at index (x, y) (0-indexed).
  BinaryMatrix.dimensions() returns a list of 2 elements [n, m], which means the matrix is n * m.
  
Submissions making more than 1000 calls to BinaryMatrix.get will be judged Wrong Answer.
Also, any solutions that attempt to circumvent the judge will result in disqualification.

Example:

0 0 0 0 0 0
0 0 0 1 1 1
0 0 0 0 0 1
0 0 1 1 1 1
0 1 1 1 1 1
0 0 0 0 1 1

Answer: 1 (0-indexed)

Idea:
O(log(M) * N)
Binary search Ones in lines or sublines(from 0, to previously Found Most Left One).

O(N + M)
Imagine there is a pointer p(x, y) starting from top right corner. p can only move left or down.
If the value at p is 0, move down. If the value at p is 1, move left.

*/

/**
 * // This is the BinaryMatrix's API interface.
 * // You should not implement it, or speculate about its implementation
 * interface BinaryMatrix {
 *     public int get(int x, int y) {}
 *     public List<Integer> dimensions {}
 * };
 */

class Solution {
public int leftMostColumnWithOne(BinaryMatrix binaryMatrix) {
        final int N = binaryMatrix.dimensions().get(0);
        final int M = binaryMatrix.dimensions().get(1);

        int mostLeftOne = M + 1;

        for (int i = 0; i < N; i++) {
            if (binaryMatrix.get(i, M - 1) != 0) {
                int currentMostLeftOne = mostLeftOne == M + 1 ? M - 1 : mostLeftOne;
                int current = binarySearchMostLeftOne(binaryMatrix, i, 0, currentMostLeftOne);
                if (current != -1 && current < mostLeftOne) {
                    mostLeftOne = current;
                }
            }
        }

        return mostLeftOne == M + 1 ? -1 : mostLeftOne;
    }

    private int binarySearchMostLeftOne(BinaryMatrix binaryMatrix, int row, int leftIdx, int rightIdx) {
        if (binaryMatrix.get(row, rightIdx) == 0) {
            return -1;
        }

        int initialRight = rightIdx;
        int mostLeftOne = initialRight + 1;
        while (leftIdx <= rightIdx) {
            int middleIdx = leftIdx + (rightIdx - leftIdx) / 2;

            if (binaryMatrix.get(row, middleIdx) == 1) {
                if (middleIdx < mostLeftOne) {
                    mostLeftOne = middleIdx;
                }
                if (middleIdx > 0 && binaryMatrix.get(row, middleIdx - 1) == 1) {
                    rightIdx = middleIdx - 1;
                } else {
                    return mostLeftOne;
                }
            } else {
                leftIdx = middleIdx + 1;
            }
        }
        return mostLeftOne == initialRight + 1 ? -1 : mostLeftOne;
    }
    
    // Starting from top right corner: move down if 0, move left if 1
    public int leftMostColumnWithOne(BinaryMatrix binaryMatrix) {
        final int N = binaryMatrix.dimensions().get(0);
        final int M = binaryMatrix.dimensions().get(1);
    
        boolean foundOne = false;

        int i = 0;
        int j = M - 1;
    
        while(i < N && j >= 0){
            if(binaryMatrix.get(i, j) == 0) {
                i++;
            } else { 
                // binaryMatrix.get(i, j) == 1
                j--;
                foundOne = true;
            }
        }
    
        return foundOne == false ? -1 : j + 1;
    }

}