Binary Search Flashcards
Binary Search template
def binarysearch(array) :-> int:
def condition(vlaue) : -> bool:
{…..}
left, right = min(searchspace), max(searchspace)
while left< right:
mid = left + (right- left)//2
if condition(mid):
right = mid
else:
left = mid+1
return left ... or left-1 ========================= 1. figure out condition 2. Figure out boundaries of search space 3. figure out to send left or left -1
Capacity To Ship Packages Within D Days
A conveyor belt has packages that must be shipped from one port to another within days days.
The ith package on the conveyor belt has a weight of weights[i]. Each day, we load the ship with packages on the conveyor belt (in the order given by weights). We may not load more weight than the maximum weight capacity of the ship.
Return the least weight capacity of the ship that will result in all the packages on the conveyor belt being shipped within days days.
Example 1:
Input: weights = [1,2,3,4,5,6,7,8,9,10], days = 5
Output: 15
Explanation: A ship capacity of 15 is the minimum to ship all the packages in 5 days like this:
1st day: 1, 2, 3, 4, 5
2nd day: 6, 7
3rd day: 8
4th day: 9
5th day: 10
Note that the cargo must be shipped in the order given, so using a ship of capacity 14 and splitting the packages into parts like (2, 3, 4, 5), (1, 6, 7), (8), (9), (10) is not allowed.
’’’’
class Solution:
def shipWithinDays(self, weights: List[int], days: int) -> int:
def isFeasible(capacity):
total = 0
days_required = 1
for weight in weights:
total += weight
if total > capacity: # we need push the recently pushed weight in a new container next day
total = weight # start afresh for next day
days_required+=1
if days_required > days:
return False
return True
left,right = max(weights), sum(weights) #max(weights) - minimum capacity required to send all parcels
#sum(weights) - max capacity required to send all parcels at once
while left < right:
mid = left + (right - left)//2
if isFeasible(mid):
right = mid
else:
left = mid + 1
return left '''' We treat this problem as finding a minimum capacity that can satisfy the condition. We search for this using binarysearch So we create a search space of capacities left = minimum of search space = max(weights) - minimum capacity required to send all parcels successfully right = maximum of search space = sum(weights) - maximum capacity required to send all parcels at once Condition : total = keeps track of weights of parcel sent on a day. iterate through weights and add to total. If total > capacity , that means the recently added weight pushed it over capacity. Thus we increment the day and make the total = weight to refresh the counter. We also check the days is more than the threshold, that mean this capacity fails to deliver parcels within the threshold number of days. and we return False
Koko Eating Bananas
Koko loves to eat bananas. There are n piles of bananas, the ith pile has piles[i] bananas. The guards have gone and will come back in h hours.
Koko can decide her bananas-per-hour eating speed of k. Each hour, she chooses some pile of bananas and eats k bananas from that pile. If the pile has less than k bananas, she eats all of them instead and will not eat any more bananas during this hour.
Koko likes to eat slowly but still wants to finish eating all the bananas before the guards return.
Return the minimum integer k such that she can eat all the bananas within h hours.
Example 1:
Input: piles = [3,6,7,11], h = 8
Output: 4
Example 2:
Input: piles = [30,11,23,4,20], h = 5
Output: 30
’’’
import math
class Solution:
def minEatingSpeed(self, piles: List[int], h: int) -> int:
def isFeasible(speed):
sum_hours = 0
for pile in piles:
sum_hours += math.ceil(pile/speed)
if sum_hours > h:
return False
else:
return True
left,right = 1,max(piles) # 1 means koko for sure will eat 1 banana in hour. Thus hours = sum(piles)
#max(piles) she will a pile in 1 hour. thus hours = num of piles
while left<right:
mid = left + (right - left)//2
if isFeasible(mid):
right = mid
else:
left = mid + 1
return left ''' Here we are trying to find the speed (num of bananas that can be eaten in 1 hour) that satisfies the condition. Condition: at any hour the number of banana eaten are piles[i]/speed. ** In this problem koko doesnt go to next pile until unless this pile is finished ** example [3,6,7,11], speed = 4. h=0; 3/4 = ceil(0.75) = 1 hour (h+=1). Even though koko wants to eat 4 bananas he doesnt go after the next pile h=1; 6/4 = ceil(1.5) = 2 hours (h+=2) . Koko will eat this pile in 2 hours.
Find Minimum in Rotated Sorted Array
Suppose an array of length n sorted in ascending order is rotated between 1 and n times. For example, the array nums = [0,1,2,4,5,6,7] might become:
[4,5,6,7,0,1,2] if it was rotated 4 times.
[0,1,2,4,5,6,7] if it was rotated 7 times.
Notice that rotating an array [a[0], a[1], a[2], …, a[n-1]] 1 time results in the array [a[n-1], a[0], a[1], a[2], …, a[n-2]].
Given the sorted rotated array nums of unique elements, return the minimum element of this array.
You must write an algorithm that runs in O(log n) time.
Example 1:
Input: nums = [3,4,5,1,2]
Output: 1
Explanation: The original array was [1,2,3,4,5] rotated 3 times.
Example 2:
Input: nums = [4,5,6,7,0,1,2]
Output: 0
Explanation: The original array was [0,1,2,4,5,6,7] and it was rotated 4 times.
Example 3:
Input: nums = [11,13,15,17]
Output: 11
Explanation: The original array was [11,13,15,17] and it was rotated 4 times.
’’’
class Solution:
def findMin(self, nums: List[int]) -> int:
def isRotationPoint(index):
return nums[index] < nums[0]
if nums[-1] > nums[0]:
return nums[0]
left,right = 0, len(nums)-1
while left<right:
mid = left + (right-left)//2
if isRotationPoint(mid):
right = mid
else:
left = mid+1
return nums[left]
’’’
we have to find the number at which rotation has taken place. More precisely we need to find the index where rotation has occured and send nums[index]
search space - we have to find the index- thus 1 to len(nums)-1
Condition : Rotation happend when nums[index] < nums[0]. In below example 0 = nums[4] which is less than nums[0]. index = 4
, that nums[index] = 0, is the rotation
[4,5,6,7,0,1,2]
↑ | ↑
first | last
|
rotation point
Binary Search - find the minimum index where the condition is satisfied
if nums[index] < nums[0] – defintely rotated. If nums[index] == nums[0] then it is not rotated
** we have to take care of edge case - when the array isnt rotated at all-
if nums[-1] > nums[0]. then we return nums[0] as it is the rotation point number
BASIC BINARY SEARCH
Given an array of integers nums which is sorted in ascending order, and an integer target, write a function to search target in nums. If target exists, then return its index. Otherwise, return -1.
You must write an algorithm with O(log n) runtime complexity.
Example 1:
Input: nums = [-1,0,3,5,9,12], target = 9
Output: 4
Explanation: 9 exists in nums and its index is 4
class Solution:
def search(self, nums: List[int], target: int) -> int:
def isFeasible(index):
return nums[index] >= target
left,right = 0, len(nums)-1
while left < right:
mid = left + (right - left)//2
if isFeasible(mid):
right = mid
else:
left = mid+1
if nums[left] == target:
return left
else:
return -1
Search in Rotated Sorted Array
There is an integer array nums sorted in ascending order (with distinct values).
Prior to being passed to your function, nums is possibly rotated at an unknown pivot index k (1 <= k < nums.length) such that the resulting array is [nums[k], nums[k+1], …, nums[n-1], nums[0], nums[1], …, nums[k-1]] (0-indexed). For example, [0,1,2,4,5,6,7] might be rotated at pivot index 3 and become [4,5,6,7,0,1,2].
Given the array nums after the possible rotation and an integer target, return the index of target if it is in nums, or -1 if it is not in nums.
You must write an algorithm with O(log n) runtime complexity.
Example 1:
Input: nums = [4,5,6,7,0,1,2], target = 0
Output: 4
Example 2:
Input: nums = [4,5,6,7,0,1,2], target = 3
Output: -1
’’’
class Solution:
def search(self, nums: List[int], target: int) -> int:
def isFeasible(index):
if nums[index]>= nums[0] and target >= nums[0]: ## 4,5,6,7 - target and index are in this range
# both on same side - left. So we follow normal binary search
return nums[index] >= target
elif nums[index]>= nums[0] and target < nums[0]: ## index in 4,5,6,7. Target in 0,1,2,3 range
# so we want to move index to the side where target is. So we to move to right.
# right translates left = mid + 1, which is False for condition()
return False
elif nums[index] < nums[0] and target >= nums[0] : ## index in 0,1,2,3. Target in 4,5,6,7
# move index towards target. Mean move left, translates to right = mid, that is True for condition()
return True
else:# both in range 0,1,2,3 - same side - so normal binary search
return nums[index] >= target
left,right = 0, len(nums)-1
while left<right:
mid = left + (right - left)//2
if isFeasible(mid):
right = mid
else:
left = mid+1
if nums[left] == target:
return left
else:
return -1 '''
Time Based Key-Value Store
Design a time-based key-value data structure that can store multiple values for the same key at different time stamps and retrieve the key’s value at a certain timestamp.
Implement the TimeMap class:
TimeMap() Initializes the object of the data structure.
void set(String key, String value, int timestamp) Stores the key key with the value value at the given time timestamp.
String get(String key, int timestamp) Returns a value such that set was called previously, with timestamp_prev <= timestamp. If there are multiple such values, it returns the value associated with the largest timestamp_prev. If there are no values, it returns “”.
Example 1:
Input
[“TimeMap”, “set”, “get”, “get”, “set”, “get”, “get”]
[[], [“foo”, “bar”, 1], [“foo”, 1], [“foo”, 3], [“foo”, “bar2”, 4], [“foo”, 4], [“foo”, 5]]
Output
[null, null, “bar”, “bar”, null, “bar2”, “bar2”]
Explanation
TimeMap timeMap = new TimeMap();
timeMap.set(“foo”, “bar”, 1); // store the key “foo” and value “bar” along with timestamp = 1.
timeMap.get(“foo”, 1); // return “bar”
timeMap.get(“foo”, 3); // return “bar”, since there is no value corresponding to foo at timestamp 3 and timestamp 2, then the only value is at timestamp 1 is “bar”.
timeMap.set(“foo”, “bar2”, 4); // store the key “foo” and value “bar2” along with timestamp = 4.
timeMap.get(“foo”, 4); // return “bar2”
timeMap.get(“foo”, 5); // return “bar2
from collections import defaultdict
class TimeMap:
def \_\_init\_\_(self):
self.store = defaultdict(list)
def set(self, key: str, value: str, timestamp: int) -> None:
self.store[key].append((timestamp,value))
def get(self, key: str, timestamp: int) -> str:
if key not in self.store:
return ""
time_val_list = self.store[key] #it is monotonic, because we are storing tuples in icnreasing timestamps
# [(2,"xyz"),(3,"abc")..] We want the largest time that is smaller than timestamp_target
# search space - indexes of time_val_list
# condition + binary search - find the smallest time that is larger than timestam_target.
def isFeasible(index):
return time_val_list[index][0] > timestamp
left ,right = 0, len(time_val_list)
while left<right:
mid = left + (right - left)//2
if isFeasible(mid):
right = mid
else:
left = mid+1
if left - 1 >=0: # we got the minimum number greater than time_target, so left -1 index will hold the largest number
#smaller than target. WE want to make sure if left -1 is within bounds
return time_val_list[left-1][1]
else:
return ""
Your TimeMap object will be instantiated and called as such:
# obj = TimeMap()
# obj.set(key,value,timestamp)
# param_2 = obj.get(key,timestamp)
Find Peak Element
A peak element is an element that is strictly greater than its neighbors.
Given a 0-indexed integer array nums, find a peak element, and return its index. If the array contains multiple peaks, return the index to any of the peaks.
You may imagine that nums[-1] = nums[n] = -∞. In other words, an element is always considered to be strictly greater than a neighbor that is outside the array.
You must write an algorithm that runs in O(log n) time.
Example 1:
Input: nums = [1,2,3,1]
Output: 2
Explanation: 3 is a peak element and your function should return the index number 2.
Example 2:
Input: nums = [1,2,1,3,5,6,4]
Output: 5
Explanation: Your function can return either index number 1 where the peak element is 2, or index number 5 where the peak element is 6.
’’’
class Solution:
def findPeakElement(self, nums: List[int]) -> int:
if len(nums) == 0 or len(nums) == 1:
return 0
def isFeasible(index):
return nums[index] > nums[index+1]
left,right = 0,len(nums)-1
while left<right:
mid = left+(right-left)//2
if isFeasible(mid):
right = mid
else:
left = mid+1
return left ''''
If nums[mid] > nums[mid+1]:
We know we’re going downhill
A peak must exist either at current element or to the left
If nums[mid] < nums[mid+1]:
We know we’re going uphill
A peak must exist to the right
