Binary Search
33. Search in Rotated Sorted Array
4 min readApr 14, 2020
class Solution:
def search(self, nums: List[int], target: int) -> int:
if not nums:return -1
l, r = 0, len(nums)-1
while l<=r:
m = (l+r)//2
if target==nums[m]:return m
if nums[l]<=nums[m]:
if nums[l]<=target<nums[m]:
r = m-1
else:
l = m+1
else:
if nums[m] < target <=nums[r]:
l = m+1
else:
r = m -1
return -11044. Longest Duplicate Substring
An unoptimized solution got TLE
class Solution:
def longestDupSubstring(self, S: str) -> str:
if len(set(S))==len(S):return ""
l, r = 0, len(S)-1
def good(m):
cnt = collections.Counter()
for i in range(len(S)):
if i+m<=len(S):
cnt[S[i:i+m]] +=1
else:
break
return max([0]+list(cnt.values()))>=2
while l<r:
m = (l+r+1)//2
if good(m):
l = m
else:
r = m-1
ret = l if good(l) else 0
if ret == 0:return ""
cnt = collections.Counter()
for i in range(len(S)):
if i+ret<=len(S):
cnt[S[i:i+ret]] +=1
else:
break
return max(cnt.items(), key=lambda x:x[1])[0]Improve the code to early stop, I still get TLE.
class Solution:
def longestDupSubstring(self, S: str) -> str:
if len(set(S))==len(S):return ""
l, r = 0, len(S)
def good(m):
seen = set()
for i in range(m, len(S)+1):
curr = S[i-m:i]
if curr in seen:return i
seen.add(curr)
return 0
res = 0
while l<r:
m = (l+r+1)//2
pos = good(m)
if pos:
l = m
res = pos
else:
r = m-1
#print(l)
return S[res-l:res] if l else ""If we use a rolling hash to speed up, we can get it accepted.
# time complexity O(n log n)# space complexity O(n)
class Solution:
def longestDupSubstring(self, S: str) -> str:
A = [ord(c) - ord('a') for c in S]
mod = (1<<53)
def test(L):
p = (26**L)%mod
cur = functools.reduce(lambda x, y: (x * 26 + y) % mod, A[:L])
seen = {cur}
for i in range(L, len(S)):
cur = (cur * 26 + A[i] - A[i - L] * p) % mod
if cur in seen: return i - L + 1
seen.add(cur)
res, lo, hi = 0, 0, len(S)
while lo < hi:
mi = (lo + hi + 1) // 2
pos = test(mi)
if pos:
lo = mi
res = pos
else:
hi = mi - 1
return S[res:res + lo]
A more plain code without using the functools are here
class Solution:
def longestDupSubstring(self, S: str) -> str:
A = [ord(c)-ord('a') for c in S]
mod = 1<<43
def test(m):
p = (26**m)%mod
cur = 0
for val in A[:m]:
cur = (cur*26+val)%mod
seen = {cur}
for i in range(m, len(S)):
cur = (cur*26+A[i]-A[i-m]*p)%mod
if cur in seen:return i
seen.add(cur)
return 0
l, r = 0, len(S)
res = 0
while l<r:
m = (l+r+1)//2
pos = test(m)
if pos:
res = pos
l = m
else:
r = m - 1
return S[res-l+1:res+1]if l else ''Be super careful, if we don’t add ‘%mod’ in this line, we will get TLE
p = (26**m)%mod302. Smallest Rectangle Enclosing Black Pixels
Binary search solution
class Solution {
public:
bool row_has_one(vector<vector<char>>& image, int i)
{
for (int j = 0; j < image[0].size(); ++j)
{
if (image[i][j] == '1') return true;
}
return false;
}
bool col_has_one(vector<vector<char>>& image, int j)
{
for (int i = 0; i < image.size(); ++i)
{
if (image[i][j] == '1') return true;
}
return false;
}
int binary_row(vector<vector<char>>& image, int left, int right, bool smaller)
{
while(left < right)
{
int mid = 0;
if (smaller)
{
mid = left + (right - left) / 2;
}
else
{
mid = left + (right - left + 1) / 2;
}
if (row_has_one(image, mid))
{
if (smaller)
{
right = mid;
}
else
{
left = mid;
}
}
else
{
if (smaller)
{
left = mid + 1;
}
else
{
right = mid - 1;
}
}
}
return left;
}
int binary_col(vector<vector<char>>& image, int left, int right, bool smaller)
{
while(left < right)
{
int mid = 0;
if (smaller)
{
mid = left + (right - left) / 2;
}
else
{
mid = left + (right - left + 1) / 2;
}
if (col_has_one(image, mid))
{
if (smaller)
{
right = mid;
}
else
{
left = mid;
}
}
else
{
if (smaller)
{
left = mid + 1;
}
else
{
right = mid - 1;
}
}
}
return left;
}
int minArea(vector<vector<char>>& image, int x, int y) {
const int R = image.size(), C = image[0].size();
auto min_x = binary_row(image, 0, x, true);
auto max_x = binary_row(image, x, R - 1, false);
auto min_y = binary_col(image, 0, y, true);
auto max_y = binary_col(image, y, C - 1, false);
return (max_x - min_x + 1) * (max_y - min_y + 1);
}
};
