Distilled • LeetCode • Binary Search
 Pattern: Binary Search
 [33/Medium] Search in Rotated Sorted Array
 [34/Medium] Find First and Last Position of Element in Sorted Array
 [162/Medium] Find Peak Element
 [278/Easy] First Bad Version
 [410/Hard] Split Array Largest Sum
 [528/Medium] Random Pick with Weight
 [774/Hard] Minimize Max Distance to Gas Station
 [825/Medium] Friends Of Appropriate Ages
 [875/Medium] Koko Eating Bananas
 [1011/Medium] Capacity To Ship Packages Within D Days
 [1060/Medium] Missing Element in Sorted Array
 [1231/Hard] Divide Chocolate
 [1283/Medium] Find the Smallest Divisor Given a Threshold
 [1482/Medium] Minimum Number of Days to Make \(m\) Bouquets
 [1539/Easy] Kth Missing Positive Number
 [1891/Medium] Cutting Ribbons
 Further Reading
Pattern: Binary Search
 This section introduces one specific application of Binary Search, i.e., when you are asked to find the upper or lower bound, or more precisely, when you need to find the maximum of the smallest value or the minimum of the largest value. Binary Search is an algorithm to search for a target from a sorted array. It selects the middle element in the array and compares it against the target; if they are not equal, it eliminates one half of the array and keeps searching the other half in the same manner (Wikipedia).
 The most basic application of it is to find a number or a position from an array. Some practices could be found on Leetcode:
 First Bad Version
 Search in Rotated Sorted Array
 Find First and Last Position of Element in Sorted Array
 Median of Two Sorted Arrays
 Another popular case to apply is when you are asked to find the maximum of the smallest value or the minimum of the largest value. Let’s take Split Array Largest Sum as an example to illustrate how to deal with this kind of problem.
 Search space:
 The search space would be from the maximum of the input
nums
, whenm=len(nums)
, to the sum ofnums
, whenm=1
.
 The search space would be from the maximum of the input
 Search strategy:
 Each time we would pick the middle element mid of the search space as our threshold, and calculate the number of subarrays count while making sure that the sum of each subarray does not exceed
mid
. Ifcount>m
, it means we should increase mid to reduce the number of subarrays; else ifcount<=m
, it means we can decrease mid to increase the number of subarrays, butmid
is still qualified.  The following image shows the steps to apply binary search:
 So the pseudocode is:
while l < r: mid = l + (rl)//2 if count(mid) > m: l = mid + 1 else: r = mid return l
 Each time we would pick the middle element mid of the search space as our threshold, and calculate the number of subarrays count while making sure that the sum of each subarray does not exceed
 Picking
mid
: When picking the
mid
out of odd number of items, we can find the middle one; when the number of items is even, there are two ways to pick: the former one or the latter one.  Pick the former one or the latter one out of an even number of items:
 Both of them works, but it should align with how we deal with
l
andr
. When we select the former one usingl+(rl)/2
, we want to make sure to avoidl = mid
because that might lead to infinite loop. For example when there are two elements[0,1]
andmid=0
, thenl
becomes mid and the iteration goes again and again.  Similarly, when we select the latter one using
r(rl)/2
, we want to avoidr=mid
.
 When picking the

Picking
l
andr
: Depends on the context!
 Lower bound
 For example, when the question asks for the lower bound, if
mid
works, thenr
should be mid notmid1
becausemid
might be the answer! And whenmid
does not work,l
should bemid+1
because we are sure themid
is not the answer and everything that falls onemid
‘s left won’t work either.
 For example, when the question asks for the lower bound, if
 Upper bound
 Similarly, we can assign values to
l
andr
as below.
 Similarly, we can assign values to
 Lower bound
 Overall, the way we select
mid
and assign values tol
andr
is determined by which we are looking for: lower bound vs. upper bound.
 Depends on the context!
 How to choose
mid
,l
, andr
:
[33/Medium] 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 indexk
(1 <= k < nums.length
) such that the resulting array is[nums[k], nums[k+1], ..., nums[n1], nums[0], nums[1], ..., nums[k1]]
(0indexed). For example,[0,1,2,4,5,6,7]
might be rotated at pivot index3
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 innums
, or 1 if it is not innums
. 
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
 Example 3:
Input: nums = [1], target = 0
Output: 1
 Constraints:
1 <= nums.length <= 5000
104 <= nums[i] <= 104
All values of nums are unique.
nums is an ascending array that is possibly rotated.
104 <= target <= 104
 See problem on LeetCode.
