LC-2187 Medium LeetCode

2187. Minimum Time to Complete Trips

Read the full problem statement on LeetCode.

Difficulty: medium Acceptance: 39% Topics: Array, Binary Search

Reading material

Arrays & Hashing 12 min Binary Search 12 min

Reference solution (spoiler · python)

# Time:  O(nlogr)
# Space: O(1)

# binary search
class Solution(object):
    def minimumTime(self, time, totalTrips):
        """
        :type time: List[int]
        :type totalTrips: int
        :rtype: int
        """
        def check(time, totalTrips, x):
            return sum(x//t for t in time) >= totalTrips

        left, right = 1, max(time)*totalTrips
        while left <= right:
            mid = left + (right-left)//2
            if check(time, totalTrips, mid):
                right = mid-1
            else:
                left = mid+1
        return left

Solution from kamyu104/LeetCode-Solutions · MIT