Car Fleet

Stack Approach

Now that we have discussed the car fleet problem statement, let's discuss the solution. This is the first approach to tackling the problem. To solve this problem in general, there is only one thing you need to find out. 

You need to calculate the time taken by the cars to reach the destination. If the time taken by car2 is smaller than or equal to that of the previous car1, then car2 will join car1 and make a fleet to reach the destination.

To calculate the time, we need to subtract the car's current position from the target value and divide it by its speed. Time_taken = (target_value - position)/speed is the formula. We will also use a stack to store the valid car fleet, and the stack's size will be our answer.

You must observe that only a consecutive group of cars can make a car fleet. So car fleet is a list of consecutive cars. For example, If a car fleet consists of cars 3, 4, and 5, a car1 can only be a part of it if car 2 is also in the fleet.

We can make the pair of both position and speed array, then we will sort the pair with respect to the position, and then we can perform the operations to find out the time for each car and compare the current and previous car's time and check if they can make a fleet or not. Keep in mind that we will traverse the elements with the largest value because it is the closest position to the target value, and it will decide that can we make a fleet or not.

Algorithm

1. Initialize a stack to store the time taken by each car.
    
2. Sort the arrays in descending order with respect to the position array.
    
3. Calculate the time taken by each car by the formula.
    
4. Make a pair vector of position and speed vector and store the pair vector.
    
5. If the stack is empty, push the time taken by the car with the closest position to the target value.
    
6. If the current car time taken is greater than the top of the stack, then push it into the stack.
    
7. Repeat steps 3,4,5 until all positions are traversed.
    
8. In the end, return the size of the stack.

DRY Run

The size of the stack is 2, and this is our answer. The maximum of car fleets that will reach the destination will be 2.

Implementation in C++

#include<bits/stdc++.h>
using namespace std;

// Function to Calculate the number of fleets.
int fleetofcars(int target, vector < int > & position, vector < int > & speed) {
    // Intailizing the pair vector time.
    vector < pair < int, int >> time;
    // Intailizing the stack fleet.
    stack < double > fleet;
  
    // Adding the values in the time vector
    for (int i = 0; i < position.size(); i++) {
        time.push_back({
        position[i],
        speed[i]
        });
    }
  
    // Sorting the time vector with respect to positions.
    sort(time.begin(), time.end());
  
    // Calculating the maximum number of fleets.
    for (int i = position.size() - 1; i >= 0; i--) {
        double timetaken = double(target - time[i].first) / time[i].second;
        if (fleet.empty()) {
            fleet.push(timetaken);
        } else {
            if (fleet.top() < timetaken) {
                fleet.push(timetaken);
            }
        }
    }
    return fleet.size();
}

int main() {
    int target = 20;
    vector < int > position;
    vector < int > speed;

    position.push_back(2);
    position.push_back(6);
    position.push_back(4);

    speed.push_back(3);
    speed.push_back(2);
    speed.push_back(1);

    int res = fleetofcars(target, position, speed);
    cout << "The number of car fleets that will reach the destination is " << res;
}

You can also try this code with Online C++ Compiler

Run Code

Output

Implementation in Python

# Function to calculate the number of fleets
def fleetofcar(target, position, speed):
    # Intializing the stack.
    stack = []
    
    # Sorting the position and speed and calculating
    # the number of fleets and adding in the stack.
    for posvar, speedvar in sorted(zip(position, speed))[::-1]:
        timetaken = (target - posvar)/float(speedvar)
        if not stack:
            stack.append(timetaken)
        elif timetaken > stack[-1]:
            stack.append(timetaken)
    
    # Returning the lenght of the stack.
    return len(stack)

if __name__ == "__main__":
    target = 20
    position = [2,6,4]
    speed = [3,2,1]
    
    res = fleetofcar(target,position,speed)
    print("The number of car fleets that will reach the destination is",res)

You can also try this code with Online Python Compiler

Run Code

Output

Time Complexity

O(N*log(N)), where ‘N’ is the number of cars on the highway.

We are sorting the size 'N' vector, which takes N*log(N) time. And looping through the vector once takes O(N). So Time Complexity = O(N*log(N)) +O(N) = O(N*log(N)).

Space Complexity

O(N), where ‘N’ is the number of cars on the highway. Since we are creating a vector of size ‘N.’

