Bubble sort sorts a list by repeatedly swapping neighbours that are in the wrong order. Return how many swaps bubble sort would make to sort nums from smallest to largest. Equal numbers are never swapped.
countSwaps([3, 1, 2]) returns 2: swap 3 and 1, then swap 3 and 2.
The catch: the hidden tests use lists of 20,000 numbers, and really running bubble sort on those is far too slow. Find a faster way to count. Hint: every swap fixes exactly one pair of positions i < j where nums[i] > nums[j]. How could merge sort count those pairs while it sorts?
nums has up to 20,000 numbers between -100,000 and 100,000. The count is returned as a long, because on longer lists it can grow past what an int holds.
Input: countSwaps([3, 1, 2])
Output: 2
Input: countSwaps([1, 2, 3, 4])
Output: 0
Input: countSwaps([5, 4, 3, 2, 1])
Output: 10
Your solution is checked against 3 example tests and 8 hidden tests (edge cases and bigger inputs).
Languages you don't learn in class are worth more: C++ 1.25×, JavaScript, TypeScript, C, Rust and Go 1.5×. Your first solve in a language unlocks its "Learned" achievement: +25 for learning it.
Loading editor...
Run Code checks the example tests. Submit runs every test, including hidden ones.