Binary Search Min Answer

Table of Contents

• 1283. Find the Smallest Divisor Given a Threshold (Medium)
• 2187. Minimum Time to Complete Trips (Medium)
• 1870. Minimum Speed to Arrive on Time (Medium)
• 1011. Capacity To Ship Packages Within D Days (Medium)
• 875. Koko Eating Bananas (Medium)
• 3296. Minimum Number of Seconds to Make Mountain Height Zero (Medium)
• 475. Heaters (Medium)
• 2594. Minimum Time to Repair Cars (Medium)
• 1482. Minimum Number of Days to Make m Bouquets (Medium)
• 3048. Earliest Second to Mark Indices I (Medium)
• 2604. Minimum Time to Eat All Grains (Hard) 👑
• 2702. Minimum Operations to Make Numbers Non-positive (Hard) 👑
• 3453. Separate Squares I (Medium)

1283. Find the Smallest Divisor Given a Threshold

• LeetCode | LeetCode CH (Medium)

• Tags: array, binary search

• 二分答案的关键是找到单调性，然后分析出判断条件

1283. Find the Smallest Divisor Given a Threshold - Python Solution

from typing import List


# Binary Search Min Answer
def smallestDivisor(nums: List[int], threshold: int) -> int:
    left, right = 0, max(nums)

    while left + 1 < right:
        mid = left + (right - left) // 2
        if sum((x - 1) // mid for x in nums) <= threshold - len(nums):
            right = mid
        else:
            left = mid

    return right


if __name__ == "__main__":
    nums = [1, 2, 5, 9]
    threshold = 6
    assert smallestDivisor(nums, threshold) == 5

2187. Minimum Time to Complete Trips

• LeetCode | LeetCode CH (Medium)

• Tags: array, binary search

• Left: always insufficient trips
• Right: always sufficient trips

2187. Minimum Time to Complete Trips - Python Solution

from typing import List


# Binary Search Min Answer
def minimumTime(time: List[int], totalTrips: int) -> int:
    min_t = min(time)
    left = min_t - 1
    right = min_t * totalTrips

    while left + 1 < right:
        mid = left + (right - left) // 2
        if sum(mid // t for t in time) >= totalTrips:
            right = mid
        else:
            left = mid

    return right


if __name__ == "__main__":
    time = [1, 2, 3]
    totalTrips = 5
    assert minimumTime(time, totalTrips) == 3

1870. Minimum Speed to Arrive on Time

• LeetCode | LeetCode CH (Medium)

• Tags: array, binary search

1870. Minimum Speed to Arrive on Time - Python Solution

import math
from typing import List


# Binary Search
def minSpeedOnTime(dist: List[int], hour: float) -> int:
    if hour < len(dist) - 1:
        return -1

    def time_needed(speed):
        total_time = 0
        for i in range(len(dist) - 1):
            total_time += math.ceil(dist[i] / speed)
        total_time += dist[-1] / speed
        return total_time

    left, right = 1, 10**7
    result = -1

    while left <= right:
        mid = left + (right - left) // 2
        if time_needed(mid) <= hour:
            result = mid
            right = mid - 1
        else:
            left = mid + 1

    return result


dist = [1, 3, 2]
hour = 6
print(minSpeedOnTime(dist, hour))  # 1

1011. Capacity To Ship Packages Within D Days

• LeetCode | LeetCode CH (Medium)

• Tags: array, binary search

• A conveyor belt has packages that must be shipped from one port to another within D days. The i-th package has a weight of weights[i]. Each day, we load the ship with packages on the conveyor belt. The ship will be loaded with packages up to its capacity. The ship will not be loaded beyond its capacity. Return the least weight capacity of the ship.

1011. Capacity To Ship Packages Within D Days - Python Solution

from typing import List


# Binary Search
def shipWithinDays(weights: List[int], days: int) -> int:

    def canShip(weights, D, capacity):
        days = 1
        current_weight = 0

        for weight in weights:
            if current_weight + weight > capacity:
                days += 1
                current_weight = 0
            current_weight += weight

        return days <= D

    left, right = max(weights), sum(weights)

    while left <= right:
        mid = left + (right - left) // 2

        if canShip(weights, days, mid):
            right = mid - 1
        else:
            left = mid + 1

    return left


weights = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
days = 5
print(shipWithinDays(weights, days))  # 15

875. Koko Eating Bananas

• LeetCode | LeetCode CH (Medium)

• Tags: array, binary search

• Koko loves to eat bananas. She wants to eat all the bananas within H hours. Each pile has a number of bananas. The i-th pile has piles[i] bananas. Return the minimum integer K such that she can eat all the bananas within H hours.

875. Koko Eating Bananas - Python Solution

from typing import List


# Binary Search
def minEatingSpeed(piles: List[int], h: int) -> int:
    def canEat(piles, k, h):
        hours = 0
        for pile in piles:
            hours += (pile + k - 1) // k
        return hours <= h

    left, right = 1, max(piles)

    while left <= right:
        mid = left + (right - left) // 2

        if canEat(piles, mid, h):
            right = mid - 1
        else:
            left = mid + 1

    return left


piles = [3, 6, 7, 11]
h = 8
print(minEatingSpeed(piles, h))  # 4

3296. Minimum Number of Seconds to Make Mountain Height Zero

• LeetCode | LeetCode CH (Medium)

• Tags: array, math, binary search, greedy, heap priority queue

3296. Minimum Number of Seconds to Make Mountain Height Zero - Python Solution

from bisect import bisect_left
from heapq import heapify, heapreplace
from math import isqrt
from typing import List


# Min Heap
def minNumberOfSecondsMinHeap(
    mountainHeight: int, workerTimes: List[int]
) -> int:
    minHeap = [(t, t, t) for t in workerTimes]
    heapify(minHeap)

    for _ in range(mountainHeight):
        nxt, delta, base = minHeap[0]
        heapreplace(
            minHeap,
            (
                nxt + delta + base,
                delta + base,
                base,
            ),
        )
    return nxt


# Binary Search Min Answer
def minNumberOfSecondsBinarySearchMin(
    mountainHeight: int, workerTimes: List[int]
) -> int:
    def check(m: int) -> bool:
        left_h = mountainHeight
        for t in workerTimes:
            left_h -= (isqrt(m // t * 8 + 1) - 1) // 2
            if left_h <= 0:
                return True
        return False

    max_t = max(workerTimes)
    h = (mountainHeight - 1) // len(workerTimes) + 1
    return bisect_left(range(max_t * h * (h + 1) // 2), True, 1, key=check)


if __name__ == "__main__":
    mountainHeight = 4
    workerTimes = [2, 1, 1]
    assert minNumberOfSecondsMinHeap(mountainHeight, workerTimes) == 3
    assert minNumberOfSecondsBinarySearchMin(mountainHeight, workerTimes) == 3

475. Heaters

• LeetCode | LeetCode CH (Medium)

• Tags: array, two pointers, binary search, sorting

475. Heaters - Python Solution

from bisect import bisect_left, bisect_right
from math import inf
from typing import List


# Left Right Pointers
def findRadiusLR(houses: List[int], heaters: List[int]) -> int:
    heaters = heaters + [-inf, inf]
    houses.sort()
    heaters.sort()
    i, j, res = 0, 0, 0

    while i < len(houses):
        cur = inf
        while heaters[j] <= houses[i]:
            cur = houses[i] - heaters[j]
            j += 1
        cur = min(cur, heaters[j] - houses[i])
        res = max(cur, res)
        i += 1
        j -= 1

    return res


# Binary Search Min Answer
def findRadiusBS(houses: List[int], heaters: List[int]) -> int:
    houses.sort()
    heaters.sort()

    def closest(house):
        left = bisect_right(heaters, house) - 1
        d1 = abs(heaters[left] - house) if left >= 0 else inf

        right = bisect_left(heaters, house)
        d2 = abs(heaters[right] - house) if right < len(heaters) else inf

        return min(d1, d2)

    return max(closest(house) for house in houses)


if __name__ == "__main__":
    houses = [1, 2, 3]
    heaters = [2]
    assert findRadiusLR(houses, heaters) == 1
    assert findRadiusBS(houses, heaters) == 1

2594. Minimum Time to Repair Cars

• LeetCode | LeetCode CH (Medium)

• Tags: array, binary search

2594. Minimum Time to Repair Cars - Python Solution

from math import isqrt
from typing import List


# Binary Search Min Answer
def repairCars(ranks: List[int], cars: int) -> int:
    left, right = 0, max(ranks) * cars * cars

    while left + 1 < right:
        mid = left + (right - left) // 2
        if sum(isqrt(mid // rank) for rank in ranks) >= cars:
            right = mid
        else:
            left = mid
    return right


if __name__ == "__main__":
    ranks = [4, 2, 3, 1]
    cars = 10
    assert repairCars(ranks, cars) == 16

1482. Minimum Number of Days to Make m Bouquets

• LeetCode | LeetCode CH (Medium)

• Tags: array, binary search

1482. Minimum Number of Days to Make m Bouquets - Python Solution

from typing import List


# Binary Search Min Answer
def minDays(bloomDay: List[int], m: int, k: int) -> int:
    n = len(bloomDay)
    if m * k > n:
        return -1

    def canMake(day: int) -> bool:
        bouquets = 0
        flowers = 0
        for bloom in bloomDay:
            if bloom <= day:
                flowers += 1
                if flowers == k:
                    bouquets += 1
                    flowers = 0
            else:
                flowers = 0
        return bouquets >= m

    left, right = min(bloomDay), max(bloomDay)
    res = -1

    while left <= right:
        mid = left + (right - left) // 2
        if canMake(mid):
            res = mid
            right = mid - 1
        else:
            left = mid + 1

    return res


if __name__ == "__main__":
    bloomDay = [1, 10, 3, 10, 2]
    m = 3
    k = 1
    assert minDays(bloomDay, m, k) == 3

3048. Earliest Second to Mark Indices I

• LeetCode | LeetCode CH (Medium)

• Tags: array, binary search

3048. Earliest Second to Mark Indices I - Python Solution

from bisect import bisect_left
from typing import List


# Binary Search Min Answer
def earliestSecondToMarkIndices(
    nums: List[int], changeIndices: List[int]
) -> int:
    n, m = len(nums), len(changeIndices)
    if n > m:
        return -1

    def check(mx: int) -> bool:
        last_t = [-1] * n
        for t, idx in enumerate(changeIndices[:mx]):
            last_t[idx - 1] = t
        if -1 in last_t:
            return False

        cnt = 0
        for i, idx in enumerate(changeIndices[:mx]):
            idx -= 1
            if i == last_t[idx]:
                if nums[idx] > cnt:
                    return False
                cnt -= nums[idx]
            else:
                cnt += 1
        return True

    left = n + sum(nums)
    res = left + bisect_left(range(left, m + 1), True, key=check)
    return -1 if res > m else res


if __name__ == "__main__":
    nums = [2, 2, 0]
    changeIndices = [2, 2, 2, 2, 3, 2, 2, 1]
    assert earliestSecondToMarkIndices(nums, changeIndices) == 8

2604. Minimum Time to Eat All Grains

• LeetCode | LeetCode CH (Hard)

• Tags: array, two pointers, binary search, sorting

2702. Minimum Operations to Make Numbers Non-positive

• LeetCode | LeetCode CH (Hard)

• Tags: array, binary search

3453. Separate Squares I

• LeetCode | LeetCode CH (Medium)

• Tags: array, binary search

Comments