Also see, Morris Traversal for Inorder and Rabin Karp Algorithm

Map Approach

We will implement the above-discussed approach using maps in this approach. The map is used in this approach because it will automatically sort the time taken by each car with respect to the key. So that we do not have to sort the vectors again.

Algorithm

1. Initialize a map with <int, double> values.
    
2. Insert the elements in the map where the key is the position, and the value is the time taken to reach the destination.
    
3. Since the map elements are sorted by keys, we don't have to explicitly sort the elements.
    
4. Next, we loop through the map elements and see if the CURRENT_CAR time is greater than PREVIOUS_TIME. Then, we know this car will start a new car fleet, so we increment the COUNT_OF_FLEET by one and update the PREVIOUS_TIME to the time taken by this fleet.
    
5. Return the total number of car fleets.

DRY Run

Implementation in C++

#include<bits/stdc++.h>
using namespace std;

// Function to Calculate the number of fleets.
int countCarFleets(int target, vector < int > position, vector < int > speed) {
    int n = position.size();
  
    // Intializing the map.
    map < int, double > mp;
  
    // Adding the values in the map
    for (int i = 0; i < n; i++) {
        mp[-position[i]] = double(target - position[i]) / speed[i];
    }

    int countOfFleet = 0;
    double previousTime = INT_MIN;
  
    // Calculating the maximum number of bridges.
    for (auto currCar: mp) {
        if (currCar.second > previousTime) {
            previousTime = currCar.second;
            countOfFleet++;
        }
    }
    return countOfFleet;
}

int main() {
    int destination = 20;
    vector < int > position;
    vector < int > speed;

    position.push_back(2);
    position.push_back(6);
    position.push_back(4);

    speed.push_back(3);
    speed.push_back(2);
    speed.push_back(1);

    int res = countCarFleets(destination, position, speed);
    cout << "The number of car fleets that will reach the destination is " << res;
    return 0;
}

You can also try this code with Online C++ Compiler

Run Code

Output

Implementation in Python

import sys
# Function to calculate the number of fleets
def fleetofcar(target, position, speed):
    # Intializing a dictionary
    dictmap = {}
    
    # Calculating the time taken and adding in the dictmap.
    for i in range(len(position)):
        dictmap[-position[i]] = (target - position[i])/float(speed[i])	
    
    # Declaring the counterfleet and prevtime variable.
    counterfleet = 0
    
    # Intializing the prevtime with minimum integer value.
    prevtime = -sys.maxsize - 1
    
    # Calculating the maximum fleets.
    for m,n in sorted(dictmap.items()):
        if(n > prevtime):
            prevtime = n
            counterfleet +=1
            
    return counterfleet

if __name__ == "__main__":
    target = 20
    position = [2,6,4]
    speed = [3,2,1]
    
    res = fleetofcar(target,position,speed)
    print("The number of car fleets that will reach the destination is",res)

You can also try this code with Online Python Compiler

Run Code

Output

Time Complexity

O(N*log(N)), where ‘N’ is the number of cars on the highway. Since inserting in a map takes log(N) time, we are inserting ‘N’ elements.

Space Complexity

O(N), where ‘N’ is the number of cars on the highway. Since we are creating a map of size ‘N’.

Check out this problem - Check If A String Is Palindrome

Frequently Asked Questions

What is a map?

A map is one of the data structures which allows us to store the data in the form of key-value pair.

What is the formula to calculate time?

The formula to calculate time is distance/speed.

Why are we using the double data type to store the time?

We are using the double because it will give us more precise results than the integer value.

What is a vector?

Vector stores the elements with similar data types like an array, but it can grow dynamically, unlike an array in size.

How to store key-value pairs in python?

We have to use the dictionary in python to implement the key-value pairs property of the map.

Conclusion

In this blog, we have discussed the car fleet problem and implemented the problem in two different approaches. To learn more programming problems check out the following links.

• Vertex Cover Problem
• Channel Assignment Problem
• Matrix probability problem
• The Stable Marriage Problem
   

To learn more about DSA, competitive coding, and many more knowledgeable topics, please look into the guided paths on Coding Ninjas Studio. Also, you can enroll in our courses and check out the mock test and problems available to you. Please check out our interview experiences and interview bundle for placement preparations.

Happy Coding!