Problem

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 nums that are strictly less than instructions[i].
  • The number of elements currently in nums that are strictly greater than instructions[i].

For example, if inserting element 3 into nums = [1,2,3,5], the cost of insertion is min(2, 1) (elements 1 and 2 are less than 3, element 5 is greater than 3) and nums will become [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

Examples

Example 1:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

Input:
instructions = [1,5,6,2]
Output:
 1
Explanation: Begin with nums = [].
Insert 1 with cost min(0, 0) = 0, now nums = [1].
Insert 5 with cost min(1, 0) = 0, now nums = [1,5].
Insert 6 with cost min(2, 0) = 0, now nums = [1,5,6].
Insert 2 with cost min(1, 2) = 1, now nums = [1,2,5,6].
The total cost is 0 + 0 + 0 + 1 = 1.

Example 2:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

Input:
instructions = [1,2,3,6,5,4]
Output:
 3
Explanation: Begin with nums = [].
Insert 1 with cost min(0, 0) = 0, now nums = [1].
Insert 2 with cost min(1, 0) = 0, now nums = [1,2].
Insert 3 with cost min(2, 0) = 0, now nums = [1,2,3].
Insert 6 with cost min(3, 0) = 0, now nums = [1,2,3,6].
Insert 5 with cost min(3, 1) = 1, now nums = [1,2,3,5,6].
Insert 4 with cost min(3, 2) = 2, now nums = [1,2,3,4,5,6].
The total cost is 0 + 0 + 0 + 0 + 1 + 2 = 3.

Example 3:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

Input:
instructions = [1,3,3,3,2,4,2,1,2]
Output:
 4
Explanation: Begin with nums = [].
Insert 1 with cost min(0, 0) = 0, now nums = [1].
Insert 3 with cost min(1, 0) = 0, now nums = [1,3].
Insert 3 with cost min(1, 0) = 0, now nums = [1,3,3].
Insert 3 with cost min(1, 0) = 0, now nums = [1,3,3,3].
Insert 2 with cost min(1, 3) = 1, now nums = [1,2,3,3,3].
Insert 4 with cost min(5, 0) = 0, now nums = [1,2,3,3,3,4].
Insert 2 with cost min(1, 4) = 1, now nums = [1,2,2,3,3,3,4].
Insert 1 with cost min(0, 6) = 0, now nums = [1,1,2,2,3,3,3,4].
Insert 2 with cost min(2, 4) = 2, now nums = [1,1,2,2,2,3,3,3,4].
The total cost is 0 + 0 + 0 + 0 + 1 + 0 + 1 + 0 + 2 = 4.

Solution

Method 1 - Using Fenwick Tree or Binary Indexed Tree

To solve this problem, we need to calculate the cost of insertion for each element from the instructions array into the sorted array nums. The challenge is to efficiently compute the number of elements in the sorted container nums that are:

  1. Strictly less than the current element (left_count).
  2. Strictly greater than the current element (right_count). The cost is determined as min(left_count, right_count) for each insertion.

Approach

  1. Naive Solution with Linear Search:
    • Maintain a list nums which holds sorted elements.
    • For each element in instructions, compute left_count and right_count by iterating through all elements in nums.
    • Insert the current element into nums at the appropriate position to keep it sorted.
    • This approach has O(n^2) time complexity, which is inefficient for large inputs.
  2. Efficient Solution with Fenwick Tree (Binary Indexed Tree):
    • Use a Fenwick Tree to efficiently query and update counts of elements less than and greater than the current element.
    • Fenwick Tree allows us to:
      • Query the prefix sum (counts of elements less than the current element).
      • Query the suffix sum (counts of elements greater than the current element).
    • Insert the current element into the Fenwick Tree and update the total cost.

Complexity

  • ⏰ Time complexity: O(n * log(max_val)). The Fenwick Tree operations (query and update) each take O(log(max_val)). Let n be the size of instructions and max_val be the maximum value in instructions.
    • Total complexity is O(n * log(max_val)).
  • 🧺 Space complexity: O(max_val). The Fenwick Tree requires O(max_val) space.