Only Neighbour Inversions?
MediumSorting & Searching
Problem
Runners finish a race and their bib numbers are recorded in finishing order as order, a permutation of 0..n-1. A swap is any pair of positions i < j with order[i] > order[j]; a neighbour swap is such a pair with j = i + 1.
Return true if the number of swaps equals the number of neighbour swaps, that is, every out-of-order pair is adjacent. Return false otherwise.
Example 1
- Input:
- order = [1, 0, 2]
- Output:
- true
The only swap is (1, 0), and those two runners are neighbours.
Example 2
- Input:
- order = [1, 2, 0]
- Output:
- false
Swaps: (1, 0) and (2, 0), but only (2, 0) is a neighbour pair.
Constraints
- 1 ≤ order.length ≤ 10^5
- order is a permutation of 0..n-1
Hint
Show the first hint
Every neighbour swap is also a swap. So the question is whether any non-adjacent swap exists.
Walkthrough
How to approach it
01Clarify before coding
- Is it always a permutation of 0..n-1? Yes, which is what makes an O(n) check possible.
- Do I need the counts themselves? No, only whether they are equal.
02Brute force
Count all swaps with merge sort (O(n log n)), count neighbour swaps in one pass, compare.
Cost: O(n log n) time, O(n) space. Correct, but the permutation structure allows O(n).
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.