Facebook Pixel

2594. Minimum Time to Repair Cars

MediumArrayBinary Search
Leetcode Link

Problem Description

You have an array ranks where each element represents the rank of a mechanic. A mechanic with rank r needs r * n² minutes to repair n cars.

Given:

  • ranks: an integer array where ranks[i] is the rank of the i-th mechanic
  • cars: the total number of cars that need to be repaired

The key points are:

  • Each mechanic works independently and simultaneously
  • A mechanic with rank r takes r * n² minutes to repair exactly n cars
  • For example, a mechanic with rank 3 would take:
    • 3 × 1² = 3 minutes to repair 1 car
    • 3 × 2² = 12 minutes to repair 2 cars
    • 3 × 3² = 27 minutes to repair 3 cars

You need to find the minimum time required to repair all cars when all mechanics work at the same time. Each mechanic can repair any number of cars (up to the total needed), and you want to distribute the work optimally to minimize the total time.

The solution uses binary search on the time. For a given time t, we can calculate how many cars each mechanic can repair: if a mechanic has rank r, they can repair ⌊√(t/r)⌋ cars in time t. We search for the minimum time where the total number of cars that can be repaired is at least equal to the required number of cars.

Quick Interview Experience
Help others by sharing your interview experience
Have you seen this problem before?

Intuition

The key insight is recognizing that this is a monotonic problem - as we give mechanics more time, they can repair more cars. This monotonic property makes binary search a natural fit.

Let's think about it differently: instead of asking "how should we distribute cars to minimize time?", we can ask "given a fixed amount of time t, can we repair all the cars?" This transforms the optimization problem into a decision problem.

For any given time t, we can calculate exactly how many cars each mechanic can complete. Since a mechanic with rank r needs r * n² minutes to repair n cars, we can rearrange this formula: if we have t minutes available, then t = r * n², which means n = √(t/r). So each mechanic can repair ⌊√(t/r)⌋ cars in time t.

The beautiful part is that we don't need to figure out the optimal distribution of cars among mechanics. We just need to check if the total capacity (sum of all cars that can be repaired by all mechanics in time t) meets our requirement. If it does, we might be able to do it faster (try a smaller time). If it doesn't, we definitely need more time.

This naturally leads to binary search on the time:

  • If mechanics can repair at least cars vehicles in time t, try a smaller time
  • If they can't repair enough in time t, we need more time

The search space for time ranges from 0 to some upper bound. The worst case would be if we only had one mechanic with the highest rank repairing all cars sequentially, giving us an upper bound of ranks[0] * cars * cars.

Learn more about Binary Search patterns.

Solution Implementation

