Solution Approach

The solution uses the binary search template to find the minimum time required. We're looking for the first time value where we can complete at least totalTrips - a classic first_true_index pattern.

Defining the Feasible Function:

A time value t is feasible if we can complete at least totalTrips in time t:

feasible(t) = sum(t // busTime for busTime in time) >= totalTrips

This creates the pattern: false, false, ..., true, true, true We want to find the first true (minimum feasible time).

Setting Up the Search Range:

• left = 1: Minimum possible time (at least 1 unit needed for any trip)
• right = min(time) * totalTrips: Maximum time needed if only the fastest bus operates

Binary Search Template:

left, right = 1, min(time) * totalTrips
first_true_index = -1

while left <= right:
    mid = (left + right) // 2
    if feasible(mid):  # Can complete totalTrips in mid time
        first_true_index = mid
        right = mid - 1  # Try to find smaller time
    else:
        left = mid + 1  # Need more time

return first_true_index

Why This Works:

• When feasible(mid) is true, we've found a valid answer but want to minimize, so we search left (right = mid - 1)
• When feasible(mid) is false, we need more time, so we search right (left = mid + 1)
• first_true_index always holds the smallest feasible time found so far

Time Complexity: O(n × log(min(time) × totalTrips)) where n is the number of buses.

Space Complexity: O(1) - only constant extra space used.

Example Walkthrough

Let's trace through with time = [2, 3, 5] and totalTrips = 8.

Initialize:

• left = 1, right = min(2, 3, 5) × 8 = 16
• first_true_index = -1

Iteration 1: left = 1, right = 16

• mid = (1 + 16) // 2 = 8
• Trips at time 8: 8//2 + 8//3 + 8//5 = 4 + 2 + 1 = 7
• feasible(8) = (7 >= 8) → false
• left = 8 + 1 = 9

Iteration 2: left = 9, right = 16

• mid = (9 + 16) // 2 = 12
• Trips at time 12: 12//2 + 12//3 + 12//5 = 6 + 4 + 2 = 12
• feasible(12) = (12 >= 8) → true
• first_true_index = 12, right = 12 - 1 = 11

Iteration 3: left = 9, right = 11

• mid = (9 + 11) // 2 = 10
• Trips at time 10: 10//2 + 10//3 + 10//5 = 5 + 3 + 2 = 10
• feasible(10) = (10 >= 8) → true
• first_true_index = 10, right = 10 - 1 = 9

Iteration 4: left = 9, right = 9

• mid = (9 + 9) // 2 = 9
• Trips at time 9: 9//2 + 9//3 + 9//5 = 4 + 3 + 1 = 8
• feasible(9) = (8 >= 8) → true
• first_true_index = 9, right = 9 - 1 = 8

Termination: left = 9 > right = 8, exit loop

Result: first_true_index = 9

Verification: At time 9, buses complete exactly 8 trips. At time 8, only 7 trips - insufficient.

Time and Space Complexity

The time complexity is O(n × log(m × k)), where:

• n is the length of the array time (used in the sum computation within the key function)
• m is the minimum value in the array time (found by min(time))
• k is totalTrips

The binary search operates on a range from 0 to mx = min(time) × totalTrips, which has O(m × k) elements. Each binary search iteration calls the key function lambda x: sum(x // v for v in time), which takes O(n) time to compute the sum over all buses. Since binary search performs O(log(m × k)) iterations, the total time complexity is O(n × log(m × k)).

The space complexity is O(1) as the algorithm only uses a constant amount of extra space for variables. The bisect_left function with a range object and key function doesn't create the entire range in memory but rather computes values on-the-fly, maintaining constant space usage.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Using Wrong Binary Search Template Variant

A common mistake is using the while left < right with right = mid variant instead of the standard template with first_true_index tracking.

Wrong approach:

while left < right:
    mid = (left + right) // 2
    if feasible(mid):
        right = mid  # Wrong: should be right = mid - 1
    else:
        left = mid + 1
return left  # Wrong: should return first_true_index

Correct approach (using template):

first_true_index = -1
while left <= right:
    mid = (left + right) // 2
    if feasible(mid):
        first_true_index = mid
        right = mid - 1
    else:
        left = mid + 1
return first_true_index

2. Integer Overflow for Large Inputs

When totalTrips is very large (up to 10^7) and min(time) is also large, the multiplication min(time) * totalTrips could overflow in languages with fixed integer sizes.

Solution: Use appropriate data types (long in Java, long long in C++, bigint in TypeScript):

long right = (long) minTime * totalTrips;  // Cast to long before multiplication

3. Forgetting to Handle Edge Cases

When all buses are very slow or totalTrips is 1, the result might be at the boundary.

Solution: The template handles this naturally since first_true_index will be set on the first feasible value found.

4. Off-by-One in Search Range

Starting with left = 0 instead of left = 1 can cause issues since time 0 results in 0 trips.

Solution: Always start with left = 1 as the minimum meaningful time value.