LC 853. Car Fleet

The problem

Solution - $O(n \log n)$ Time

Once again, I got close to a solution but didn't fully catch the trick of the problem without a tip. Given my 20-minute time limit, I stopped and looked into a tutorial that had a slightly different approach. What will help for stack problems in the future is if I can better recognize when to use increasing or decreasing for my application.

Here, by creating an increasing stack and looping through the cars in descending position, fleets can be found by pushing longer timeToTargets to the increasing stack. If the timeToTarget is longer than a car in a previous position, it can be added to the stack of fleets because it is impossible for the car to catch up to the next group.

function carFleet(target: number, position: number[], speed: number[]): number {
  let stack = []
  let sortedCars = position
    .map((_, idx) => {
      return {
        position: position[idx],
        speed: speed[idx],
        timeToTarget: (target - position[idx]) / speed[idx],
      }
    })
    .sort((a, b) => b.position - a.position)

  for (let i = 0; i < sortedCars.length; i++) {
    if (!stack.length || sortedCars[i].timeToTarget > stack[stack.length - 1]) {
      stack.push(sortedCars[i].timeToTarget)
    }
  }

  return stack.length
}