How Messy Is the Shelf
A library volunteer tidies shelves by one rule: she only ever swaps two books that stand next to each other. Each book has a call number, and the shelf is tidy when the numbers read in non-decreasing order from left to right. A library may own several copies of a book, so numbers can repeat.
Before she starts on a long shelf, the head librarian wants to know how many swaps the job will take. Call a pair of books out of order when the left one has a larger number than the right one. A useful neighbour swap fixes exactly one such pair and breaks none, so the job takes exactly as many swaps as there are out-of-order pairs.
Your task
Write countOutOfOrder(callNumbers). Return the number of index pairs i < j with callNumbers[i] > callNumbers[j]. Equal numbers are not out of order. An empty shelf returns 0.
Aim for O(n log n). With 50,000 books, checking every pair is too slow.
countOutOfOrder(callNumbers: int[]) → int
Examples
callNumbers = [112, 108, 130, 125, 101]
6
The out-of-order pairs are (112, 108), (112, 101), (108, 101), (130, 125), (130, 101) and (125, 101). Six pairs, so six neighbour swaps.
callNumbers = [205, 205, 199, 210]
2
Each 205 sits left of the smaller 199: two pairs. The two copies of 205 are equal, so they do not count, and 210 is already where it belongs.
Constraints
- 0 ≤ callNumbers.length ≤ 50,000
- 1 ≤ callNumbers[i] ≤ 1,000,000
- The answer fits in a normal integer (at most about 1.25 billion).
Start with brute force
Check every pair i < j and count those with the left number larger. Simple and correct.
That is about n²/2 comparisons: 1.25 billion for 50,000 books. Simulating the volunteer's swaps (bubble sort) is just as slow, because a badly mixed shelf really does need that many swaps; you want to count them without doing them.
Hints
0 of 4 shown- Hint 1
Suppose the left half of the shelf and the right half are each already sorted, like
[108, 112]and[101, 125, 130]. How many left-half books are bigger than 101? Can you see it without comparing 101 to each one? - Hint 2
Because the left half is sorted, once one left book is bigger than 101, every book after it in the left half is bigger too. So one comparison can count a whole block of pairs at once.
- Hint 3
That is exactly the moment in merge sort's merge step when a book from the right half is taken before the remaining left-half books. How many left books are still waiting at that moment?
- Hint 4
Run merge sort and return a count along with the sorted half. Total = pairs inside the left half + pairs inside the right half + pairs across the halves. While merging, every time you take from the right (only when strictly smaller), add the number of items left in the left half. Take from the left on ties so equal books are not counted.
Walkthrough and solution
Unlocks when you pass every test. Stuck for a while? Looking is fine too, as long as you then close it and write the code yourself.
How to solve it
Every out-of-order pair is either inside the left half, inside the right half, or has one book in each half. Merge sort already handles the first two by recursion. The cross pairs are counted for free during the merge, because both halves are sorted by then.
Trace [112, 108, 130, 125, 101]. Split into [112, 108] and [130, 125, 101].
- Left half:
[112]and[108]. Merging, 108 is taken from the right while 112 waits: +1. Result[108, 112], 1 pair. - Right half: first
[125]and[101]give +1 and[101, 125]. Then merge[130]with[101, 125]: 101 is taken while 130 waits (+1), then 125 is taken while 130 still waits (+1). Result[101, 125, 130], 3 pairs. - Top merge of
[108, 112]and[101, 125, 130]: 101 is taken first while 108 and 112 both wait: +2 in one step. Then 108, 112, 125, 130 come out with no more right-before-left moments. - Total: 1 + 3 + 2 = 6.
Step 3 is the whole trick: one comparison counted two pairs, because a sorted left half means everything after 108 is at least 108. Two details matter. Add mid - i (all waiting left books), not 1. And on a tie take from the left, so equal call numbers never count.
function countOutOfOrder(callNumbers) {
const a = callNumbers.slice();
const tmp = new Array(a.length);
// sorts a[lo..hi) and returns the out-of-order pairs inside it
const sortCount = (lo, hi) => {
if (hi - lo < 2) return 0;
const mid = Math.floor((lo + hi) / 2);
let count = sortCount(lo, mid) + sortCount(mid, hi);
let i = lo, j = mid, k = lo;
while (i < mid && j < hi) {
if (a[i] <= a[j]) tmp[k++] = a[i++]; // ties go left: not out of order
else {
count += mid - i; // a[j] is smaller than every left book still waiting
tmp[k++] = a[j++];
}
}
while (i < mid) tmp[k++] = a[i++];
while (j < hi) tmp[k++] = a[j++];
for (let t = lo; t < hi; t++) a[t] = tmp[t];
return count;
};
return sortCount(0, a.length);
}def count_out_of_order(call_numbers):
# returns (sorted copy of books, out-of-order pairs inside it)
def sort_count(books):
if len(books) < 2:
return books, 0
mid = len(books) // 2
left, count_left = sort_count(books[:mid])
right, count_right = sort_count(books[mid:])
count = count_left + count_right
merged, i, j = [], 0, 0
while i < len(left) and j < len(right):
if left[i] <= right[j]: # ties go left: not out of order
merged.append(left[i])
i += 1
else:
count += len(left) - i # right[j] is smaller than every left book still waiting
merged.append(right[j])
j += 1
merged.extend(left[i:])
merged.extend(right[j:])
return merged, count
return sort_count(call_numbers)[1]Run your code to see results here. Run checks the examples. Submit checks every test, including hidden edge cases.