1428.Leftmost Column with at Least a One

Tags: Binary Search Medium

Links: https://leetcode.com/explore/challenge/card/30-day-leetcoding-challenge/530/week-3/3306/

---

(This problem is an **interactive problem*.)*

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.

For custom testing purposes you're given the binary matrix mat as input in the following four examples. You will not have access the binary matrix directly.

Example 1:

Input: mat = [[0,0],[1,1]]
Output: 0

Example 2:

Input: mat = [[0,0],[0,1]]
Output: 1

Example 3:

Input: mat = [[0,0],[0,0]]
Output: -1

Example 4:

Input: mat = [[0,0,0,1],[0,0,1,1],[0,1,1,1]]
Output: 1

Constraints:

• 1 <= mat.length, mat[i].length <= 100
• mat[i][j] is either 0 or 1.
• mat[i] is sorted in a non-decreasing way.

---

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

class Solution {
public:
    int leftMostColumnWithOne(BinaryMatrix &binaryMatrix) {
        std::ios_base::sync_with_stdio(false);
        cin.tie(NULL);
        cout.tie(NULL);

        auto v = binaryMatrix.dimensions();
        int m = v[0], n = v[1];

        int res = INT_MAX;
        for (int i = 0; i < m; ++i) {
            int left = 0, right = n;
            while (left < right) {
                int mid = left + ((right - left) >> 1);
                if (binaryMatrix.get(i, mid) == 0) left = mid + 1;
                else right = mid;
            }
            if (left != n) res = min(res, left);
        }

        return res == INT_MAX ? -1 : res;
    }
};

一道交互式类型的题目，题意是你不能访问这个数组，但是可以通过两个函数来得到一些信息。因为每一行都是单调的，所以考虑每一行使用二分搜索。题目限定使用get函数的次数不能超过1000次，也就是你不能暴力访问数组，另外还是为了计算时间复杂度。时间复杂度是$O(m \log n)$，也就是$200\log _2 10 \leq 700$。类似的题目其实就是矩阵查找类型的问题。