Buckets:
tags:
- notes
- binary-search
Search in 2D Matrix MEDIUM
You are given an m x n 2-D integer array matrix and an integer target.
- Each row in
matrixis sorted in non-decreasing order. - The first integer of every row is greater than the last integer of the previous row.
Return
trueiftargetexists withinmatrixorfalseotherwise. Can you write a solution that runs inO(log(m * n))time? ![[search-in-2d-matrix.png.png]]
Input: matrix = [[1,2,4,8],[10,11,12,13],[14,20,30,40]], target = 10
Output: true
![[search-in-2d-matrix-2.png.png]]
Input: matrix = [[1,2,4,8],[10,11,12,13],[14,20,30,40]], target = 15
Output: false
[!info] Time and Space complexity You should aim for a solution with
O(log(m * n))time andO(1)space, wheremis the number of rows andnis the number of columns in the matrix.
Solution
This problem can be solved by two methods:
- Finding the element in row and then in the column: Loop over the rows to find the possible location of the target, using binary search technique. Once found, loop over the columns for that row using binary search technique. If found return
Trueelse returnFalse.
class Solution:
def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
ROWS, COLS = len(matrix), len(matrix[0])
if target < matrix[0][0] or target > matrix[ROWS - 1][COLS - 1]:
return False
row = 0
top, bottom = row, ROWS - 1
while top <= bottom:
row = (top + bottom) // 2
if target < matrix[row][0]:
bottom = row - 1
elif target > matrix[row][-1]:
top = row + 1
else:
break
col = 0
left, right = col, COLS - 1
while left <= right:
mid = (right + left) // 2
if target == matrix[row][mid]:
return True
elif target < matrix[row][mid]:
right = mid - 1
elif target > matrix[row][mid]:
left = mid + 1
return False
- Considering the entire matrix as a flat list: The matrix can be visualised as a flattened 1D sorted array because each row is sorted and every row starts after the previous ends. Using this property, binary search is applied across the entire matrix by converting the 1D mid index into 2D coordinates using
row = mid // COLSandcol = mid % COLS. This allows efficient comparison with the target in O(log (m × n)) time. No extra space is used, and the search continues by adjusting the binary range based on comparisons until the target is found or the range is exhausted.
class Solution:
def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
ROWS, COLS = len(matrix), len(matrix[0])
total = ROWS * COLS
start, end = 0, total - 1
while start <= end:
mid = (start + end) // 2
i = mid // COLS
j = mid % COLS
if target == matrix[i][j]:
return True
elif target < matrix[i][j]:
end = mid - 1
else:
start = mid + 1
return False
Koko Eating Bananas MEDIUM
You are given an integer array piles where piles[i] is the number of bananas in the ith pile. You are also given an integer h, which represents the number of hours you have to eat all the bananas.
You may decide your bananas-per-hour eating rate of k. Each hour, you may choose a pile of bananas and eats k bananas from that pile. If the pile has less than k bananas, you may finish eating the pile but you can not eat from another pile in the same hour.
Return the minimum integer k such that you can eat all the bananas within h hours.
Example 1:
Input: piles = [1,4,3,2], h = 9
Output: 2
Explanation: With an eating rate of 2, you can eat the bananas in 6 hours. With an eating rate of 1, you would need 10 hours to eat all the bananas (which exceeds h=9), thus the minimum eating rate is 2. Example 2:
Input: piles = [25,10,23,4], h = 4
Output: 25
[!info] Time and Space Complexity You should aim for a solution with
O(nlogm)time andO(1)space, wherenis the size of the input array, andmis the maximum value in the array.
Solution
We start with max pile size to be the starting threshold. We calculate the mid threshold between 1 and max pile size and calculate the time taken to complete all piles. We compare the time taken with max provided time h and check if its valid. We continue till we have the ideal threshold.
class Solution:
def minEatingSpeed(self, piles: List[int], h: int) -> int:
start, end = 1, max(piles)
threshold = max(piles)
total = sum(piles)
while start <= end:
mid = (start + end) // 2
time = 0
for pile in piles:
time += math.ceil(float(pile) / mid)
if time <= h:
threshold = mid
end = mid - 1
else:
start = mid + 1
return threshold
Find Minimum in Rotated Sorted Array MEDIUM
You are given an array of length n which was originally sorted in ascending order. It has now been rotated between 1 and n times. For example, the array nums = [1,2,3,4,5,6] might become:
[3,4,5,6,1,2]if it was rotated4times.[1,2,3,4,5,6]if it was rotated6times. Notice that rotating the array4times moves the last four elements of the array to the beginning. Rotating the array6times produces the original array. Assuming all elements in the rotated sorted arraynumsare unique, return the minimum element of this array. A solution that runs inO(n)time is trivial, can you write an algorithm that runs inO(log n) time? Example 1:
Input: nums = [3,4,5,6,1,2]
Output: 1
Example 2:
Input: nums = [4,5,0,1,2,3]
Output: 0
Example 3:
Input: nums = [4,5,6,7]
Output: 4
[!info] Time and Space Complexity You should aim for a solution with
O(logn)time andO(1)space, wherenis the size of the input array.
Solution
class Solution:
def findMin(self, nums: List[int]) -> int:
start, end = 0, len(nums) - 1
res = float("inf")
while start <= end:
if nums[start] < nums[end]:
res = min(res, nums[start])
break
mid = (start + end) // 2
res = min(res, nums[mid])
if nums[mid] < nums[end]:
end = mid - 1
else:
start = mid + 1
return res
First Bad Version EASY
You are a product manager and currently leading a team to develop a new product. Unfortunately, the latest version of your product fails the quality check. Since each version is developed based on the previous version, all the versions after a bad version are also bad.
Suppose you have n versions [1, 2, ..., n] and you want to find out the first bad one, which causes all the following ones to be bad.
You are given an API bool isBadVersion(version) which returns whether version is bad. Implement a function to find the first bad version. You should minimize the number of calls to the API.
Input: n = 5, bad = 4
Output: 4
Explanation:
call isBadVersion(3) -> false
call isBadVersion(5) -> true
call isBadVersion(4) -> true
Then 4 is the first bad version.
Solution
We start from the mid of the version list. If we find a version that is bad, we flag it and shrink the search space.
# The isBadVersion API is already defined for you.
# def isBadVersion(version: int) -> bool:
class Solution:
def firstBadVersion(self, n: int) -> int:
start, end = 1, n
bad = float("inf")
while start <= end:
mid = (start + end) // 2
if isBadVersion(mid):
bad = mid
end = mid - 1
else:
start = mid + 1
return bad
Xet Storage Details
- Size:
- 8.48 kB
- Xet hash:
- 5b7bd122ff83ee267efb72fd954746502df71c328937f5b992564ed6f9105446
Xet efficiently stores files, intelligently splitting them into unique chunks and accelerating uploads and downloads. More info.