Binary, Binary Search
Problem: https://leetcode.com/problems/leftmost-column-with-at-least-a-one/
Given the constraints in the number of calls to the BinaryMatrix methods, the solution seems to suggest some sort of Binary Search (especially given that the rows are sorted). Rows are sorted and they are binary rows (0 or 1). You can use Binary Search on each row to find the first 1 (standard binary search but looking for a binary value of 1). Then run thru all the rows doing so. Time complexity becomes O(Rows * Log2(Cols)). Given that Max(Rows, Cols) = 100, we then have the total execution time as log2(100)*100, or:
Which is < 1000. Code is below, cheers, ACC.
class Solution
{
public int LeftMostColumnWithOne(BinaryMatrix binaryMatrix)
{
int leftMost = 1000;
IList<int> dimensions = binaryMatrix.Dimensions();
for (int r = 0; r < dimensions[0]; r++)
{
int left = 0;
int right = dimensions[1] - 1;
while (left < right)
{
int mid = (left + right) / 2;
int val = binaryMatrix.Get(r, mid);
if (val == 0) left = mid + 1;
else right = mid;
}
if (binaryMatrix.Get(r, left) == 1)
{
leftMost = Math.Min(leftMost, left);
}
}
return (leftMost == 1000) ? -1 : leftMost;
}
}
1428. Leftmost Column with at Least a One
Medium
(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(row, col)returns the element of the matrix at index(row, col)(0-indexed).BinaryMatrix.dimensions()returns a list of 2 elements[rows, cols], which means the matrix isrows * 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 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:
rows == mat.lengthcols == mat[i].length1 <= rows, cols <= 100mat[i][j]is either0or1.mat[i]is sorted in a non-decreasing way.
Accepted
487
Submissions
90,779
Given the constraints in the number of calls to the BinaryMatrix methods, the solution seems to suggest some sort of Binary Search (especially given that the rows are sorted). Rows are sorted and they are binary rows (0 or 1). You can use Binary Search on each row to find the first 1 (standard binary search but looking for a binary value of 1). Then run thru all the rows doing so. Time complexity becomes O(Rows * Log2(Cols)). Given that Max(Rows, Cols) = 100, we then have the total execution time as log2(100)*100, or:
Which is < 1000. Code is below, cheers, ACC.
class Solution
{
public int LeftMostColumnWithOne(BinaryMatrix binaryMatrix)
{
int leftMost = 1000;
IList<int> dimensions = binaryMatrix.Dimensions();
for (int r = 0; r < dimensions[0]; r++)
{
int left = 0;
int right = dimensions[1] - 1;
while (left < right)
{
int mid = (left + right) / 2;
int val = binaryMatrix.Get(r, mid);
if (val == 0) left = mid + 1;
else right = mid;
}
if (binaryMatrix.Get(r, left) == 1)
{
leftMost = Math.Min(leftMost, left);
}
}
return (leftMost == 1000) ? -1 : leftMost;
}
}
Comments
Post a Comment
[γγ¬γΌγ ]