966. Insertion Cost
A librarian builds a shelf of books ordered by their catalogue numbers, starting from an empty shelf. She receives the numbers in the array instructions and places the books one at a time, from left to right in that array, always keeping the shelf sorted (books with equal numbers may sit next to each other).
Placing a book costs the smaller of two counts: the number of books already on the shelf whose number is strictly less than the new book's number, and the number of books already on the shelf whose number is strictly greater. Return the total cost of placing all books, modulo 1000000007.
Example 1
- Input:
- instructions = [5,5,1,9,5,7]
- Output:
- 2
- Explanation:
Inserting the values one at a time costs [0, 0, 0, 0, 1, 1] in turn (each is the smaller of the number of already stored values below it and above it), so the total is 2.
Example 2
- Input:
- instructions = [6,3,9,4,8,3,6]
- Output:
- 4
- Explanation:
Inserting the values one at a time costs [0, 0, 0, 1, 1, 0, 2] in turn (each is the smaller of the number of already stored values below it and above it), so the total is 4.
Constraints
- 1 ≤ instructions.length ≤ 105
- 1 ≤ instructions[i] ≤ 105
- The answer is returned modulo 1000000007
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 800 msC++ 200 msJava 400 msJavaScript 400 msTypeScript 400 ms
Expected complexity
- Time
- O(n log m), m = max value
- Space
- O(m)