Minimum Time to Repair Cars solution and explanation
Deloitte
Google
9 more videos on this problem
Minimum Time to Repair Cars - Leetcode 2594 - PythonNeetCodeIO · 15:45 · 13K views
Minimum Time to Repair Cars | With Minute Details | Leetcode 2594 | codestorywithMIKcodestorywithMIK · 29:35 · 11K views
2594. Minimum Time to Repair Cars || Binary Search on AnswerAryan Mittal · 10:25 · 5K views
Minimum Time to Repair Cars | Leetcode 2594Techdose · 24:09 · 4K views
2594. Minimum Time to Repair Cars | leetcode daily challenge | dsa | shashcodeShashCode · 15:35 · 2K views
2594. Minimum Time to Repair Cars - JAVA (Biweekly Contest 100)Sourin Majumdar · 11:11 · 1K views
2594. Minimum Time to Repair Cars (Leetcode Medium)Programming Live with Larry · 16:28 · 603 views
Leetcode 2594. Minimum Time to Repair CarsElite Code · 30:47 · 426 views
Leetcode: 2594 | Minimum Time to Repair Cars| C++ | Easy Solution | Hindi | Beginner FriendlyDrunken Programmer · 7:33 · 376 views
LeetCode 2594 Minimum Time to Repair Cars | Binary Search on Answer SpaceCode Harmony · 19:48 · 178 views
The problem
You are given an integer array ranks representing the ranks of some mechanics. ranksi is the rank of the ith mechanic. A mechanic with a rank r can repair n cars in r * n2 minutes.
You are also given an integer cars representing the total number of cars waiting in the garage to be repaired.
Return the minimum time taken to repair all the cars.
Note: All the mechanics can repair the cars simultaneously.
Example 1:
Input: ranks = [4,2,3,1], cars = 10 Output: 16 Explanation: - The first mechanic will repair two cars. The time required is 4 * 2 * 2 = 16 minutes. - The second mechanic will repair two cars. The time required is 2 * 2 * 2 = 8 minutes. - The third mechanic will repair two cars. The time required is 3 * 2 * 2 = 12 minutes. - The fourth mechanic will repair four cars. The time required is 1 * 4 * 4 = 16 minutes. It can be proved that the cars cannot be repaired in less than 16 minutes.
Example 2:
Input: ranks = [5,1,8], cars = 6 Output: 16 Explanation: - The first mechanic will repair one car. The time required is 5 * 1 * 1 = 5 minutes. - The second mechanic will repair four cars. The time required is 1 * 4 * 4 = 16 minutes. - The third mechanic will repair one car. The time required is 8 * 1 * 1 = 8 minutes. It can be proved that the cars cannot be repaired in less than 16 minutes.
Constraints:
1 <= ranks.length <= 1051 <= ranks[i] <= 1001 <= cars <= 106
Approach overview
Problem Overview: You are given an array ranks where each mechanic with rank r takes r * n² minutes to repair n cars. The goal is to determine the minimum time required for all mechanics combined to repair a given number of cars.
Approach 1: Binary Search on Minimum Time (Time: O(n log T), Space: O(1))
The key observation: if a mechanic has rank r, the maximum cars they can repair in time t is floor(sqrt(t / r)). Instead of simulating repairs directly, search for the smallest time t where the total cars repaired by all mechanics is at least the required number. Use binary search over the time range from 1 to min(rank) * cars². For each candidate time, iterate through the array of ranks and sum how many cars each mechanic can repair. If the total meets the requirement, move left to minimize time; otherwise move right.
This works because the number of cars repaired increases monotonically with time, which makes the problem ideal for binary search on the answer. The check operation runs in linear time across mechanics.
Approach 2: Greedy with Priority Queue (Time: O(cars log n), Space: O(n))
Another way is to simulate the next available repair completion using a min-heap. Each mechanic initially schedules their first car repair taking r * 1² time. Push these into a priority queue ordered by completion time. Repeatedly pop the earliest finishing repair, assign the next car to that mechanic, compute the new completion time r * (k+1)², and push it back. Continue until all cars are assigned.
This greedy simulation always processes the earliest finishing repair next. While intuitive, it becomes slower when the number of cars is large because every repair assignment involves heap operations.
Recommended for interviews: Binary search on time is the expected solution. Interviewers want to see that you recognize the monotonic property and convert the problem into a search over the answer space. The priority queue approach demonstrates understanding of scheduling but does not scale as well for large inputs.
Approach 1: Binary Search on Minimum Time
This approach leverages binary search to find the minimum time required to repair all the cars. We observe that if a mechanic with rank r repairs n cars, they can do so in r * n^2 minutes. Our goal is to minimize the maximum amount of time any mechanic would spend to repair the cars. We perform binary search on time to decide the least time possible where all cars can be finished.
The key observation here is that given a time, we can check if it's possible for all cars to be repaired within that time by distributing cars among all mechanics optimally.
def can_repair(ranks, cars, time):
total_cars = 0
for rank in ranks:
total_cars += time // (rank * rank)
if total_cars >= cars:
return True
return False
def min_time_repair_cars(ranks, cars):
low, high = 1, int(1e9)
while low < high:
mid = (low + high) // 2
if can_repair(ranks, cars, mid):
high = mid
else:
low = mid + 1
return low
ranks = [4, 2, 3, 1]
cars = 10
print(min_time_repair_cars(ranks, cars))import java.util.*;
public class MinimumTimeToRepairCars {
private static boolean canRepair(int[] ranks, int cars, int time) {
int totalCars = 0;
for (int rank : ranks) {
totalCars += time / (rank * rank);
if (totalCars >= cars) return true;
}
return false;
}
public static int minTimeRepairCars(int[] ranks, int cars) {
int low = 1, high = (int)1e9;
while (low < high) {
int mid = (low + high) / 2;
if (canRepair(ranks, cars, mid)) {
high = mid;
} else {
low = mid + 1;
}
}
return low;
}
public static void main(String[] args) {
int[] ranks = {4, 2, 3, 1};
int cars = 10;
System.out.println(minTimeRepairCars(ranks, cars));
}
}#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
bool canRepair(const vector<int>& ranks, int cars, int time) {
int totalCars = 0;
for (int r : ranks) {
totalCars += time / (r * r);
if (totalCars >= cars) return true;
}
return false;
}
int minTimeRepairCars(const vector<int>& ranks, int cars) {
int left = 1, right = 1e8, answer = right;
while (left <= right) {
int mid = left + (right - left) / 2;
if (canRepair(ranks, cars, mid)) {
answer = mid;
right = mid - 1;
} else {
left = mid + 1;
}
}
return answer;
}
int main() {
vector<int> ranks = {4, 2, 3, 1};
int cars = 10;
cout << minTimeRepairCars(ranks, cars) << endl;
return 0;
}function canRepair(ranks, cars, time) {
let totalCars = 0;
for (let rank of ranks) {
totalCars += Math.floor(time / (rank * rank));
if (totalCars >= cars) {
return true;
}
}
return false;
}
function minTimeRepairCars(ranks, cars) {
let low = 1, high = 1e9;
while (low < high) {
let mid = Math.floor((low + high) / 2);
if (canRepair(ranks, cars, mid)) {
high = mid;
} else {
low = mid + 1;
}
}
return low;
}
const ranks = [4, 2, 3, 1];
const cars = 10;
console.log(minTimeRepairCars(ranks, cars));#include <stdio.h>
int canRepair(int ranks[], int n, int cars, int time) {
int totalCars = 0;
for (int i = 0; i < n; i++) {
totalCars += (int)(time / ranks[i]) / ranks[i];
if (totalCars >= cars) return 1;
}
return 0;
}
int minTimeRepairCars(int ranks[], int n, int cars) {
int low = 1, high = 1e9, result = 0;
while (low <= high) {
int mid = low + (high - low) / 2;
if (canRepair(ranks, n, cars, mid)) {
result = mid;
high = mid - 1;
} else {
low = mid + 1;
}
}
return result;
}
int main() {
int ranks[] = {4, 2, 3, 1};
int cars = 10;
int n = sizeof(ranks) / sizeof(ranks[0]);
printf("%d\n", minTimeRepairCars(ranks, n, cars));
return 0;
}using System;
class Program {
public static bool CanRepair(int[] ranks, int cars, int time) {
int totalCars = 0;
foreach (int rank in ranks) {
totalCars += time / (rank * rank);
if (totalCars >= cars) return true;
}
return false;
}
public static int MinTimeRepairCars(int[] ranks, int cars) {
int left = 1, right = (int)1e9;
while (left < right) {
int mid = (left + right) / 2;
if (CanRepair(ranks, cars, mid)) {
right = mid;
} else {
left = mid + 1;
}
}
return left;
}
public static void Main() {
int[] ranks = {4, 2, 3, 1};
int cars = 10;
Console.WriteLine(MinTimeRepairCars(ranks, cars));
}
}This Python code performs a binary search over time. It uses a helper function can_repair to verify if a given time allows for repairing all cars, adjusting the search boundaries accordingly.
Time Complexity: O(n * log(max_time)).
Space Complexity: O(1).
Approach 2: Greedy with Priority Queue
This approach uses a greedy algorithm with a priority queue (or a min-heap) to assign cars to mechanics such that the total time taken is minimized. The priority queue is used to always pick the mechanic who will complete their next car repair in the shortest time. This approach minimizes the overall time in a different manner compared to the binary search method.
import heapq
class Mechanic:
def __init__(self, rank):
self.rank = rank
self.time = 0
self.cars = 0
def repair_car(self):
self.cars += 1
self.time += self.rank * self.cars * self.cars
def __lt__(self, other):
return self.time < other.time
def min_time_repair_cars(ranks, cars):
pq = [Mechanic(rank) for rank in ranks]
heapq.heapify(pq)
for _ in range(cars):
m = heapq.heappop(pq)
m.repair_car()
heapq.heappush(pq, m)
return max(mechanic.time for mechanic in pq)
ranks = [4, 2, 3, 1]
cars = 10
print(min_time_repair_cars(ranks, cars))import java.util.PriorityQueue;
class Mechanic implements Comparable<Mechanic> {
int rank;
int time;
int cars;
Mechanic(int rank) {
this.rank = rank;
this.time = 0;
this.cars = 0;
}
void repairCar() {
cars++;
time += rank * cars * cars;
}
@Override
public int compareTo(Mechanic other) {
return Integer.compare(this.time, other.time);
}
}
public class MinimumTime {
public static int minTimeRepairCars(int[] ranks, int cars) {
PriorityQueue<Mechanic> pq = new PriorityQueue<>();
for (int rank : ranks) {
pq.add(new Mechanic(rank));
}
while (cars-- > 0) {
Mechanic m = pq.poll();
m.repairCar();
pq.add(m);
}
int max_time = 0;
for (Mechanic m : pq) {
max_time = Math.max(max_time, m.time);
}
return max_time;
}
public static void main(String[] args) {
int[] ranks = {4, 2, 3, 1};
int cars = 10;
System.out.println(minTimeRepairCars(ranks, cars));
}
}#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
class Mechanic {
public:
int rank;
int time;
int cars;
Mechanic(int r) : rank(r), time(0), cars(0) {}
void repairCar() {
time += rank * (cars + 1) * (cars + 1);
cars++;
}
bool operator<(const Mechanic& other) const {
return time > other.time;
}
};
int minTimeRepairCars(vector<int>& ranks, int cars) {
priority_queue<Mechanic> pq;
for (int rank : ranks) {
pq.emplace(rank);
}
while (cars--) {
Mechanic m = pq.top();
pq.pop();
m.repairCar();
pq.push(m);
}
int max_time = 0;
while (!pq.empty()) {
max_time = max(max_time, pq.top().time);
pq.pop();
}
return max_time;
}
int main() {
vector<int> ranks = {4, 2, 3, 1};
int cars = 10;
cout << minTimeRepairCars(ranks, cars) << endl;
return 0;
}In this Python solution, we employ a priority queue to efficiently track and manage the mechanics' workloads. By assigning cars to the mechanic who can complete their next car the quickest, we attempt to minimize the maximum completion time.
Time Complexity: O(cars * log(n)).
Space Complexity: O(n).
Approach 3: Binary Search
We notice that the longer the repair time, the more cars are repaired. Therefore, we can use the repair time as the target of binary search, and binary search for the minimum repair time.
We define the left and right boundaries of the binary search as left=0, right=ranks[0] times cars times cars. Next, we binary search for the repair time mid, and the number of cars each mechanic can repair is \lfloor \sqrt{\frac{mid}{r}} \rfloor, where \lfloor x \rfloor represents rounding down. If the number of cars repaired is greater than or equal to cars, it means that the repair time mid is feasible, we reduce the right boundary to mid, otherwise we increase the left boundary to mid+1.
Finally, we return the left boundary.
The time complexity is O(n times log M), and the space complexity is O(1). Here, n is the number of mechanics, and M is the upper bound of the binary search.
function repairCars(ranks: number[], cars: number): number {
let left = 0;
let right = ranks[0] * cars * cars;
while (left < right) {
const mid = left + Math.floor((right - left) / 2);
let cnt = 0;
for (const r of ranks) {
cnt += Math.floor(Math.sqrt(mid / r));
}
if (cnt >= cars) {
right = mid;
} else {
left = mid + 1;
}
}
return left;
}func repairCars(ranks []int, cars int) int64 {
return int64(sort.Search(ranks[0]*cars*cars, func(t int) bool {
cnt := 0
for _, r := range ranks {
cnt += int(math.Sqrt(float64(t / r)))
}
return cnt >= cars
}))
}Complexity comparison
| Approach | Complexity |
|---|---|
| Binary Search on Minimum Time | Time Complexity: |
| Greedy with Priority Queue | Time Complexity: |
| Binary Search | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Binary Search on Minimum Time | O(n log T) | O(1) | Best general solution when the answer space is monotonic and constraints are large |
| Greedy with Priority Queue | O(cars log n) | O(n) | Useful for simulation problems or when the number of tasks is relatively small |
Frequently asked questions
Is Minimum Time to Repair Cars easy or hard?
Minimum Time to Repair Cars is generally rated Medium difficulty. The challenge lies in recognizing that the problem should be solved using binary search on the answer rather than direct simulation.
Minimum Time to Repair Cars Python/Java solution
Most implementations use binary search combined with a helper function that computes repaired cars using sqrt(t / rank). The same logic works across Python, Java, C++, C#, and JavaScript with minor syntax differences.
How to solve Minimum Time to Repair Cars in O(n)?
An exact O(n) solution is not practical because the answer itself must be searched within a large time range. The best approach is binary search on time with O(n log T) complexity. Each iteration scans the mechanics array once to compute how many cars can be repaired within the candidate time.
What is the best approach for Minimum Time to Repair Cars?
Binary search on the answer (minimum time) is the most efficient approach. For a candidate time t, calculate how many cars each mechanic can repair using floor(sqrt(t / rank)). Summing across all mechanics determines if the target number of cars can be repaired. This runs in O(n log T) time with constant space.
Is Minimum Time to Repair Cars asked at Google/Amazon/Meta?
Binary search on answer problems like this frequently appear in interviews at companies such as Amazon, Google, and Meta. The pattern—searching the smallest feasible value with a monotonic check—is a common interview technique tested in system scheduling and optimization problems.
What data structure is used in Minimum Time to Repair Cars?
The optimal solution mainly relies on binary search and simple iteration over an array of ranks. An alternative implementation uses a priority queue (min-heap) to simulate repair completion order, which helps schedule the next available mechanic.
What is the time complexity of Minimum Time to Repair Cars?
The optimal solution uses binary search over the time range. Each check iterates through all mechanics, giving O(n) work per step, and binary search adds a log T factor where T is the maximum possible time. The overall complexity is O(n log T) with O(1) extra space.