Solution: Binary Search
 Background:
 We have an ascending array, which is rotated at some pivot. Let’s call the rotation the inflection point (
IP
).  One characteristic the inflection point holds is:
arr[IP] > arr[IP + 1]
andarr[IP] > arr[IP  1]
.  If we rotated an array
[0, 1, 2, 3, 4, 7, 8, 9]
to[7, 8, 9, 0, 1, 2, 3, 4]
, the inflection point (where the numbers go from monotonically increasing to decreasing or viceversa),IP
number 9 (in terms of the pivot , this would be index5
).  One thing we can see is that values until the
IP
are ascending. And values fromIP + 1
until end are also ascending (hint: binary search).  Also the values from
[0, IP]
are always bigger than[IP + 1, n]
.
 We have an ascending array, which is rotated at some pivot. Let’s call the rotation the inflection point (
 Intuition:
 We can perform a Binary Search.
 If
A[mid]
is bigger thanA[left]
we know the inflection point will be to the right of us, meaning values froma[left] ... a[mid]
are ascending.  So if
target
is between that range we just cut our search space to the left. Otherwise go right.  The other condition is that
A[mid]
is not bigger thanA[left]
meaninga[mid] ... a[right]
is ascending.  In the same manner we can check if
target
is in that range and cut the search space correspondingly.
class Solution:
def search(self, nums: List[int], target: int) > int:
if not nums:
return 1
low, high = 0, len(nums)  1
while low <= high:
mid = (low + high) // 2
if target == nums[mid]:
return mid
# left portion is sorted, i.e., left is strictly increasing.
# inflection point to the right of mid.
if nums[low] <= nums[mid]:
if nums[low] <= target <= nums[mid]:
high = mid  1
else:
low = mid + 1
# left portion is unsorted, i.e., right is strictly increasing.
# inflection point to the left of mid.
else:
if nums[mid] <= target <= nums[high]:
low = mid + 1
else:
high = mid  1
return 1
Complexity
 Time: \(O(\log{n})\) where \(n\) is \(len(nums)\)
 Space: \(O(1)\)
[34/Medium] Find First and Last Position of Element in Sorted Array

Given an array of integers
nums
sorted in nondecreasing order, find the starting and ending position of a given target value. 
If target is not found in the array, return
[1, 1]
. 
You must write an algorithm with
O(log n)
runtime complexity. 
Example 1:
Input: nums = [5,7,7,8,8,10], target = 8
Output: [3,4]
 Example 2:
Input: nums = [5,7,7,8,8,10], target = 6
Output: [1,1]
 Example 3:
Input: nums = [], target = 0
Output: [1,1]
 Constraints:
0 <= nums.length <= 105
109 <= nums[i] <= 109
nums is a nondecreasing array.
109 <= target <= 109
 See problem on LeetCode.
Solution: Binary Search
 Explanation:
search()
:find the lowest index of target num in nums if there is target num in nums lo = lowest index of target hi = lowest index of target if there is no target num in nums if there is higher num than target in nums lo = lowest index of the first higher num than target in nums hi = lowest index of the first higher num than target in nums if there is no higher num than target in nums lo = len(nums) hi = len(nums)
 after
lo = search(target), hi = search(target+1)1
:if there is more than one target num lo = lowest index of target hi = (lowest index of the first higher num than target)1 (highest index of target) then, lo < high elif there is only one target num lo == high else if there is only higher number than target in nums lo = lowest index of the first higher num than target (at least target+1 or higher) hi = lowest index of the (target+1)  1 then, lo > high if there is only lower number than target in nums lo = len(nums) hi = len(nums)1 then, lo > high
def searchRange(self, nums, target):
def binarySearchLeft(A, x):
left, right = 0, len(A)  1
while left <= right:
mid = (left + right) / 2
if x > A[mid]: left = mid + 1
else: right = mid  1
return left
def binarySearchRight(A, x):
left, right = 0, len(A)  1
while left <= right:
mid = (left + right) / 2
if x >= A[mid]: left = mid + 1
else: right = mid  1
return right
left, right = binarySearchLeft(nums, target), binarySearchRight(nums, target)
return (left, right) if left <= right else [1, 1]
 Same approach; compressed version:
class Solution:
def searchRange(self, nums: List[int], target: int) > List[int]:
def search(x):
lo, hi = 0, len(nums)
while lo < hi:
mid = (lo + hi) // 2
if nums[mid] < x:
lo = mid+1
else:
hi = mid
return lo
lo = search(target)
hi = search(target + 1)1
return [lo, hi] if lo <= hi else [1, 1]
Complexity
 Time: \(O(\log{n})\)
 Space: \(O(1)\)
[162/Medium] Find Peak Element
Problem

A peak element is an element that is strictly greater than its neighbors.

Given an 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] = ∞
. 
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.
 Constraints:
1 <= nums.length <= 1000
2^31 <= nums[i] <= 2^31  1
nums[i] != nums[i + 1] for all valid i.
 See problem on LeetCode.
Solution: Binary search
class Solution:
def findPeakElement(self, nums: List[int]) > int:
left = 0
right = len(nums)1
# handle condition 3
while left < right1:
mid = (left+right) // 2
if nums[mid] > nums[mid+1] and nums[mid] > nums[mid1]:
return mid
if nums[mid] < nums[mid+1]:
left = mid+1
else:
right = mid1
# handle condition 1 and 2
return left if nums[left] >= nums[right] else right
Complexity
 Time: \(O(\log{n})\)
 Space: \(O(1)\)
Solution: Oneliner
class Solution:
# @param nums, an integer[]
# @return an integer
def findPeakElement(self, nums):
return nums.index(max(nums))
Complexity
 Time: \(O(n)\)
 Space: \(O(1)\)
[278/Easy] First Bad Version
Problem
 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.  Example 1:
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.
 Example 2:
Input: n = 1, bad = 1
Output: 1
 Constraints:
1 <= bad <= n <= 2^31  1
 See problem on LeetCode.
Solution: Binary search
# The isBadVersion API is already defined for you.
# def isBadVersion(version: int) > bool:
class Solution:
def firstBadVersion(self, n: int) > int:
"""
:type n: int
:rtype: int
"""
r = n1
l = 0
while l <= r:
mid = l + (rl)//2 # or (l + r)//2
if not isBadVersion(mid):
l = mid+1
else:
r = mid1
# returning left here because we need the first bad version
return l
Complexity
 Time: \(O(\log{n})\)
 Space: \(O(1)\)
Solution: Bisect
# The isBadVersion API is already defined for you.
# def isBadVersion(version: int) > bool:
import bisect
class Solution(dict):
def firstBadVersion(self, n: int) > int:
return bisect.bisect_left(self, True, 1, n)
def __getitem__(self, key):
return isBadVersion(key)
Complexity
 Time: \(O(\log{n})\)
 Space: \(O(1)\)
[410/Hard] Split Array Largest Sum
Problem

Given an array
nums
which consists of nonnegative integers and an integerm
, you can split the array intom
nonempty continuous subarrays. 
Write an algorithm to minimize the largest sum among these
m
subarrays. 
Example 1:
Input: nums = [7,2,5,10,8], m = 2
Output: 18
Explanation:
There are four ways to split nums into two subarrays.
The best way is to split it into [7,2,5] and [10,8],
where the largest sum among the two subarrays is only 18.
 Example 2:
