1007. Insertion Cost
A librarian files returned books into a shelf that must stay sorted by call number. The books arrive in the order given by instructions, where instructions[i] is the call number of the i-th returned book. The shelf starts empty.
To place a book, the librarian may slide either all books with a strictly smaller call number or all books with a strictly larger call number out of the way, whichever group is smaller; books with the same call number are not moved. Sliding one book costs 1, and the book is then put in a valid position among its equals. Return the total sliding cost of filing every book. Aim for O(n log n) time.
Example 1
- Input:
- instructions = [11,4,20,4,9,15]
- Output:
- 3
- Explanation:
The costs of the six books are 0, 0, 0, 0, 2 and 1, which total 3.
Example 2
- Input:
- instructions = [8,8,8,8]
- Output:
- 0
- Explanation:
Equal call numbers never need to move, so every book costs 0.
Constraints
1 ≤ instructions.length ≤ 30000
1 ≤ instructions[i] ≤ 105
The total cost is at most n * n / 4, so it fits in a 32-bit signed integer.
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 1,600 msC++ 400 msJava 800 msJavaScript 800 msTypeScript 800 ms
Expected complexity
- Time
- O(n log V)
- Space
- O(V)