Loading page…
Practice problem · medium
A chat app gives every message a send number: 1 for the first message sent, 2 for the next, and so on. Messages can reach a phone in a different order from the one they were sent in.
You get the send numbers in the order the messages arrived. A pair is out of order when the message that arrived first has a larger send number than the one that arrived later. Support counts these pairs to measure how scrambled a connection is.
Write out_of_order_pairs(seqs).
seqs[i] is the send number of the i-th message to arrive. Numbers can repeat.i < j with seqs[i] > seqs[j].Input: seqs = [2, 4, 1, 3]
Output: 3The out-of-order pairs are (2, 1), (4, 1) and (4, 3). Merge sort finds them by counting as it merges two sorted halves, [2, 4] and [1, 3].
| Step | Left waiting | Right waiting | Taken | Pairs added | Total |
|---|---|---|---|---|---|
| 1 | [2, 4] | [1, 3] | 1 from the right | 2 | 2 |
| 2 | [2, 4] | [3] | 2 from the left | 0 | 2 |
| 3 | [4] | [3] | 3 from the right | 1 | 3 |
| 4 | [4] | [] | 4 from the left | 0 | 3 |
The total is 3.
Input: seqs = [5, 5, 5]
Output: 0Equal send numbers are not out of order.
Input: seqs = [3, 2, 1]
Output: 3Every pair is out of order: (3, 2), (3, 1) and (2, 1).
0 ≤ seqs.length ≤ 100,000 (messages)1 ≤ seqs[i] ≤ 1,000,000,000Checking every pair costs about n × n / 2, which is 5 × 10^9 at n = 100,000. Merge sort costs about n log n, roughly 1.7 million steps. The count itself can reach 5 × 10^9, so use a 64-bit integer.
out_of_order_pairs · runs in your browserCoding is easiest on a laptop. On a phone, read, trace and try small edits.