Input: nums = [1,2,3,4,5], m = 2
Output: 9
 Example 3:
Input: nums = [1,4,4], m = 3
Output: 4
 Constraints:
1 <= nums.length <= 1000
0 <= nums[i] <= 106
1 <= m <= min(50, nums.length)
 See problem on LeetCode.
Solution: Binary Search
class Solution:
def splitArray(self, nums: List[int], m: int) > int:
"""
:type nums: List[int]
:type m: int
:rtype: int
"""
def split(nums, largest_sum):
"""
Given the largest_sum returns the number of pieces.
"""
pieces = 1
tmp_sum = 0
for num in nums:
if tmp_sum + num > largest_sum:
tmp_sum = num
pieces += 1
else:
tmp_sum += num
return pieces
# pieces is number of pieces for a given largest_sum
# For pieces = len(nums), the largest_sum is max(nums)
# for pieces = 1, the largest_sum is sum(nums)
# We are looking for p=m, as we go from p=1 to p=len(nums) the
# largest sum goes from max(nums) to sum(nums) (which is our search space)
low = max(nums) # m = len(nums)
high = sum(nums) # m = 1
# if pieces > m high is small
while low < high:
mid = (low + high) // 2 # or mid = low + (high  low) // 2
pieces = split(nums, mid)
if pieces > m: # the largest_sum is small, we have too many pieces and we can merge some of them
# we have more pieces than m, which means largest sum needs to increase so set low to mid+1
low = mid + 1
else:
# mid works so cap high to mid
high = mid
return low
Complexity
 Time: \(O(n\log{m})\) where \(m = sum(nums)\) and \(nums\) is the input array containing \(n\) items.
 Space \(O(1)\)
[528/Medium] Random Pick with Weight
Problem

You are given a 0indexed array of positive integers
w
wherew[i]
describes the weight of thei^th
index. 
You need to implement the function
pickIndex()
, which randomly picks an index in the range[0, w.length  1]
(inclusive) and returns it. The probability of picking an indexi
isw[i] / sum(w)
. For example, if w =
[1, 3]
, the probability of picking index0
is1 / (1 + 3) = 0.25
(i.e.,25%
), and the probability of picking index 1 is3 / (1 + 3) = 0.75
(i.e.,75%
).
 For example, if w =

Example 1:
Input
["Solution","pickIndex"]
[[[1]],[]]
Output
[null,0]
Explanation
Solution solution = new Solution([1]);
solution.pickIndex(); // return 0. The only option is to return 0 since there is only one element in w.
 Example 2:
Input
["Solution","pickIndex","pickIndex","pickIndex","pickIndex","pickIndex"]
[[[1,3]],[],[],[],[],[]]
Output
[null,1,1,1,1,0]
Explanation
Solution solution = new Solution([1, 3]);
solution.pickIndex(); // return 1. It is returning the second element (index = 1) that has a probability of 3/4.
solution.pickIndex(); // return 1
solution.pickIndex(); // return 1
solution.pickIndex(); // return 1
solution.pickIndex(); // return 0. It is returning the first element (index = 0) that has a probability of 1/4.
Since this is a randomization problem, multiple answers are allowed.
All of the following outputs can be considered correct:
[null,1,1,1,1,0]
[null,1,1,1,1,1]
[null,1,1,1,0,0]
[null,1,1,1,0,1]
[null,1,0,1,0,0]
......
and so on.
 Constraints:
1 <= w.length <= 104
1 <= w[i] <= 105
pickIndex will be called at most 104 times.
 See problem on LeetCode.
Solution: Normalize weights, sample N uniformly and pick based on testing if N <= Weight
 Normalize the weights in the initial w list to ratios
 i.e.,
[1, 3, 3, 1] > [1 / 8, 3 / 8, 3 / 8, 1 / 8]
, for a general list […i…] —> [… i / sum(list) …]  This give us the frequency of each index
 i.e.,
 Take these new weights and put them on a number line from 0 –> 1 by adding to each element all of the previous elements
 i.e. [1/8, 3/8, 3/8, 1/8] –> [1/8,4/8,7/8,1], for a general list […i…] —> [… i + sum(all previous)…]
 Note this will always mean list[1] = 1
 This gives us a number line to test a random variable on
 Generate a random number between 0, 1
 Find the section of the number line the random number falls into and return its index
 The while loop effectively gives us each index with its correct probability
Pseudocode:
1. Initialize class.
2. Get a list of all unique values.
3. Normalize weights.
4. Put weights on the number line.
5. If a uniform variable falls in the range of a value that value is returned.
import random
class Solution:
def __init__(self, w: List[int]):
self.w = w
# 1. calculate relative frequency
denom = sum(self.w)
for i in range(len(self.w)):
self.w[i] = self.w[i] / denom
# 2. put relative frequencies on the number line between 0 and 1
# Note self.w[1] = 1
for i in range(1, len(self.w)):
self.w[i] += self.w[i1]
def pickIndex(self) > int:
# this is where we pick the index
N = random.uniform(0, 1)
# test each region of the number line to see if N falls in it, if it
# does not then go to the next index and check if N falls in it
# this is guaranteed to break because of previous normalization
for index, weight in enumerate(self.w):
if N <= weight:
return index
# OR
# index = 0
# while index < len(self.w):
# if N <= self.w[index]:
# return index
# index += 1
# OR
# flag = 1
# index = 1
#
# while flag:
# index +=1
# if N <= self.w[index]:
# flag = 0
#
# return index
Solution: Binary search
class Solution:
def __init__(self, w: List[int]):
s = sum(w)
self.weight = [w[0]/s]
for i in range(1, len(w)):
self.weight.append(self.weight[1]+w[i]/s)
def pickIndex(self) > int:
l, r, seed = 0, len(self.weight)1, random.random()
while l < r:
m = (l+r)//2
if self.weight[m] <= seed: l = m+1
else: r = m
return l
Complexity
 Time: \(O(n + n) = O(2n) = O(n)\)
 Space: \(O(1)\)
