# Create Sorted Array through Instructions

This page explains Java solution to problem `Create Sorted Array through Instructions` using `Binary Indexed Tree` algorithm.

## Problem Statement

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

Example 1:

Input: instructions = [1,5,6,2]
Output: 1
Explanation: Begin with nums = [].
Insert 1 with cost min(0, 0) = 0, now nums = .
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:

Input: instructions = [1,2,3,6,5,4]
Output: 3
Explanation: Begin with nums = [].
Insert 1 with cost min(0, 0) = 0, now nums = .
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:

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 = .
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

If you have any suggestions in below code, please create a pull request by clicking here.
``````
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;
}
}
``````

## Time Complexity

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 1e5 + 1

## Space Complexity

O(M) Where
M is maximum value in an instructions input array, in our case it is 1e5 + 1