Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Problem Statement
2.1.
Example
3.
Stack Approach
3.1.
Algorithm
3.2.
DRY Run
3.3.
Implementation in C++
3.4.
Implementation in Python
3.5.
Time Complexity
3.6.
Space Complexity
4.
Map Approach
4.1.
Algorithm
4.2.
DRY Run
4.3.
Implementation in C++
4.4.
Implementation in Python
4.5.
Time Complexity
4.6.
Space Complexity
5.
Frequently Asked Questions
5.1.
What is a map?
5.2.
What is the formula to calculate time?
5.3.
Why are we using the double data type to store the time?
5.4.
What is a vector?
5.5.
How to store key-value pairs in python?
6.
Conclusion
Last Updated: Mar 27, 2024
Medium

Car Fleet

Master Python: Predicting weather forecasts
Speaker
Ashwin Goyal
Product Manager @

Introduction

Solving good programming questions where you need to think of logic will help you to become an excellent programmer. Solving these problems gives you a better edge during the coding interviews.

introduction image

In this blog, we will discuss the car fleet problem, one of the problems where you need to think of logic. The car fleet problem is a famous problem on various coding platforms, and you might have to face this problem in a coding round.

Problem Statement

There will be N number of cars reaching a target destination on a single-lane road. As input, you will have two arrays of N size, position[N] and speed[N], and the target value to complete the destination.

Each car position will be unique, and the value at speed[i] will be the car's speed at position[i]. Since they are on a single-lane road, the car which is faster than the car ahead of it cannot overtake each other. If a car is faster than the car ahead of it, the faster car will match the speed of the slower car and drive bumper to bumper to it. At this time, the positions of the cars will be considered the same.

For example, Suppose car 2 is moving at 10 km/h, and car 3 is moving at 2 km/h. They need to cover a very large distance. At some time during the destination, car2 will catch up to car3 and then travel together until the destination.

example image

Our task is to find the number of car fleets reaching the destination. A car fleet is a group of cars at the same speed and driving at the same position.

A single car can be considered a car fleet, and if the car reaches at the same time as a car fleet, it will be one car fleet.

Example

Input

input image

Explanation

From the above input, first, we will calculate the time taken by the car at position 2, which is 6. This can be calculated from the formula: Time Taken = (Target - Position)/Speed.
Therefore, time = (20-2)/3 = 18/3 = 6.

Then we will calculate the time taken by the car at position 4, which is 16. Now at position 6, the time taken is 7.

After comparing at all 3 positions, we can conclude that cars at positions 2 and 4 will make a fleet and reach the target together. The car at position 6 will target alone, which means, according to the statement, it will consider a separate fleet. The above code will give us two fleets.

Output

The number of car fleets that will reach the destination is 2.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

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

approach 1 dry run

 

approach 1 dry run
approach 1 dry run
approach 1 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;
}


Output

c++ 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)


Output

python 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

approach 2 dry run
approach 2 dry run
approach 2 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;
}


Output

c++ 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)


Output

python 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.

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!

Previous article
Find All Occurrences of the Pattern in the String
Next article
Count Palindromes
Live masterclass