[774/Hard] Minimize Max Distance to Gas Station
Problem

You are given an integer array
stations
that represents the positions of the gas stations on thexaxis
. You are also given an integerk
. 
You should add
k
new gas stations. You can add the stations anywhere on the xaxis, and not necessarily on an integer position. 
Let
penalty()
be the maximum distance between adjacent gas stations after adding thek
new stations. 
Return the smallest possible value of
penalty()
. Answers within106
of the actual answer will be accepted. 
Example 1:
Input: stations = [1,2,3,4,5,6,7,8,9,10], k = 9
Output: 0.50000
 Example 2:
Input: stations = [23,24,36,39,46,56,57,65,84,98], k = 1
Output: 14.00000
 Constraints:
10 <= stations.length <= 2000
0 <= stations[i] <= 108
stations is sorted in a strictly increasing order.
1 <= k <= 106
 See problem on LeetCode.
Solution: Binary Search
 The hint is that “answers within 10^6 of the true value will be accepted as correct”. Because binary search may not find exact value but it can approach the correct answer.
 To use binary search to find the smallest possible value of penalty distance, initialize
left = 0
andright = the distance between the first and the last station
.count
is the number of gas station we need to make it possible. if count > k
, it meansmid
is too small to realize usingk
stations.if count <= k
, it meansmid
is possible and we can continue to find a bigger one. When
left + 1e6 >= right
, it means that the answer is within10^6
of the true value.
class Solution:
def minmaxGasDist(self, stations: List[int], k: int) > float:
left, right = 1e6, stations[1]  stations[0]
while left + 1e6 < right:
mid = (left + right) / 2
count = 0
for a, b in zip(stations, stations[1:]):
count += math.ceil((b  a) / mid)  1
if count > k:
left = mid
else:
right = mid
return right
Complexity
 Time: \(O(n\log{m})\) where \(m = stations[N  1]  stations[0]\) and \(stations\) is the input array containing \(n\) items.
 Space \(O(1)\)
[825/Medium] Friends Of Appropriate Ages
Problem

There are
n
persons on a social media website. You are given an integer arrayages
whereages[i]
is the age of theith
person. 
A person
x
will not send a friend request to a persony
(x != y
) if any of the following conditions is true:age[y] <= 0.5 * age[x] + 7
age[y] > age[x]
age[y] > 100 && age[x] < 100

Otherwise,
x
will send a friend request toy
. 
Note that if
x
sends a request toy
,y
will not necessarily send a request tox
. Also, a person will not send a friend request to themselves. 
Return the total number of friend requests made.

Example 1:
Input: ages = [16,16]
Output: 2
Explanation: 2 people friend request each other.
 Example 2:
Input: ages = [16,17,18]
Output: 2
Explanation: Friend requests are made 17 > 16, 18 > 17.
 Example 3:
Input: ages = [20,30,100,110,120]
Output: 3
Explanation: Friend requests are made 110 > 100, 120 > 110, 120 > 100.
 Constraints:
n == ages.length
1 <= n <= 2 * 104
1 <= ages[i] <= 120
 See problem on LeetCode.
Complexity
 Time: \(O(\log{n})\)
 Space: \(O(n)\)
Solution: Dictionary with {age: num_members}
, iterate for each age group and check conditions
 Algorithm:
 Step 1: construct a dictionary with age as key and number of members in that age group as values. This can be done using
Counter
in thecollections
module.  Step 2: iterate for every age group (not every person!) say “me”
 Step 3: for every age group check condition take (“age”,”me”) pair and check if the conditions asked are satisfied with
age<= 0.5 * me +7 age>me 3rd condition is always false so we can omit it.
 Step 4:
 Here we have 2 cases.
 Case (a): if your age is different from the other age
 For e.g., 16, 15, 15 then 15>16 and 15>16, i.e., 2*1 which is
age_count * me_count
 For e.g., 16, 15, 15 then 15>16 and 15>16, i.e., 2*1 which is
 Case (b): if your age is same as other age
 For e.g., 16, 16 then 16<>16 i.e., 2.
 This would be same as number of edges in a graph with n vertices where each edge considered 2 times which is
2*nC2
which would beme_count*(me_count1)
 Step 1: construct a dictionary with age as key and number of members in that age group as values. This can be done using
from collections import Counter
class Solution:
def numFriendRequests(self, ages: List[int]) > int:
count = 0
# Step 1
ages_dict = Counter(ages)
# Step 2
for me in ages_dict:
my_age_count = ages_dict[me]
# Step 3
for age in ages_dict:
if not (age <= 0.5 * me + 7 or age > me):
# Step 4: case (a)
if age != me:
count += ages_dict[age]*my_age_count
# Step 4: case (b)
else:
count += int(my_age_count*(my_age_count1))
return count
Complexity
 Time: \(O(n)\)
 Space: \(O(n)\)
Solution: Binary Search with Counter
 Algorithm:
 Sort by age
 index
i
person will not send friend request toages[i]+1, ages[i]+2
….  index
i
person will not send friend request to elements whose age is less than (0.5 * ages[i] + 7
)  Using binary search we can find upper and lower limit, persons which fall in this range, can send friend requests (remove 1,
ith
person itself)
import bisect
from collections import Counter
class Solution:
def numFriendRequests(self, ages: List[int]) > int:
ages.sort()
counts = Counter(ages)
total = 0
for age in counts:
min_age = 0.5 * age + 7 # or age / 2 + 7
left = bisect.bisect_right(ages, min_age)
right = bisect.bisect_right(ages, age)
total += max(0, right  left  1)*counts[age] # you cannot have negative count
return total
Complexity
 Time: \(O(n)\)
 Space: \(O(n)\)
Solution: Binary Search without a Counter
import bisect
from collections import Counter
class Solution:
def numFriendRequests(self, ages: List[int]) > int:
ages.sort()
count = 0
for age in ages:
left = bisect.bisect_right(ages, (0.5 * age) + 7)
right = bisect.bisect_right(ages, age)
count += max(0, right  left  1) # you cannot have negative count
return count
Complexity
 Time: \(O(n)\)
 Space: \(O(1)\)
