LeetCode 2594 - Minimum Time to Repair Cars

The problem gives us a list of mechanics, where each mechanic has a specific rank. A mechanic with rank r takes r n^2 minutes to repair n cars. This means the repair time grows quadratically as the number of assigned cars increases.

leetcodemediumarraybinary-search

LeetCode Problem 2594

Difficulty: 🟡 Medium
Topics: Array, Binary Search

Solution

Problem Understanding

The problem gives us a list of mechanics, where each mechanic has a specific rank. A mechanic with rank r takes r * n^2 minutes to repair n cars. This means the repair time grows quadratically as the number of assigned cars increases.

We are also given an integer cars, representing the total number of cars that must be repaired. All mechanics work simultaneously, so the total completion time is determined by the slowest mechanic among the assigned workloads.

The goal is to determine the minimum amount of time required so that all cars can be repaired collectively.

To understand the formula better, consider a mechanic with rank 2:

  • Repairing 1 car takes 2 * 1^2 = 2
  • Repairing 2 cars takes 2 * 2^2 = 8
  • Repairing 3 cars takes 2 * 3^2 = 18

The important observation is that for a fixed amount of time T, we can determine how many cars a mechanic can repair by solving:

$$r \cdot n^2 \le T$$

Rearranging:

$$n^2 \le \frac{T}{r}$$

$$n \le \sqrt{\frac{T}{r}}$$

So a mechanic with rank r can repair at most:

$$\left\lfloor \sqrt{\frac{T}{r}} \right\rfloor$$

cars within time T.

The constraints are large:

  • Up to 10^5 mechanics
  • Up to 10^6 cars

These limits immediately rule out simulation-based solutions or exhaustive search approaches. We need something significantly more efficient.

Several edge cases are important:

  • Only one mechanic exists
  • Only one car exists
  • All mechanics have the same rank
  • One mechanic is dramatically faster than the others
  • The optimal answer may become very large, so integer overflow must be considered in Go

The problem guarantees:

  • At least one mechanic exists
  • All ranks are positive
  • At least one car exists

This means we never need to handle invalid or empty input.

Approaches

Brute Force Approach

A naive approach would be to simulate time minute by minute and check how many cars can be repaired at each moment.

For every time t, we could calculate:

$$\sum \left\lfloor \sqrt{\frac{t}{r_i}} \right\rfloor$$

If the total repaired cars reaches or exceeds cars, then t is a valid answer.

While this approach is conceptually simple, iterating through every possible time value is far too slow. The maximum possible answer can become extremely large. For example, if one mechanic with rank 100 repairs 10^6 cars:

$$100 \cdot (10^6)^2 = 10^{14}$$

Checking every time value up to 10^{14} is infeasible.

Key Insight

The critical observation is that the answer space is monotonic.

If it is possible to repair all cars within time T, then it is also possible within any larger time.

Similarly:

  • If time T is insufficient, all smaller times are also insufficient.
  • If time T works, all larger times also work.

This monotonic property makes binary search ideal.

Instead of searching through all times linearly, we binary search over the answer space.

For a candidate time mid, we compute how many cars all mechanics can collectively repair:

$$\sum \left\lfloor \sqrt{\frac{mid}{r_i}} \right\rfloor$$

If the total is at least cars, then mid is feasible, and we try smaller times.

Otherwise, we need more time.

This reduces the problem from a huge linear search into a logarithmic search.

Approach Time Complexity Space Complexity Notes
Brute Force O(MaxTime × n) O(1) Checks every possible time value
Optimal O(n log(MaxTime)) O(1) Uses binary search on the answer

Algorithm Walkthrough

Optimal Binary Search Algorithm

  1. Initialize the search boundaries.

The minimum possible time is 1.

The maximum possible time occurs when the fastest mechanic repairs all cars alone.

If the minimum rank is minRank, then:

$$maxTime = minRank \cdot cars^2$$ 2. Start binary search on the range [left, right].

