Question

1428. Leftmost Column with at Least a One

中文文档

Description

A row-sorted binary matrix means that all elements are 0 or 1 and each row of the matrix is sorted in non-decreasing order.

Given a row-sorted binary matrix binaryMatrix, return _the index (0-indexed) of the leftmost column with a 1 in it_. If such an index does not exist, return -1.

You can't access the Binary Matrix directly. You may only access the matrix using a BinaryMatrix interface:

• BinaryMatrix.get(row, col) returns the element of the matrix at index (row, col) (0-indexed).
• BinaryMatrix.dimensions() returns the dimensions of the matrix as a list of 2 elements [rows, cols], which means the matrix is rows x cols.

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, the input will be the entire binary matrix mat. You will not have access to 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

 

Constraints:

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

Solutions

Solution 1: Binary Search

First, we call BinaryMatrix.dimensions() to get the number of rows $m$ and columns $n$ of the matrix. Then for each row, we use binary search to find the column number $j$ where the leftmost $1$ is located. The smallest $j$ value that satisfies all rows is the answer. If there is no such column, return $-1$.

The time complexity is $O(m \times \log n)$, where $m$ and $n$ are the number of rows and columns of the matrix, respectively. We need to traverse each row, and use binary search within each row, which has a time complexity of $O(\log n)$. The space complexity is $O(1)$.

# """
# This is BinaryMatrix's API interface.
# You should not implement it, or speculate about its implementation
# """
# class BinaryMatrix(object):
#  def get(self, row: int, col: int) -> int:
#  def dimensions(self) -> list[]:


class Solution:
  def leftMostColumnWithOne(self, binaryMatrix: "BinaryMatrix") -> int:
    m, n = binaryMatrix.dimensions()
    ans = n
    for i in range(m):
      j = bisect_left(range(n), 1, key=lambda k: binaryMatrix.get(i, k))
      ans = min(ans, j)
    return -1 if ans >= n else ans

/**
 * // 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> e = binaryMatrix.dimensions();
    int m = e.get(0), n = e.get(1);
    int ans = n;
    for (int i = 0; i < m; ++i) {
      int l = 0, r = n;
      while (l < r) {
        int mid = (l + r) >> 1;
        if (binaryMatrix.get(i, mid) == 1) {
          r = mid;
        } else {
          l = mid + 1;
        }
      }
      ans = Math.min(ans, l);
    }
    return ans >= n ? -1 : ans;
  }
}

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

class Solution {
public:
  int leftMostColumnWithOne(BinaryMatrix& binaryMatrix) {
    auto e = binaryMatrix.dimensions();
    int m = e[0], n = e[1];
    int ans = n;
    for (int i = 0; i < m; ++i) {
      int l = 0, r = n;
      while (l < r) {
        int mid = (l + r) >> 1;
        if (binaryMatrix.get(i, mid)) {
          r = mid;
        } else {
          l = mid + 1;
        }
      }
      ans = min(ans, l);
    }
    return ans >= n ? -1 : ans;
  }
};

/**
 * // This is the BinaryMatrix's API interface.
 * // You should not implement it, or speculate about its implementation
 * type BinaryMatrix struct {
 *   Get func(int, int) int
 *   Dimensions func() []int
 * }
 */

func leftMostColumnWithOne(binaryMatrix BinaryMatrix) int {
  e := binaryMatrix.Dimensions()
  m, n := e[0], e[1]
  ans := n
  for i := 0; i < m; i++ {
    l, r := 0, n
    for l < r {
      mid := (l + r) >> 1
      if binaryMatrix.Get(i, mid) == 1 {
        r = mid
      } else {
        l = mid + 1
      }
    }
    ans = min(ans, l)
  }
  if ans >= n {
    return -1
  }
  return ans
}

/**
 * // This is the BinaryMatrix's API interface.
 * // You should not implement it, or speculate about its implementation
 * class BinaryMatrix {
 *    get(row: number, col: number): number {}
 *
 *    dimensions(): number[] {}
 * }
 */

function leftMostColumnWithOne(binaryMatrix: BinaryMatrix) {
  const [m, n] = binaryMatrix.dimensions();
  let ans = n;
  for (let i = 0; i < m; ++i) {
    let [l, r] = [0, n];
    while (l < r) {
      const mid = (l + r) >> 1;
      if (binaryMatrix.get(i, mid) === 1) {
        r = mid;
      } else {
        l = mid + 1;
      }
    }
    ans = Math.min(ans, l);
  }
  return ans >= n ? -1 : ans;
}

/**
 * // This is the BinaryMatrix's API interface.
 * // You should not implement it, or speculate about its implementation
 *  struct BinaryMatrix;
 *  impl BinaryMatrix {
 *   fn get(row: i32, col: i32) -> i32;
 *   fn dimensions() -> Vec<i32>;
 * };
 */

impl Solution {
  pub fn left_most_column_with_one(binaryMatrix: &BinaryMatrix) -> i32 {
    let e = binaryMatrix.dimensions();
    let m = e[0] as usize;
    let n = e[1] as usize;
    let mut ans = n;

    for i in 0..m {
      let (mut l, mut r) = (0, n);
      while l < r {
        let mid = (l + r) / 2;
        if binaryMatrix.get(i as i32, mid as i32) == 1 {
          r = mid;
        } else {
          l = mid + 1;
        }
      }
      ans = ans.min(l);
    }

    if ans >= n {
      -1
    } else {
      ans as i32
    }
  }
}

/**
 * // This is BinaryMatrix's API interface.
 * // You should not implement it, or speculate about its implementation
 * class BinaryMatrix {
 *   public int Get(int row, int col) {}
 *   public IList<int> Dimensions() {}
 * }
 */

class Solution {
  public int LeftMostColumnWithOne(BinaryMatrix binaryMatrix) {
    var e = binaryMatrix.Dimensions();
    int m = e[0], n = e[1];
    int ans = n;
    for (int i = 0; i < m; ++i) {
      int l = 0, r = n;
      while (l < r) {
        int mid = (l + r) >> 1;
        if (binaryMatrix.Get(i, mid) == 1) {
          r = mid;
        } else {
          l = mid + 1;
        }
      }
      ans = Math.Min(ans, l);
    }
    return ans >= n ? -1 : ans;
  }
}