[875/Medium] Koko Eating Bananas
Problem

Koko loves to eat bananas. There are
n
piles of bananas, theith
pile haspiles[i]
bananas. The guards have gone and will come back inh
hours. 
Koko can decide her bananasperhour eating speed of
k
. Each hour, she chooses some pile of bananas and eatsk
bananas from that pile. If the pile has less thank
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 withinh
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
 Example 3:
Input: piles = [30,11,23,4,20], h = 6
Output: 23
 Constraints:
1 <= piles.length <= 104
piles.length <= h <= 109
1 <= piles[i] <= 109
 See problem on LeetCode.
Solution: Binary search
 Binary search between
[1, max(piles)]
to find the result.  Note that
ceil(p / m)
is equal to(p + m  1) // m
.
class Solution:
def minEatingSpeed(self, piles: List[int], h: int) > int:
# bananasperhour rate can vary between 1 and max(piles)
l, r = 1, max(piles)
while l < r:
m = (l + r) // 2
# the ceil is present because if pile has less than `k` bananas,
# Koko eats all of them instead and will not eat any more bananas during this hour.
if sum(ceil(num_bananas_in_pile / m) for num_bananas_in_pile in piles) > h:
# the number of hours needed are beyond what's permissible, i.e., the bananasperhour rate is less than needed
l = m + 1
else:
r = m
return l
Complexity
 Time: \(O(n\log{m})\) where \(m = max(piles)\) and \(piles\) is the input array containing \(n\) items.
 Space \(O(1)\)
[1011/Medium] Capacity To Ship Packages Within D Days
Problem

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 ofweights[i]
. Each day, we load the ship with packages on the conveyor belt (in the order given byweights
). 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.
 Example 2:
Input: weights = [3,2,2,4,1,4], days = 3
Output: 6
Explanation: A ship capacity of 6 is the minimum to ship all the packages in 3 days like this:
1st day: 3, 2
2nd day: 2, 4
3rd day: 1, 4
 Example 3:
Input: weights = [1,2,3,1,1], days = 4
Output: 3
Explanation:
1st day: 1
2nd day: 2
3rd day: 3
4th day: 1, 1
 Constraints:
1 <= days <= weights.length <= 5 * 104
1 <= weights[i] <= 500
Solution: Binary Search
 Binary search doesn’t sound like a natural fit when this problem is first encountered. We might want to automatically treat weights as search space and then realize we’ve entered a dead end after wasting lots of time. In fact, we are looking for the minimal one among all feasible capacities.
 The underpinning idea behind this problem is that if we can successfully ship all packages within
D
days with capacitym
, then we can definitely ship them all with any capacity larger thanm
. Now we can design a condition function, let’s call itfeasible
, given an input capacity, it returns whether it’s possible to ship all packages withinD
days. This can run in a greedy way: if there’s still room for the current package, we put this package onto the conveyor belt, otherwise we wait for the next day to place this package. If the total days needed exceedsD
, we returnFalse
, otherwise we returnTrue
.  Next, we need to initialize our boundary correctly. Obviously capacity should be at least
max(weights)
, otherwise the conveyor belt couldn’t ship the heaviest package. On the other hand, capacity need not be more thansum(weights)
, because then we can ship all packages in just one day. In other words. the lower bound ismax(A)
for binary search, while the upper bound issum(A)
.
class Solution:
def shipWithinDays(self, weights: List[int], D: int) > int:
def feasible(capacity):
days = 1
local = 0
for w in weights:
local+=w
if local>capacity:
local = w
days+=1
if days>D:
return False
return True
left, right = max(weights), sum(weights)
while left < right:
mid = left + (rightleft)//2
if feasible(mid):
right = mid
else:
left = mid + 1
return left
 Same approach; rehashed:
class Solution:
def shipWithinDays(self, weights: List[int], D: int) > int:
left, right = max(weights), sum(weights)
while left < right:
mid, need, cur = (left + right) / 2, 1, 0
for w in weights:
if cur + w > mid:
need += 1
cur = 0
cur += w
if need > D: left = mid + 1
else: right = mid
return floor(left)
Complexity
 Time: \(O(n\log{m})\) where \(m = sum(weights)\) and \(weights\) is the input array containing \(n\) items
 Space \(O(1)\)
[1060/Medium] Missing Element in Sorted Array
Problem

Given an integer array
nums
which is sorted in ascending order and all of its elements are unique and given also an integerk
, return thekth
missing number starting from the leftmost number of the array. 
Example 1:
Input: nums = [4,7,9,10], k = 1
Output: 5
Explanation: The first missing number is 5.
 Example 2:
Input: nums = [4,7,9,10], k = 3
Output: 8
Explanation: The missing numbers are [5,6,8,...], hence the third missing number is 8.
 Example 3:
Input: nums = [1,2,4], k = 3
Output: 6
Explanation: The missing numbers are [3,5,6,7,...], hence the third missing number is 6.
 Constraints:
1 <= nums.length <= 5 * 104
1 <= nums[i] <= 107
nums is sorted in ascending order, and all the elements are unique.
1 <= k <= 108

Follow up: Can you find a logarithmic time complexity (i.e.,
O(log(n))
) solution?  See problem on LeetCode.
Solution: Linear scan
class Solution:
def missingElement(self, nums: List[int], k: int):
for i in range(1, len(nums)):
# number of missing elements between one index and the prior
diff = nums[i]  nums[i1]  1
if diff >= k:
return nums[i1] + k
else:
k = diff
return nums[1] + k
 Similar approach:
