1428. Leftmost Column with at Least a One

binary search

time: O(m*logn)

space: O(1)

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

class Solution {
    public int leftMostColumnWithOne(BinaryMatrix binaryMatrix) {
        List<Integer> dim = binaryMatrix.dimensions();
        int m = dim.get(0);
        int n = dim.get(1);
        int leftMost = n; // if all 0, at last leftMost will be n
        
        for (int i = 0; i < m; i++) {
            int left = 0;
            int right = leftMost; // this is the key, upbound should be updated each time
            while (left < right) {
                int mid = (left + right) >>> 1;
                
                if (binaryMatrix.get(i, mid) == 1) {
                    right = mid;
                } else {
                    left = mid + 1; // cant find 1, keep moving to right part
                }
            }
            leftMost = left;
        }
        return leftMost == n ? -1 : leftMost;
    }
}

這裡要注意, 右邊界用 n, 而不是 n-1, 用 n-1 最後會無法判斷 是真的全 0, 還是最右邊真的是 1

ex: 00

01

linear solution

the idea is the same as leetcode 240

time: O(m+n)

space: O(1)

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

class Solution {
    public static int leftMostColumnWithOne(BinaryMatrix binaryMatrix) {
        List<Integer> dim = binaryMatrix.dimensions();
        int m = dim.get(0);
        int n = dim.get(1);
        
        int res = -1;
        int rowIndex = 0;
        int colIndex = n-1;
        
        while (rowIndex < m && colIndex >= 0) {
            int value = binaryMatrix.get(rowIndex, colIndex);
            if (value == 1) {
                res = colIndex;
                colIndex--;
            } else {
                rowIndex++;
            }
        }
        
        return res;
    }
}