Create Sorted Array through Instructions
Given an integer array instructions, you are asked to create a sorted array from the elements in instructions.
You start with an empty container nums. For each element from left to right in instructions, insert it into nums. The cost of each insertion is the minimum of the following:
- The number of elements currently in
numsthat are strictly less thaninstructions[i]. - The number of elements currently in
numsthat are strictly greater thaninstructions[i].
For example, if inserting element 3 into nums = [1,2,3,5], the cost of insertion is min(2, 1) because elements 1 and 2 are less than 3, and element 5 is greater than 3; then nums becomes [1,2,3,3,5].
Return the total cost to insert all elements from instructions into nums. Since the answer may be large, return it modulo 10^9 + 7.
Example 1
Input
instructions = [1,5,6,2]Output
1The insertion costs are 0, 0, 0, and 1, so the total cost is 1.
Example 2
Input
instructions = [1,2,3,6,5,4]Output
3The insertion costs are 0, 0, 0, 0, 1, and 2, so the total cost is 3.
Constraints
- 1 <= instructions.length <= 10^5
- 1 <= instructions[i] <= 10^5
Asked at 2 companies
Practice questions like this out loud in a mock coding interview with a live AI interviewer. First one free.