class Solution:
def missingElement(self, nums: List[int], k: int) > int:
#Approach:
# Step 1: find maximum possible kth number provided we had only one digit in array.
# if will be (nums[0] + k)
# Step2: nums[0] + k would have been the answer if there were no other digits, but if we have than we need to find number of digits which are less than nums[0] + k.
# what is the kth missing number for single digit x, it is x + k
ans = nums[0] + k
# if length is one then x + k will be the answer
if len(nums) == 1:
return ans
# if length is greater than one, we try to find how many numbers are less than
# the maximum possible kth missing number (x+k)
# whenever we encounter that there exist a number that is less than (x+k) we increase the (x+k) by 1
# as soon as our ans (x+k) is greater than any number in the list, we return ans.
for currentNum in nums[1:]:
if currentNum > ans:
return ans
if currentNum <= ans:
ans += 1
return ans
Complexity
 Time: \(O(n)\)
 Space \(O(1)\)
Solution: Binary Search
 The idea is to find the first index that has more missing elements than
k
using binary search.  For an input of
nums = [4,7,9,10]
, let’s consider the number of missing elements at the second index. They are[5,6]
, i.e., 2 missing elements. This can be written as:num[1]  num[0]  1
. For indexi
, this can be generalized tonums[i]  nums[0]  i
.  Finally, to get the first missing element, you can do
num[0] + k + 0
. Generalizing this, you getnum[i] + k + i
.
class Solution:
def missingElement(self, nums: List[int], k: int) > int:
def calculateMissings(i):
return nums[i]  nums[0]  i
left, right = 0, len(nums)
# find the first index that has more missing elements than `k` using binary search
# i.e., the lower bound
while left < right:
middle = (left + right) // 2
# select the middle element in the array and compare it against the target
if calculateMissings(middle) < k:
left = middle + 1
else:
right = middle
return nums[0] + k + left  1
 To understand the choice of
left
andright
, check out Shawnlyu: Binary Search – Find Upper and Lower Bound or Medium: Binary Search — Find Upper and Lower Bound
Complexity
 Time: \(O(n\log{n})\)
 Space \(O(1)\)
[1231/Hard] Divide Chocolate
Problem

You have one chocolate bar that consists of some chunks. Each chunk has its own sweetness given by the array sweetness.

You want to share the chocolate with your
k
friends so you start cutting the chocolate bar intok + 1
pieces usingk
cuts, each piece consists of some consecutive chunks. 
Being generous, you will eat the piece with the minimum total sweetness and give the other pieces to your friends.

Find the maximum total sweetness of the piece you can get by cutting the chocolate bar optimally.

Example 1:
Input: sweetness = [1,2,3,4,5,6,7,8,9], k = 5
Output: 6
Explanation: You can divide the chocolate to [1,2,3], [4,5], [6], [7], [8], [9]
 Example 2:
Input: sweetness = [5,6,7,8,9,1,2,3,4], k = 8
Output: 1
Explanation: There is only one way to cut the bar into 9 pieces.
 Example 3:
Input: sweetness = [1,2,2,1,2,2,1,2,2], k = 2
Output: 5
Explanation: You can divide the chocolate to [1,2,2], [1,2,2], [1,2,2]
 Constraints:
0 <= k < sweetness.length <= 104
1 <= sweetness[i] <= 105
 See problem on LeetCode.
Solution: Binary Search
class Solution:
def maximizeSweetness(self, sweetness: List[int], k: int) > int:
left, right = 1, sum(sweetness) // (k + 1)
while left < right:
mid = (left + right + 1) // 2
cur = cuts = 0
for chunk in sweetness:
cur += chunk
if cur >= mid:
cuts += 1
cur = 0
if cuts > k:
left = mid
else:
right = mid  1
return right
 Note that in this question, we want to find the maximum total sweetness. We have to find the rightmost value, so we use
int mid = (left + right + 1)/2
andif (condition passed) left = mid; else right = mid  1
. For a question like Capacity to Ship Packages Within D Days, we want to find the leftmost value. So we have to use something likeint mid = (left + right) / 2
andif (condition passed) right = mid; else left = mid + 1
.
Complexity
 Time: \(O(n\log{m})\) where \(m = sum(sweetness)\) and \(sweetness\) is the input array containing \(n\) items
 Space \(O(1)\)
[1283/Medium] Find the Smallest Divisor Given a Threshold
Problem

Given an array of integers
nums
and an integerthreshold
, we will choose a positive integerdivisor
, divide all the array by it, and sum the division’s result. Find the smallestdivisor
such that the result mentioned above is less than or equal tothreshold
. 
Each result of the division is rounded to the nearest integer greater than or equal to that element. (For example:
7/3 = 3
and10/2 = 5
). 
The test cases are generated so that there will be an answer.

Example 1:
Input: nums = [1,2,5,9], threshold = 6
Output: 5
Explanation: We can get a sum to 17 (1+2+5+9) if the divisor is 1.
If the divisor is 4 we can get a sum of 7 (1+1+2+3) and if the divisor is 5 the sum will be 5 (1+1+1+2).
 Example 2:
Input: nums = [44,22,33,11,1], threshold = 5
Output: 44
 Constraints:
1 <= nums.length <= 5 * 104
1 <= nums[i] <= 106
nums.length <= threshold <= 106
 See problem on LeetCode.
Solution: Binary Search
 If
sum > threshold
, the divisor is too small.  If
sum <= threshold
, the divisor is big enough.
class Solution:
def smallestDivisor(self, nums: List[int], threshold: int) > int:
l, r = 1, max(nums)
while l < r:
m = (l + r) // 2
if sum(math.ceil(num / m) for num in nums) > threshold:
# or if sum((num + m  1) // m for num in nums) > threshold:
l = m + 1
else:
r = m
return l

Note that
(p + m  1) / m
is equal toceil(p / m)
. 
Same approach; rehashed:
 If a number is large enough, it will definitely have a result less than threshold; we need to find the smallest number that can do this.
 How to check whether a given number can make the result less than or equal to
threshold
? Just do a one pass on
nums
and see if the sum of theceil
of each division is less than or equal tothreshold
.
 Just do a one pass on
 If given
