This page explains Java solution to problem `Create Sorted Array through Instructions`

using `Binary Indexed Tree`

algorithm.

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]`

.

Input: instructions = [1,5,6,2]Output: 1Explanation: 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.

Input: instructions = [1,2,3,6,5,4]Output: 3Explanation: 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.

Input: instructions = [1,3,3,3,2,4,2,1,2]Output: 4Explanation: 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.

```
package com.vc.hard;
class CreateSortedArrayThroughInstructions {
private int[] count;
private int limit = (int)1e5 + 1;
private int MOD = (int)1e9 + 7;
public int createSortedArray(int[] instructions) {
int totalCost = 0;
this.count = new int[limit];
for(int i = 0; i < instructions.length; i++) {
int smallerNumberCount = getCount(instructions[i] - 1);
int greaterNumberCount = i - getCount(instructions[i]);
totalCost = (totalCost + Math.min(smallerNumberCount, greaterNumberCount)) % MOD;
updateCount(instructions[i]);
}
return totalCost;
}
private void updateCount(int number) {
while(number < limit) {
count[number]++;
number += number & -number;
}
}
private int getCount(int number) {
int res = 0;
while(number > 0) {
res += count[number];
number -= number & -number;
}
return res;
}
}
```

O(N log M) Where

N is total number of instructions in an input array

M is maximum value in an instructions input array, in our case it is 1e^{5}+ 1

O(M) Where

M is maximum value in an instructions input array, in our case it is 1e^{5}+ 1