Car Fleet
Car Fleet Problem – Medium Level Problem
You are given n cars traveling on a one-lane highway toward the same destination.
You have two integer arrays, position and speed, both of length n:
- position[i] represents the current position (in miles) of the i-th car.
- speed[i] represents the speed (in miles per hour) of the i-th car.
The destination is at target miles.
Cars cannot overtake each other on this road. If a faster car catches up to a slower car ahead, it will match the slower car’s speed, and they will form a car fleet (a group of cars traveling together at the same speed). A single car by itself is also considered a fleet.
If a car catches up to a fleet right as the fleet reaches the destination, that car is counted as part of the same fleet.
Your task is to return the total number of car fleets that will arrive at the destination.
Output: 1
Explanation: The cars starting at 1 (speed 3) and 4 (speed 2) become a fleet, meeting each other at 10, the destination.
Output: 3
Explanation: The cars starting at 4 and 7 become a fleet at position 10. The cars starting at 1 and 0 never catch up to the car ahead of them. Thus, there are 3 car fleets that will arrive at the destination.
Constraints:
- n == position.length == speed.length.
- 1 <= n <= 1000
- 0 < target <= 1000
- 0 < speed[i] <= 100
- 0 <= position[i] < target
- All the values of position are unique.
Car Fleet Solution
Recommendation for Time and Space Complexity –You should aim for a solution with O(nlogn) time and O(n) space, where n is the size of the input array.
Hints for solving problems
Hint 1 :
First draw a picture of all the points which represents the positions and respective speeds of the cars. It is appropriate to represent the position and speed of each car as an array, where each cell corresponds to a car. It is also logical to sort this array based on the positions in descending order. Why?
Hint 2 :
Because a car can only form a fleet with another car that is ahead of it, sorting the array in descending order ensures clarity about the final speed of each car. Sorting in ascending order would create ambiguity, as the next car might form a fleet with another car while reaching the target, making it difficult to determine its final speed.
Hint 3 :
Calculating the time for a car to reach the target is straightforward and can be done using the formula: time = (target – position) / speed. Now, it becomes easy to identify that two cars will form a fleet if and only if the car ahead has a time that is greater than or equal to the time of the car behind it. How can we maintain the total number of fleets happened while going through the array? Maybe a data structure is helpful.
Hint 4 :
We can use a stack to maintain the times of the fleets. As we iterate through the array (sorted in descending order of positions), we compute the time for each car to reach the target and check if it can form a fleet with the car ahead. If the current car’s time is less than or equal to the top of the stack, it joins the same fleet. Otherwise, it forms a new fleet, and we push its time onto the stack. The length of the stack at the end represents the total number of fleets formed.
There are mainly 2 approach to solve this problem-
- Stack Method
- Iteration Method
1. Stack Method
In this approach, cars are sorted based on their starting positions, and a stack is used to keep track of arrival times. If a car reaches the destination later than the car before it (top of the stack), they form a fleet and merge.
- Time complexity: O(n logn)
- Space complexity: O(n)
Code
class Solution {
public:
int carFleet(int target, vector& position, vector& speed) {
vector> pair;
for (int i = 0; i < position.size(); i++) {
pair.push_back({position[i], speed[i]});
}
sort(pair.rbegin(), pair.rend());
vector stack;
for (auto& p : pair) {
stack.push_back((double)(target - p.first) / p.second);
if (stack.size() >= 2 &&
stack.back() <= stack[stack.size() - 2])
{
stack.pop_back();
}
}
return stack.size();
}
};
public class Solution {
public int carFleet(int target, int[] position, int[] speed) {
int[][] pair = new int[position.length][2];
for (int i = 0; i < position.length; i++) {
pair[i][0] = position[i];
pair[i][1] = speed[i];
}
Arrays.sort(pair, (a, b) -> Integer.compare(b[0], a[0]));
Stack stack = new Stack<>();
for (int[] p : pair) {
stack.push((double) (target - p[0]) / p[1]);
if (stack.size() >= 2 &&
stack.peek() <= stack.get(stack.size() - 2))
{
stack.pop();
}
}
return stack.size();
}
}
class Solution:
def carFleet(self, target: int, position: List[int], speed: List[int]) -> int:
pair = [(p, s) for p, s in zip(position, speed)]
pair.sort(reverse=True)
stack = []
for p, s in pair: # Reverse Sorted Order
stack.append((target - p) / s)
if len(stack) >= 2 and stack[-1] <= stack[-2]:
stack.pop()
return len(stack)
class Solution {
/**
* @param {number} target
* @param {number[]} position
* @param {number[]} speed
* @return {number}
*/
carFleet(target, position, speed) {
let pair = position.map((p, i) => [p, speed[i]]);
pair.sort((a, b) => b[0] - a[0]);
let stack = [];
for (let [p, s] of pair) {
stack.push((target - p) / s);
if (stack.length >= 2 &&
stack[stack.length - 1] <= stack[stack.length - 2])
{
stack.pop();
}
}
return stack.length;
}
}
2. Iteration Method
Cars are sorted by position, and we iterate from right to left, calculating the time each car takes to reach the destination. A fleet is formed if the current car takes longer than or equal to the previous car.
- Time complexity: O(n logn)
- Space complexity: O(n)
Code
class Solution {
public:
int carFleet(int target, vector& position, vector<int>& speed) {
int n = position.size();
vector<pair<int, int>> pair;
for (int i = 0; i < n; i++) {
pair.push_back({position[i], speed[i]});
}
sort(pair.rbegin(), pair.rend());
int fleets = 1;
double prevTime = (double)(target - pair[0].first) / pair[0].second;
for (int i = 1; i < n; i++) { double currTime = (double)(target - pair[i].first) / pair[i].second; if (currTime > prevTime) {
fleets++;
prevTime = currTime;
}
}
return fleets;
}
};
public class Solution {
public int carFleet(int target, int[] position, int[] speed) {
int n = position.length;
int[][] pair = new int[n][2];
for (int i = 0; i < n; i++) {
pair[i][0] = position[i];
pair[i][1] = speed[i];
}
Arrays.sort(pair, (a, b) -> Integer.compare(b[0], a[0]));
int fleets = 1;
double prevTime = (double)(target - pair[0][0]) / pair[0][1];
for (int i = 1; i < n; i++) {
double currTime = (double)(target - pair[i][0]) / pair[i][1];
if (currTime > prevTime) {
fleets++;
prevTime = currTime;
}
}
return fleets;
}
}
class Solution:
def carFleet(self, target: int, position: List[int], speed: List[int]) -> int:
pair = [(p, s) for p, s in zip(position, speed)]
pair.sort(reverse=True)
fleets = 1
prevTime = (target - pair[0][0]) / pair[0][1]
for i in range(1, len(pair)):
currCar = pair[i]
currTime = (target - currCar[0]) / currCar[1]
if currTime > prevTime:
fleets += 1
prevTime = currTime
return fleets
class Solution {
/**
* @param {number} target
* @param {number[]} position
* @param {number[]} speed
* @return {number}
*/
carFleet(target, position, speed) {
let pair = position.map((p, i) => [p, speed[i]]);
pair.sort((a, b) => b[0] - a[0]);
let fleets = 1;
let prevTime = (target - pair[0][0]) / pair[0][1];
for (let i = 1; i < pair.length; i++) {
let currTime = (target - pair[i][0]) / pair[i][1];
if (currTime > prevTime) {
fleets++;
prevTime = currTime;
}
}
return fleets;
}
}
