Water Droplet Mixing

Easy
0/40
Average time to solve is 28m
profile
Contributed by
5 upvotes
Asked in companies
AdobeShareChatSprinklr

Problem statement

Consider a pipe of length L. The pipe has N water droplets at N different positions within it. Each water droplet is moving towards the end of the pipe (x = L) at different speeds. When a water droplet mixes with another water droplet, it assumes the speed of the water droplet it is mixing with, or to put it in other words, the water resulting water droplet formed post mixing will take the speed of the smaller ones.

Determine the number of droplets that come out of the pipe.

Detailed explanation ( Input/output format, Notes, Images )
Input format : 
The first line contains an integer 't' which denotes the number of test cases or queries to be run. Then the test cases follow.

The first line of each test case or query contains two integers(N and L) separated by a single space. Where 'N' represents the number of water droplets present in the pipe initially and 'L' represents the length of the pipe.

The second line contains 'N' single space-separated integers representing the positions of the droplets initially.

The third line contains 'N' single space-separated integers representing the velocities of the droplets initially.
Output Format : 
For each test case, return the number of water droplets that come out of the pipe.

Output for every test case will be printed in a separate line.
Note: 
The positions of all the droplets are unique in that is no water droplet will have the same initial position.

You do not need to print anything, it has already been taken care of.
Constraints : 
1 <= t <= 100
0 <= N <= 10^5
1 <= L <= 10^9
0 <= Position[i] <= L
1 <= Speed[i] <= 10^9

Time Limit: 1 sec
Sample Input 1 :
1
5 12
10 8 0 5 3
2 4 1 1 3
Sample Output 1 :
3
Sample Input 2 :
1
2 5
0 1
1 1
Sample Output 2 :
2
Hint

Can we optimize search for the first two minimum positions?

Approaches (1)
Minimum Position Approach

We can solve this problem by calculating the time required by each drop to reach the end of the pipe and comparing them based on their position in the pipe and the time required to reach the end.

 

  • Calculate the time required by each drop to reach the end of the pipe in fraction format (storing a pair of numerator and denominator) to eliminate the risk of the precision issue in different programming languages.
  • Now make a pair of positions and times and sort them according to the position.
  • Now say there are two drops i and j such that i < j,  if the time required by drop ‘i’ is less than equal to the time required by drop ‘j’ then it will get merged in drop j and will come out with drop ‘j’.
  • Now make a stack to store the time of each drop moving separately and the ans will be the size of the stack in the end.
  • Iterate from i  = 0  to i = n-1. For each drop ‘i’, check with drops stored in the stack that if they are merging with ‘i’th drop or not.
  • While the stack is not empty and drops on the top of the stack are merging with the drop ‘i' keep poping.
  • Push the ‘i’ drop in the stack.
  • Return the size of the stack.

 

We can observe all the drops before a slower drop will mix with it. And all the drops after the slower drop mix with the next slower drop and so on.

 

For example, if the times to reach the end are - 12, 3, 7, 8, 1 (sorted according to positions)
 

  • 0th drop is slowest, it won’t mix with the next drop
  • The 1st drop is faster than the 2nd drop so they will mix and the 2nd drop is faster than the 3rd drop so all three will mix together.
  • They cannot mix with the 4th drop because it is faster.
  • So we used a stack to maintain the time of drops in increasing order to check efficiently for every next drop.
Time Complexity

O(N * log(N)), Where N is the total number of droplets.

 

N operations to make a list of pairs where each pair contains the position of every droplet and its respective time to reach the destination.

 

Then N * log(N) operations to sort the list of pairs on the basis of positions.

 

N operations to figure out which all drops mix together, and which all don't. We used a stack for this.

Space Complexity

O(N), Where N is the total number of droplets.


As we have a list of pairs of size N where each pair contains the position of every droplet and its respective time to reach the destination.

Code Solution
(100% EXP penalty)
Water Droplet Mixing
Full screen
Console