Given an array speed[] of size N denoting the speed of N cars moving on an infinitely long single lane road (i.e. no overtaking is allowed) from left to right. Initially, the rightmost car is at the first position and whenever a car with higher speed reaches a car with lower speed they start moving with the speed to the slower car and form a cluster. The task is to find the total number of clusters that will form.
Note: A single car is also considered a cluster.
Examples:
Input: speed[] = {1, 4, 5, 2, 17, 4 }
Output: 3
Explanation: After a certain time, car with speed 17 will reach car with speed 4(car5) and will form a cluster.
And similarly, cars with speed 4 and 5 will start moving with speed 2 on reaching car3.
The clusters will be (car0), (car1, car2, car3), (car4, car5).Input: speed[] = {2, 3, 4, 7, 7}
Output: 5
Explanation: Each car will form a cluster.
Approach: The solution is based on greedy approach. Here, a car with less speed forms a cluster with all the cars behind it and having speeds greater than itself. Follow the steps below to solve the problem:
- Start iterating from the last index of array speed[].
- Store the speed of the car in a variable, say currentCar.
- A cluster is formed till the speed of cars behind the currentCar is greater than itself. Therefore increase the value of clusters as soon as a car with less speed is found behind it or when the array is out of bounds.
Below is the implementation of the above approach.
C++
// C++ code to implement above approach#include <bits/stdc++.h>#include <vector>using namespace std;// Function to count total number of clustersint countClusters(vector<int>& speed){ int N = speed.size(); // For number of clusters int cluster = 0; for (int i = N - 1; i >= 0; i--) { int currentCar = speed[i]; // comparing with previous car while (i != 0 and speed[i - 1] > currentCar) { i--; } cluster++; } return cluster;}// Driver codeint main(){ vector<int> speed = { 1, 4, 5, 2, 17, 4 }; int clusters = countClusters(speed); cout << clusters; return 0;} |
Java
// Java program to implement// the above approachimport java.io.*;class GFG{ // Function to count total number of clusters static int countClusters(int []speed) { int N = speed.length; // For number of clusters int cluster = 0; for (int i = N - 1; i >= 0; i--) { int currentCar = speed[i]; // comparing with previous car while (i != 0 && speed[i - 1] > currentCar) { i--; } cluster++; } return cluster; } // Driver Code public static void main(String args[]) { int []speed = { 1, 4, 5, 2, 17, 4 }; int clusters = countClusters(speed); System.out.println(clusters); }}// This code is contributed by Saurabh Jaiswal |
Python3
# Python code to implement above approach# Function to count total number of clustersdef countClusters(speed): N = len(speed) clusters = 0 i = N-1 while(i >= 0): currentCar = speed[i] while(i != 0 and speed[i-1] > currentCar): i = i-1 clusters = clusters+1 i = i-1 return clusters# Driver codeif __name__ == '__main__': speed = [1, 4, 5, 2, 17, 4] clusters = countClusters(speed) print(clusters) |
C#
// C# program to implement// the above approachusing System;class GFG{ // Function to count total number of clusters static int countClusters(int []speed) { int N = speed.Length; // For number of clusters int cluster = 0; for (int i = N - 1; i >= 0; i--) { int currentCar = speed[i]; // comparing with previous car while (i != 0 && speed[i - 1] > currentCar) { i--; } cluster++; } return cluster; } // Driver Code public static void Main() { int []speed = { 1, 4, 5, 2, 17, 4 }; int clusters = countClusters(speed); Console.Write(clusters); }}// This code is contributed by Samim Hossain Mondal. |
Javascript
<script> // JavaScript code for the above approach // Function to count total number of clusters function countClusters(speed) { let N = speed.length; // For number of clusters let cluster = 0; for (let i = N - 1; i >= 0; i--) { let currentCar = speed[i]; // comparing with previous car while (i != 0 && speed[i - 1] > currentCar) { i--; } cluster++; } return cluster; } // Driver code let speed = [1, 4, 5, 2, 17, 4]; let clusters = countClusters(speed); document.write(clusters); // This code is contributed by Potta Lokesh </script> |
3
Time Complexity: O(N)
Auxiliary Space: O(1)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
