-
Notifications
You must be signed in to change notification settings - Fork 1
Expand file tree
/
Copy pathP_1428.java
More file actions
38 lines (32 loc) · 1.01 KB
/
Copy pathP_1428.java
File metadata and controls
38 lines (32 loc) · 1.01 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
package leetcode.medium;
import java.util.List;
public class P_1428 {
interface BinaryMatrix {
int get(int x, int y);
List<Integer> dimensions();
}
public int leftMostColumnWithOne(BinaryMatrix binaryMatrix) {
final List<Integer> dimensions = binaryMatrix.dimensions();
int res = Integer.MAX_VALUE;
for (int i = 0; i < dimensions.get(0); i++) {
final int currRow = bs(binaryMatrix, dimensions.get(1), i);
if (currRow != -1) {
res = Math.min(res, currRow);
}
}
return res == Integer.MAX_VALUE ? -1 : res;
}
private static int bs(BinaryMatrix binaryMatrix, int colSize, int currRow) {
int lo = 0;
int hi = colSize;
while (lo < hi) {
final int mid = lo + hi >>> 1;
if (binaryMatrix.get(currRow, mid) == 0) {
lo = mid + 1;
} else {
hi = mid;
}
}
return lo == colSize ? -1 : lo;
}
}