mid
is a ok number, then we want to see if a smaller number can do the same thing, so if
ok(mid)
isTrue
:r = mid1
 else:
l = mid+1
 if
class Solution:
def smallestDivisor(self, nums: List[int], threshold: int) > int:
def ok(mid):
ans = 0
for num in nums:
ans += math.ceil(num / mid)
if ans > threshold: return False
return True
l, r = 1, int(1e6)
while l <= r:
mid = (l+r) // 2
if ok(mid): r = mid  1
else: l = mid + 1
return l
Complexity
 Time: \(O(n\log{m})\) where \(m = max(A)\) and \(A\) is the input array containing \(n\) items
 Space \(O(1)\)
[1482/Medium] Minimum Number of Days to Make \(m\) Bouquets
Problem

You are given an integer array
bloomDay
, an integerm
and an integerk
. 
You want to make
m
bouquets. To make a bouquet, you need to usek
adjacent flowers from the garden. 
The garden consists of
n
flowers, theith
flower will bloom in thebloomDay[i]
and then can be used in exactly one bouquet. 
Return the minimum number of days you need to wait to be able to make m bouquets from the garden. If it is impossible to make m bouquets return
1
. 
Example 1:
Input: bloomDay = [1,10,3,10,2], m = 3, k = 1
Output: 3
Explanation: Let us see what happened in the first three days. x means flower bloomed and _ means flower did not bloom in the garden.
We need 3 bouquets each should contain 1 flower.
After day 1: [x, _, _, _, _] // we can only make one bouquet.
After day 2: [x, _, _, _, x] // we can only make two bouquets.
After day 3: [x, _, x, _, x] // we can make 3 bouquets. The answer is 3.
 Example 2:
Input: bloomDay = [1,10,3,10,2], m = 3, k = 2
Output: 1
Explanation: We need 3 bouquets each has 2 flowers, that means we need 6 flowers. We only have 5 flowers so it is impossible to get the needed bouquets and we return 1.
 Example 3:
Input: bloomDay = [7,7,7,7,12,7,7], m = 2, k = 3
Output: 12
Explanation: We need 2 bouquets each should have 3 flowers.
Here is the garden after the 7 and 12 days:
After day 7: [x, x, x, x, _, x, x]
We can make one bouquet of the first three flowers that bloomed. We cannot make another bouquet from the last three flowers that bloomed because they are not adjacent.
After day 12: [x, x, x, x, x, x, x]
It is obvious that we can make two bouquets in different ways.
 Constraints:
bloomDay.length == n
1 <= n <= 105
1 <= bloomDay[i] <= 109
1 <= m <= 106
1 <= k <= n
 See problem on LeetCode.
Solution: Binary Search
 If
m * k > n
, it’s impossible, so return1
.  Otherwise, we deem it a possible task, so we can binary search the result.
left = 1
is the smallest number of days,right = max(bloomDay)
is big enough to makem
bouquets.
 Next, we are going to binary search in range
[left, right]
.  Given
mid
days, we can know which flowers blooms.  Now the problem is, given an array of
True
andFalse
, find out how many adjacentTrue
bouquets are there in total.  If
bouq < m
,mid
is still small form
bouquet. So we setleft = mid + 1
.  If
bouq >= m
,mid
is big enough form
bouquet. So we setright = mid
class Solution:
def minDays(self, bloomDay: List[int], m: int, k: int) > int:
if m * k > len(bloomDay): return 1
left, right = 1, max(bloomDay)
while left < right:
mid = (left + right) // 2
flow = bouq = 0
for a in bloomDay:
flow = 0 if a > mid else flow + 1
if flow >= k:
flow = 0
bouq += 1
if bouq == m: break
if bouq == m:
right = mid
else:
left = mid + 1
return left
Complexity
 Time: \(O(n\log{m})\) where \(m = max(bloomDay)\) and \(bloomDay\) is the input array containing \(n\) items
 Space \(O(1)\)
[1539/Easy] Kth Missing Positive Number
Problem

Given an array
arr
of positive integers sorted in a strictly increasing order, and an integerk
. 
Find the
kth
positive integer that is missing from this array. 
Example 1:
Input: arr = [2,3,4,7,11], k = 5
Output: 9
Explanation: The missing positive integers are [1,5,6,8,9,10,12,13,...]. The 5th missing positive integer is 9.
 Example 2:
Input: arr = [1,2,3,4], k = 2
Output: 6
Explanation: The missing positive integers are [5,6,7,...]. The 2nd missing positive integer is 6.
 Constraints:
1 <= arr.length <= 1000
1 <= arr[i] <= 1000
1 <= k <= 1000
arr[i] < arr[j] for 1 <= i < j <= arr.length
 See problem on LeetCode.
Solution: Maintain a count for number of missed values
 We could go one by one from 1 and check if the number contained in the list (converting
a
to set for faster checking) and maintain a counter for the number of missed values.
class Solution:
def findKthPositive(self, a: List[int], k: int) > int:
s = set(a)
cnt = 0
for i in range(1, max(s)):
if i not in s:
cnt += 1
if cnt == k:
return i
return max(s) + k  cnt
Complexity
 Time: \(O(L+\max(a))\) time, where L is the length of the array assuming Python set takes \(O(1)\) time insert or look up an element (the average case for a hash table). \(L\) for building the set and max(a) for the number of set queries.
 Space \(O(1)\)
Solution: Maintain a count
 Since the array is sorted, we could do better by going one pass over the array instead.
class Solution:
def findKthPositive(self, a: List[int], k: int) > int:
cnt = 0
j = 0
for i in range(1, max(a)):
if i < a[j]:
cnt += 1
if cnt == k:
return i
else:
j += 1
if j >= len(a):
break
return a[1] + k  cnt
Complexity
 Time: \(O(max(a))\)
 Space \(O(1)\)
Solution: Maintain a count between adjacent integers
 We do not need to increase the numbers one by one. All numbers between two adjacent integers in