1from typing import List
2from math import sqrt
3
4class Solution:
5    def repairCars(self, ranks: List[int], cars: int) -> int:
6        def feasible(time_limit: int) -> bool:
7            """Check if all cars can be repaired within the given time limit."""
8            total_cars_repaired = 0
9            for rank in ranks:
10                total_cars_repaired += int(sqrt(time_limit // rank))
11            return total_cars_repaired >= cars
12
13        min_rank = min(ranks)
14        left, right = 0, min_rank * cars * cars
15        first_true_index = -1
16
17        while left <= right:
18            mid = (left + right) // 2
19            if feasible(mid):
20                first_true_index = mid
21                right = mid - 1
22            else:
23                left = mid + 1
24
25        return first_true_index
26
1class Solution {
2    public long repairCars(int[] ranks, int cars) {
3        int minRank = ranks[0];
4        for (int rank : ranks) {
5            minRank = Math.min(minRank, rank);
6        }
7
8        long left = 0;
9        long right = (long) minRank * cars * cars;
10        long firstTrueIndex = -1;
11
12        while (left <= right) {
13            long mid = left + (right - left) / 2;
14            if (feasible(ranks, cars, mid)) {
15                firstTrueIndex = mid;
16                right = mid - 1;
17            } else {
18                left = mid + 1;
19            }
20        }
21
22        return firstTrueIndex;
23    }
24
25    private boolean feasible(int[] ranks, int cars, long timeLimit) {
26        long totalCarsRepaired = 0;
27        for (int rank : ranks) {
28            totalCarsRepaired += (long) Math.sqrt(timeLimit / rank);
29        }
30        return totalCarsRepaired >= cars;
31    }
32}
33
1class Solution {
2public:
3    long long repairCars(vector<int>& ranks, int cars) {
4        int minRank = *min_element(ranks.begin(), ranks.end());
5
6        long long left = 0;
7        long long right = 1LL * minRank * cars * cars;
8        long long firstTrueIndex = -1;
9
10        while (left <= right) {
11            long long mid = left + (right - left) / 2;
12            if (feasible(ranks, cars, mid)) {
13                firstTrueIndex = mid;
14                right = mid - 1;
15            } else {
16                left = mid + 1;
17            }
18        }
19
20        return firstTrueIndex;
21    }
22
23private:
24    bool feasible(vector<int>& ranks, int cars, long long timeLimit) {
25        long long totalCarsRepaired = 0;
26        for (int rank : ranks) {
27            totalCarsRepaired += (long long)sqrt(timeLimit / rank);
28        }
29        return totalCarsRepaired >= cars;
30    }
31};
32
1function repairCars(ranks: number[], cars: number): number {
2    const feasible = (timeLimit: number): boolean => {
3        let totalCarsRepaired = 0;
4        for (const rank of ranks) {
5            totalCarsRepaired += Math.floor(Math.sqrt(timeLimit / rank));
6        }
7        return totalCarsRepaired >= cars;
8    };
9
10    const minRank = Math.min(...ranks);
11    let left = 0;
12    let right = minRank * cars * cars;
13    let firstTrueIndex = -1;
14
15    while (left <= right) {
16        const mid = Math.floor((left + right) / 2);
17        if (feasible(mid)) {
18            firstTrueIndex = mid;
19            right = mid - 1;
20        } else {
21            left = mid + 1;
22        }
23    }
24
25    return firstTrueIndex;
26}
27

Solution Approach

The implementation uses the standard binary search template with a feasible function to check if a given time is sufficient.

Binary Search Template: We use the first_true_index template to find the minimum time where we can repair all cars:

  • Initialize left = 0 and right = min_rank * cars * cars (worst case)
  • Track the answer with first_true_index = -1
  • Use while left <= right loop structure
  • When feasible(mid) returns True, update first_true_index = mid and search left with right = mid - 1
  • When feasible(mid) returns False, search right with left = mid + 1

Feasible Function: The feasible(time_limit) function determines if all cars can be repaired within time_limit:

  • For each mechanic with rank r, calculate cars they can repair: ⌊√(time_limit/r)⌋
  • Sum up all cars repaired by all mechanics
  • Return True if total ≥ cars, otherwise False

Why This Creates a Monotonic Pattern: As time increases, each mechanic can repair more cars. This creates the pattern:

time:     0   1   2   ...  15   16   17  ...
feasible: F   F   F   ...  F    T    T   ...

The binary search finds the first True in this sequence.

Time Complexity:

  • Binary search runs in O(log(min_rank * cars²)) iterations
  • Each feasible check iterates through all mechanics: O(len(ranks))
  • Overall: O(len(ranks) * log(min_rank * cars²))

Ready to land your dream job?

Unlock your dream job with a 5-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's walk through a concrete example with ranks = [4, 2, 3, 1] and cars = 10.

Step 1: Set up binary search range

  • Lower bound: 0
  • Upper bound: 4 × 10 × 10 = 400 (using first mechanic's rank)
  • We'll search for the minimum time in range [0, 400)

Step 2: Binary search process

Let's trace through a few iterations:

Check time = 200 (midpoint)

  • Mechanic rank 4: Can repair ⌊√(200/4)⌋ = ⌊√50⌋ = 7 cars
  • Mechanic rank 2: Can repair ⌊√(200/2)⌋ = ⌊√100⌋ = 10 cars
  • Mechanic rank 3: Can repair ⌊√(200/3)⌋ = ⌊√66.67⌋ = 8 cars
  • Mechanic rank 1: Can repair ⌊√(200/1)⌋ = ⌊√200⌋ = 14 cars
  • Total: 7 + 10 + 8 + 14 = 39 cars ✓ (more than 10 needed)
  • Since we can repair all cars, try a smaller time

Check time = 100

  • Mechanic rank 4: Can repair ⌊√(100/4)⌋ = ⌊√25⌋ = 5 cars
  • Mechanic rank 2: Can repair ⌊√(100/2)⌋ = ⌊√50⌋ = 7 cars
  • Mechanic rank 3: Can repair ⌊√(100/3)⌋ = ⌊√33.33⌋ = 5 cars
  • Mechanic rank 1: Can repair ⌊√(100/1)⌋ = ⌊√100⌋ = 10 cars
  • Total: 5 + 7 + 5 + 10 = 27 cars ✓ (still more than 10)
  • Try even smaller time

Check time = 50

  • Mechanic rank 4: Can repair ⌊√(50/4)⌋ = ⌊√12.5⌋ = 3 cars
  • Mechanic rank 2: Can repair ⌊√(50/2)⌋ = ⌊√25⌋ = 5 cars
  • Mechanic rank 3: Can repair ⌊√(50/3)⌋ = ⌊√16.67⌋ = 4 cars
  • Mechanic rank 1: Can repair ⌊√(50/1)⌋ = ⌊√50⌋ = 7 cars
  • Total: 3 + 5 + 4 + 7 = 19 cars ✓ (still sufficient)

Check time = 25

  • Mechanic rank 4: Can repair ⌊√(25/4)⌋ = ⌊√6.25⌋ = 2 cars
  • Mechanic rank 2: Can repair ⌊√(25/2)⌋ = ⌊√12.5⌋ = 3 cars
  • Mechanic rank 3: Can repair ⌊√(25/3)⌋ = ⌊√8.33⌋ = 2 cars
  • Mechanic rank 1: Can repair ⌊√(25/1)⌋ = ⌊√25⌋ = 5 cars
  • Total: 2 + 3 + 2 + 5 = 12 cars ✓ (just enough!)

Check time = 12

  • Mechanic rank 4: Can repair ⌊√(12/4)⌋ = ⌊√3⌋ = 1 car
  • Mechanic rank 2: Can repair ⌊√(12/2)⌋ = ⌊√6⌋ = 2 cars
  • Mechanic rank 3: Can repair ⌊√(12/3)⌋ = ⌊√4⌋ = 2 cars
  • Mechanic rank 1: Can repair ⌊√(12/1)⌋ = ⌊√12⌋ = 3 cars
  • Total: 1 + 2 + 2 + 3 = 8 cars ✗ (not enough)
  • Need more time

Check time = 16

  • Mechanic rank 4: Can repair ⌊√(16/4)⌋ = ⌊√4⌋ = 2 cars
  • Mechanic rank 2: Can repair ⌊√(16/2)⌋ = ⌊√8⌋ = 2 cars
  • Mechanic rank 3: Can repair ⌊√(16/3)⌋ = ⌊√5.33⌋ = 2 cars
  • Mechanic rank 1: Can repair ⌊√(16/1)⌋ = ⌊√16⌋ = 4 cars
  • Total: 2 + 2 + 2 + 4 = 10 cars ✓ (exactly enough!)

The binary search converges to 16 minutes as the minimum time needed to repair all 10 cars.

Verification: With 16 minutes, the optimal distribution would be:

  • Mechanic rank 1 repairs 4 cars (takes 1×4² = 16 minutes)
  • Mechanic rank 2 repairs 2 cars (takes 2×2² = 8 minutes)
  • Mechanic rank 3 repairs 2 cars (takes 3×2² = 12 minutes)
  • Mechanic rank 4 repairs 2 cars (takes 4×2² = 16 minutes)
  • Total: 4 + 2 + 2 + 2 = 10 cars ✓

Time and Space Complexity

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

  • n is the length of the ranks list (number of mechanics)
  • M is the upper bound of the binary search, which is ranks[0] * cars * cars

The binary search performed by bisect_left runs in O(log M) time. For each iteration of the binary search, the check function is called, which iterates through all n elements in ranks to compute the sum, taking O(n) time. Therefore, the overall time complexity is O(n × log M).

The space complexity is O(1) as the algorithm only uses a constant amount of extra space. The check function uses a generator expression that doesn't create an intermediate list, and only maintains variables for the sum calculation and the binary search bounds.

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

Common Pitfalls

1. Using Wrong Binary Search Template

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

Incorrect:

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

Correct (template-compliant):

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. Incorrect Binary Search Bounds

The upper bound should use min(ranks) (the most efficient mechanic), not an arbitrary rank.

Incorrect:

max_time = ranks[0] * cars * cars  # ranks[0] might not be minimum

Correct:

min_rank = min(ranks)
max_time = min_rank * cars * cars

3. Integer Overflow in Square Root Calculation

When calculating sqrt(time_limit // rank), precision issues can occur with large values.

Solution: Use floating-point division when needed:

cars_by_mechanic = int(sqrt(time_limit / rank))

4. Not Handling Edge Cases

When first_true_index remains -1, it means no valid time was found. For this problem, a valid answer always exists (the upper bound guarantees it), but the template handles edge cases gracefully.

Loading...
Discover Your Strengths and Weaknesses: Take Our 5-Minute Quiz to Tailor Your Study Plan:

Which algorithm is best for finding the shortest distance between two points in an unweighted graph?

Recommended Readings

Vanilla Binary Search

https assets algo monster cover_photos Binary_Search svg Binary Search Intuition Binary search is an efficient array search algorithm It works by narrowing down the search range by half each time If you have looked up a word in a physical dictionary you've already used binary search in real life Let's

Coding Interview Patterns: The Smart, Data-Driven Way to Prepare for Tech Interviews

Coding Interview Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way

Recursion Review

Recursion If you prefer videos here's a video that explains recursion in a fun and easy way Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https assets algo monster recursion jpg You first call Ben and ask him

Want a Structured Path to Master System Design Too? Don’t Miss This!

Load More