At each iteration:

$$mid = \frac{left + right}{2}$$ 3. Compute how many cars can be repaired within mid minutes.

For each mechanic with rank r:

$$repaired = \left\lfloor \sqrt{\frac{mid}{r}} \right\rfloor$$

Add all repaired cars together. 4. Check feasibility.

  • If total repaired cars is at least cars, then mid is sufficient.
  • Store it as a candidate answer and continue searching the left half.
  • Otherwise, search the right half.
  1. Continue until left > right.
  2. Return the smallest feasible time found.

Why it works

The binary search works because feasibility is monotonic.

If mechanics can repair all cars within time T, then giving them more time cannot reduce their capacity. Therefore, all larger times are also feasible.

This guarantees a clean transition point from infeasible to feasible values, which is exactly the condition required for binary search.

Python Solution

from typing import List
import math

class Solution:
    def repairCars(self, ranks: List[int], cars: int) -> int:
        left = 1
        right = min(ranks) * cars * cars

        answer = right

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

            repaired_cars = 0

            for rank in ranks:
                repaired_cars += math.isqrt(mid // rank)

            if repaired_cars >= cars:
                answer = mid
                right = mid - 1
            else:
                left = mid + 1

        return answer

The implementation begins by defining the binary search boundaries.

The lower bound is 1, while the upper bound assumes the fastest mechanic repairs every car alone.

Inside the binary search loop, the midpoint represents a candidate repair time.

For each mechanic, we compute:

$$\left\lfloor \sqrt{\frac{mid}{rank}} \right\rfloor$$

Python's math.isqrt() is used because it performs integer square root efficiently and avoids floating-point precision issues.

If the total repaired cars meet or exceed the required number of cars, the current time is feasible, so we attempt to find an even smaller valid time.

Otherwise, we increase the search range.

The final answer is the smallest feasible time discovered during the search.

Go Solution

package main

import "math"

func repairCars(ranks []int, cars int) int64 {
	left := int64(1)

	minRank := ranks[0]
	for _, rank := range ranks {
		if rank < minRank {
			minRank = rank
		}
	}

	right := int64(minRank) * int64(cars) * int64(cars)

	answer := right

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

		repairedCars := int64(0)

		for _, rank := range ranks {
			repairedCars += int64(math.Sqrt(float64(mid / int64(rank))))
		}

		if repairedCars >= int64(cars) {
			answer = mid
			right = mid - 1
		} else {
			left = mid + 1
		}
	}

	return answer
}

The Go implementation follows the same binary search logic as the Python version.

One important difference is integer overflow handling. Since the upper bound can reach 10^14, all time-related variables use int64.

Go does not provide an integer square root function equivalent to Python's math.isqrt, so math.Sqrt is used with floating-point conversion. The result is converted back to int64.

The midpoint calculation uses:

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

which avoids overflow that could occur with (left + right) / 2.

Worked Examples

Example 1

Input:

ranks = [4,2,3,1]
cars = 10

Initial search range:

Variable Value
left 1
right 1 × 10² = 100

Binary Search Iterations

mid Cars Repaired Feasible?
50 3 + 5 + 4 + 7 = 19 Yes
25 2 + 3 + 2 + 5 = 12 Yes
12 1 + 2 + 2 + 3 = 8 No
18 2 + 3 + 2 + 4 = 11 Yes
15 1 + 2 + 2 + 3 = 8 No
16 2 + 2 + 2 + 4 = 10 Yes

The smallest feasible value is 16.

Final answer:

16

Example 2

Input:

ranks = [5,1,8]
cars = 6

Initial range:

Variable Value
left 1
right 1 × 6² = 36

Binary Search Iterations

mid Cars Repaired Feasible?
18 1 + 4 + 1 = 6 Yes
9 1 + 3 + 1 = 5 No
13 1 + 3 + 1 = 5 No
15 1 + 3 + 1 = 5 No
16 1 + 4 + 1 = 6 Yes