a
can be updated to the counter at once.
class Solution:
def findKthPositive(self, a: List[int], k: int) > int:
cnt, prev = 0, 0
for x in a:
old_cnt = cnt
cnt += x  prev  1
if cnt >= k:
return prev + k  old_cnt
prev = x
return a[1] + k  cnt
Complexity
 Time: \(O(n)\) where \(n = len(arr)\)
 Space \(O(1)\)
Solution: Maintain a count between adjacent integers

But wait… Do we really need a counter? If there is no missing number, the
a[i]
should just bei+1
. If there is a single missing number beforea[i]
,a[i]
should be justi+2
. So on so forth. In general, if there are m missing numbers up toa[i]
,a[i] = i + m + 1
. So, when we seea[i]
, we know there area[i]i1
missing numbers up to it. Ifa[i]i1 >= k
ora[i] > i+k
, thekth
missing value must be betweena[i1]
anda[i]
. 
On the other hand, if there have already been
i
numbers ina
, thekth
missing value must be at leastk+i
. We show thatk+i
is actually the value we are looking for. First,a[i] > i+k
, soi+k
cannot bea[i]
. Neither can it be anya[j], j > i
, becausea
is increasing anda[j] > a[i] > i+k
. Cani+k
appear beforea[i]
? If that is the case, sayi+k = a[j]
for somej < i
, then we will have a[j] =i+k > j+k
. That means we would have found an earlier locationj
that triggers thea[j] > j+k
criterion, and we would have stopped over there. 
The above analysis gives us this clean 4 lines of code:
class Solution:
def findKthPositive(self, a: List[int], k: int) > int:
for i, x in enumerate(a):
if x > i + k:
return i + k
return len(a) + k
Complexity
 Time: \(O(n)\) where \(n = len(arr)\)
 Space \(O(1)\)
Solution: Binary Search
 Assume the final result is
x
, and there arem
numbers present in the range of[1, x]
. Binary search them
in range[0, len(A)]
.  If there are
m
numbers present, that isA[0], A[1] .. A[m1]
, the number of missing underA[m]
islen(A[m])  1  m
.  If
A[m]  1  m < k
,m
is too small, we updateleft = m
.  If
A[m]  1  m >= k
,m
is big enough, we updateright = m
.  Note that when we exit the while loop,
l = r
, which equals to the number of missing numbers.  So the
Kth
positive number will bel + k
.
class Solution:
def findKthPositive(self, arr: List[int], k: int) > int:
l, r = 0, len(arr)
while l < r:
m = (l + r) // 2
if arr[m]  1  m < k:
l = m + 1
else:
r = m
return l + k
Complexity
 Time: \(O(\log{n})\) where \(n = len(arr)\)
 Space \(O(1)\)
[1891/Medium] Cutting Ribbons
Problem

You are given an integer array
ribbons
, whereribbons[i]
represents the length of theith
ribbon, and an integerk
. You may cut any of the ribbons into any number of segments of positive integer lengths, or perform no cuts at all. For example, if you have a ribbon of length 4, you can:
 Keep the ribbon of length 4,
 Cut it into one ribbon of length 3 and one ribbon of length 1,
 Cut it into two ribbons of length 2,
 Cut it into one ribbon of length 2 and two ribbons of length 1, or
 Cut it into four ribbons of length 1.
 For example, if you have a ribbon of length 4, you can:

Your goal is to obtain
k
ribbons of all the same positive integer length. You are allowed to throw away any excess ribbon as a result of cutting. 
Return the maximum possible positive integer length that you can obtain k ribbons of, or 0 if you cannot obtain k ribbons of the same length.

Example 1:
Input: ribbons = [9,7,5], k = 3
Output: 5
Explanation:
 Cut the first ribbon to two ribbons, one of length 5 and one of length 4.
 Cut the second ribbon to two ribbons, one of length 5 and one of length 2.
 Keep the third ribbon as it is.
Now you have 3 ribbons of length 5.
 Example 2:
Input: ribbons = [7,5,9], k = 4
Output: 4
Explanation:
 Cut the first ribbon to two ribbons, one of length 4 and one of length 3.
 Cut the second ribbon to two ribbons, one of length 4 and one of length 1.
 Cut the third ribbon to three ribbons, two of length 4 and one of length 1.
Now you have 4 ribbons of length 4.
 Example 3:
Input: ribbons = [5,7,9], k = 22
Output: 0
Explanation: You cannot obtain k ribbons of the same positive integer length.
 Constraints:
1 <= ribbons.length <= 105
1 <= ribbons[i] <= 105
1 <= k <= 109
Solution: Binary search
 The crux of the problem is implementing Binary Search.
 The goal is to figure out what the maximum length of a ribbon could be so that we get
k
ribbons of that max length.  One way to think of it would be that the ribbon length could be anywhere from 1 to the max length of the a ribbon available in the list.
 So what we do is go through the list (using Binary Search since we need to optimize linear search), find the
mid
of the given array and then iterate through the list testing the length with each element and summing the number of ribbons that can be made with the mid value. Then changemid
accordingly.
class Solution:
def maxLength(self, ribbons: List[int], k: int) > int:
# impossible case: when total length sum of all ribbons are less than `k`
s = sum(ribbons)
if s < k: return 0
# The minimum length of the ribbon that we can cut is 1
start = 1
# The maximum length of the ribbon can be the maximum element in the list
end = max(ribbons)
# In this binary search, we are trying to go through the origin list and figure out which integer(from 1 > ribbon of max length) is the deired length for the the target k pieces
while(start <= end):
mid = start + (end  start) // 2
res = 0
for i in ribbons:
res += i // mid
# If the value is >= target, we know that there could be a larger integer that will satisfy the same conditon
if res >= k:
start = mid+1
else:
# If lesser than k, then there could be a value lesser than the mid that could satisfy the condition
end = mid 1
return end
Complexity
 Time: \(O(n\log{m})\) where \(m = max(ribbons)\) and \(ribbons\) is the input array containing \(n\) items
 Space \(O(1)\)