Thanks so much for the excellent explanation of the problem. It really crystallized it for me. That being said, it seems there might be a bug in the code though. In the case where there are no collisions (i.e. no car catches up to another car), the resulting fleet count should be the total number of cars (since each individual car is a fleet), but based on this code, it will be 1. Disclaimer: I didn't actually run the code, but just from looking at it, "fleet_count" is initialized to zero and incremented only when there's a collision, and once again after exiting the "for" loop. Unless I’m missing something….
Keep it up! May I recommend you discuss the solution to the "Longest Substring with At Least K Repeating Characters" problem (lc #395)? Specifically, the sliding window approach, as the divide-and-conquer approach is trivial
Great explanation thanks!
Amazing explanation and so easy to understand.
Thanks so much for the excellent explanation of the problem. It really crystallized it for me. That being said, it seems there might be a bug in the code though. In the case where there are no collisions (i.e. no car catches up to another car), the resulting fleet count should be the total number of cars (since each individual car is a fleet), but based on this code, it will be 1. Disclaimer: I didn't actually run the code, but just from looking at it, "fleet_count" is initialized to zero and incremented only when there's a collision, and once again after exiting the "for" loop. Unless I’m missing something….
Keep it up! May I recommend you discuss the solution to the "Longest Substring with At Least K Repeating Characters" problem (lc #395)? Specifically, the sliding window approach, as the divide-and-conquer approach is trivial
Insane explanation thanks Brother 🎉
Super!!
I finally managed to make my own implementation in java with my limited programming knowledge haha
import java.util.Arrays;
public class CarFleet {
public static void main(String[] args) {
int carDistance = 12;
int[] carPositions = {2, 0, 4, 7};
int[] carSpeeds = {4, 1, 2, 1};
System.out.println(countCarFleets(carDistance, carPositions, carSpeeds)); // expected fleets: 2
}
public static int countCarFleets(int distance, int[] position, int[] speed) {
int countFleets = 0;
int[] carPositions = position.clone();
int[] carSpeeds = new int[speed.length];
Arrays.sort(carPositions);
for(int i = 0; i < carSpeeds.length; ++i)
{
int index = Arrays.binarySearch(carPositions, position[i]);
carSpeeds[index] = speed[i];
}
int timeFront = (distance - carPositions[carPositions.length - 1]) / carSpeeds[carSpeeds.length - 1];
for(int i = carSpeeds.length - 2; i > -1; --i)
{
int timeBack = (distance - carPositions[i]) / carSpeeds[i];
if(timeBack > timeFront)
{
++countFleets;
timeFront = timeBack;
}
}
return ++countFleets;
}
}