-
Notifications
You must be signed in to change notification settings - Fork 0
/
Leftmost Column with at Least a One
114 lines (91 loc) · 3.59 KB
/
Leftmost Column with at Least a One
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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
/*
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.
Example:
0 0 0 0 0 0
0 0 0 1 1 1
0 0 0 0 0 1
0 0 1 1 1 1
0 1 1 1 1 1
0 0 0 0 1 1
Answer: 1 (0-indexed)
Idea:
O(log(M) * N)
Binary search Ones in lines or sublines(from 0, to previously Found Most Left One).
O(N + M)
Imagine there is a pointer p(x, y) starting from top right corner. p can only move left or down.
If the value at p is 0, move down. If the value at p is 1, move left.
*/
/**
* // This is the BinaryMatrix's API interface.
* // You should not implement it, or speculate about its implementation
* interface BinaryMatrix {
* public int get(int x, int y) {}
* public List<Integer> dimensions {}
* };
*/
class Solution {
public int leftMostColumnWithOne(BinaryMatrix binaryMatrix) {
final int N = binaryMatrix.dimensions().get(0);
final int M = binaryMatrix.dimensions().get(1);
int mostLeftOne = M + 1;
for (int i = 0; i < N; i++) {
if (binaryMatrix.get(i, M - 1) != 0) {
int currentMostLeftOne = mostLeftOne == M + 1 ? M - 1 : mostLeftOne;
int current = binarySearchMostLeftOne(binaryMatrix, i, 0, currentMostLeftOne);
if (current != -1 && current < mostLeftOne) {
mostLeftOne = current;
}
}
}
return mostLeftOne == M + 1 ? -1 : mostLeftOne;
}
private int binarySearchMostLeftOne(BinaryMatrix binaryMatrix, int row, int leftIdx, int rightIdx) {
if (binaryMatrix.get(row, rightIdx) == 0) {
return -1;
}
int initialRight = rightIdx;
int mostLeftOne = initialRight + 1;
while (leftIdx <= rightIdx) {
int middleIdx = leftIdx + (rightIdx - leftIdx) / 2;
if (binaryMatrix.get(row, middleIdx) == 1) {
if (middleIdx < mostLeftOne) {
mostLeftOne = middleIdx;
}
if (middleIdx > 0 && binaryMatrix.get(row, middleIdx - 1) == 1) {
rightIdx = middleIdx - 1;
} else {
return mostLeftOne;
}
} else {
leftIdx = middleIdx + 1;
}
}
return mostLeftOne == initialRight + 1 ? -1 : mostLeftOne;
}
// Starting from top right corner: move down if 0, move left if 1
public int leftMostColumnWithOne(BinaryMatrix binaryMatrix) {
final int N = binaryMatrix.dimensions().get(0);
final int M = binaryMatrix.dimensions().get(1);
boolean foundOne = false;
int i = 0;
int j = M - 1;
while(i < N && j >= 0){
if(binaryMatrix.get(i, j) == 0) {
i++;
} else {
// binaryMatrix.get(i, j) == 1
j--;
foundOne = true;
}
}
return foundOne == false ? -1 : j + 1;
}
}