Final answer:

16

Complexity Analysis

Measure Complexity Explanation
Time O(n log(MaxTime)) Binary search iterations times mechanics traversal
Space O(1) Only constant extra memory is used

The binary search range extends up to:

$$minRank \cdot cars^2$$

Since binary search halves the search space each iteration, the number of iterations is:

$$O(\log(maxTime))$$

For each iteration, we traverse all mechanics once.

Therefore, the total complexity becomes:

$$O(n \log(maxTime))$$

The algorithm uses only a few variables regardless of input size, so the space complexity is constant.

Test Cases

from typing import List

class Solution:
    def repairCars(self, ranks: List[int], cars: int) -> int:
        import math

        left = 1
        right = min(ranks) * cars * cars

        answer = right

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

            repaired = 0

            for rank in ranks:
                repaired += math.isqrt(mid // rank)

            if repaired >= cars:
                answer = mid
                right = mid - 1
            else:
                left = mid + 1

        return answer

sol = Solution()

assert sol.repairCars([4,2,3,1], 10) == 16  # Example 1
assert sol.repairCars([5,1,8], 6) == 16  # Example 2

assert sol.repairCars([1], 1) == 1  # Single mechanic, single car
assert sol.repairCars([1], 5) == 25  # One mechanic repairs everything
assert sol.repairCars([100], 1) == 100  # Large rank with one car

assert sol.repairCars([1,1,1], 3) == 1  # All mechanics repair one car each
assert sol.repairCars([1,1,1], 12) == 16  # Equal distribution among mechanics

assert sol.repairCars([3,3,3], 1) == 3  # Minimum cars
assert sol.repairCars([2,3,7], 20) == 98  # Mixed mechanic speeds

assert sol.repairCars([1,100,100], 10) == 64  # Fast mechanic dominates
assert sol.repairCars([5,5,5,5], 100) == 3125  # Large workload

assert sol.repairCars([1] * 100000, 1000000) == 100  # Stress test
Test Why
[4,2,3,1], 10 Validates first example
[5,1,8], 6 Validates second example
[1], 1 Smallest valid input
[1], 5 Single mechanic handles all cars
[100], 1 Large rank edge case
[1,1,1], 3 Multiple mechanics working simultaneously
[1,1,1], 12 Balanced workload distribution
[3,3,3], 1 Minimal car count
[2,3,7], 20 Mixed repair efficiencies
[1,100,100], 10 One mechanic dominates throughput
[5,5,5,5], 100 Large total workload
100000 mechanics Stress test for performance

Edge Cases

Single Mechanic

If only one mechanic exists, that mechanic must repair every car alone.

For example:

ranks = [2]
cars = 5

The answer becomes:

$$2 \cdot 5^2 = 50$$

A naive implementation might incorrectly assume work can always be distributed. Our solution handles this naturally because the feasibility calculation works correctly even with one mechanic.

Extremely Large Answer Space

The maximum possible answer can be very large:

$$100 \cdot (10^6)^2 = 10^{14}$$

This can overflow 32-bit integers.

The Go implementation uses int64 everywhere for time calculations to avoid overflow bugs.

One Mechanic Much Faster Than Others

Consider:

ranks = [1,100,100]
cars = 10

The mechanic with rank 1 does almost all the work.

Some greedy approaches may incorrectly try to distribute cars evenly among mechanics. That does not produce the optimal answer.

Our binary search solution avoids explicit assignment entirely. It only checks total repair capacity within a given time, which automatically accounts for unequal workloads.

Perfect Square Boundaries

The formula involves square roots, which can introduce off-by-one errors.

For example:

mid = 16
rank = 1

$$\sqrt{16} = 4$$

The mechanic can repair exactly 4 cars.

Using floating-point arithmetic carelessly could incorrectly produce 3.999999. Python avoids this issue with math.isqrt, and Go safely truncates the result after math.Sqrt.