# 【LeetCode】 Leftmost Column with at Least a One

## Description
> (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.

> 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.

> (這是一個互動式問題)

> 一個二元陣列表示所有元素都是`0`或`1`。陣列中每一個個別的row都經過非遞減排序。

> 給一個row都排序過的二元陣列，回傳`1`再最左邊的column索引值(從零開始算)。如不存在任何`1`就回傳`-1`。

> 你不能直接存取二元陣列。你只能使用`BinaryMatrix`的interface去使用：
> * `BinaryMatrix.get(x, y)`回傳位於`(x, y)`的元素(從零開始算)。
> * `BinaryMatrix.dimensions()`回傳包含兩個元素`[n, m]`的list，代表該陣列大小為`n * m`。

> 使用了超過`1000`次的BinaryMatrix.get將被判定錯誤，並且任何試圖走後門的方式都會被取消資格。

> 為了方便測試，下面提供了四個陣列。你不能直接存取它們。

> 限制：
> * `1 <= mat.length, mat[i].length <= 100`
> * `mat[i][j]` 只會是 `0` 或 `1`.
> * `mat[i]` 會按照非遞減順序排列。

## Example:

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

1. 
2. 
3. 
4. 

## Solution

* 先說，這題的`x` `y`給的感覺很奇怪，我一直搞反它們，因此這邊只講概念，下面的code雖然會過但請參考就好。
* 題目給的矩陣中，`1`一定在右邊，需要找到哪一排擁有最多的`1`(`1`在最左邊)。
* 最直覺的方法當然就是整個矩陣都給他看過去，然後包準你不會過。
* 比較省時間的方法是從最右上角開始跑：
* 如果遇到`1`，往左走一格。
* 如果遇到`0`，往下走一格。
* 直到最下面為止結束。
* 最後要注意，最後會停在`0`的地方，因此答案要加一。
* 並且處理全為`0`的陣列，即可成功。

### Code

/**
 * // 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) {
        vector<int> s = binaryMatrix.dimensions();
        int y = s[1] - 1;
        int x = 0;
        while(x < s[0] && y >= 0)
        {
            if(binaryMatrix.get(x, y) == 0)
                x++;
            else
                y--;
        }
        if(y + 1 == s[1]) return -1;
        return y + 1;
    }
};

###### tags: `LeetCode` `C++`