A ride-hailing dispatch queue is a singly linked list of fare amounts, in the order rides were requested. Partition the queue around a threshold fare p: all rides with fare STRICTLY LESS than p should come first, in their original relative order, followed by all rides with fare GREATER THAN OR EQUAL TO p, also in their original relative order. Print the resulting fares.
Line 1: an integer n — the number of rides.
Line 2: n space-separated integers — the fares, in request order.
Line 3: an integer p — the threshold fare.
n space-separated integers: the fares below p (in order) followed by the fares at least p (in order).
Example 1
Input
6 5 1 8 3 9 2 4
Expected
1 3 2 5 8 9
Explanation
Fares below 4 in order are 1,3,2; fares at least 4 in order are 5,8,9: result 1 3 2 5 8 9.
Example 2
Input
4 10 20 30 40 100
Expected
10 20 30 40
Explanation
All fares are below the threshold 100, so nothing moves: 10 20 30 40.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →