## The 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 fromleft to rightin`instructions`

, insert it into`nums`

. Thecostof each insertion is theminimumof the following:

- The number of elements currently in
`nums`

that arestrictly less than`instructions[i]`

.- The number of elements currently in
`nums`

that arestrictly 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`

**Example 1:**

```
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:**

```
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:**

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

**Constraints:**

`1 <= instructions.length <= 105`

`1 <= instructions[i] <= 105`

## My Tests

```
import pytest
from .Day10 import Solution
s = Solution()
@pytest.mark.parametrize(
"instructions,expected",
[
([1, 5, 6, 2], 1),
([1, 2, 3, 6, 5, 4], 3),
([1, 3, 3, 3, 2, 4, 2, 1, 2], 4),
],
)
def test_create_sortedArray(instructions, expected):
assert s.createSortedArray(instructions) == expected
```

## My Solution

The first solution I came up with was a binary search like this:

```
from typing import List
def findLastIndex(nums: List[int], val: int, n: int):
start = 0
end = n
index = -1
while start <= end:
mid = (start + end) // 2
if nums[mid] > val:
end = mid - 1
elif nums[mid] < val:
start = mid + 1
else:
index = mid
start = mid + 1
return index
def getInsertPoint(nums: List[int], val: int, n: int):
start = 0
end = n
while start <= end:
mid = (start + end) // 2
if nums[mid] < val:
start = mid + 1
else:
end = mid - 1
return start
class Solution:
def createSortedArray(self, instructions: List[int]) -> int:
nums = []
cost = 0
for i in instructions:
n = len(nums)
insertPoint = getInsertPoint(nums, i, n - 1)
nums.insert(insertPoint, i)
end = findLastIndex(nums, i, n)
cost += min(insertPoint, len(nums) - (end + 1))
mod = 1000000007
return cost % mod
```

Turned out that was nowhere near fast enough but it did get me thinking about using a binary tree. After much arduous research, I arrived at the Binary Index Tree as a good option.

```
class BinaryIndexTree:
def __init__(self, space: int):
self.space = space
# Init tree to all zeros with 'space' nodes
self.tree = [0] * space
def getCost(self, index):
result = 0
while index >= 1:
result += self.tree[index]
index -= index & -index
return result
def update(self, index, value):
while index < self.space:
self.tree[index] += value
index += index & -index
class Solution:
def createSortedArray(self, instructions: List[int]) -> int:
n = len(instructions)
# Init tree ensuring we have a node for each number
tree = BinaryIndexTree(max(instructions) + 2)
cost = 0
for i in range(n):
leftCost = tree.getCost(instructions[i])
rightCost = i - tree.getCost(instructions[i] + 1)
cost += min(leftCost, rightCost)
tree.update(instructions[i] + 1, 1)
mod = 1000000007
return cost % mod
```

## Analysis

## My Commentary

I did this on a Sunday and it took me hours. Usually, I try to limit myself to a max of 30 or maybe 45 minutes. I did find this interesting though but would have failed an interview if they were looking for anything better than a binary search.

I don't really have much to add beyond what was covered in the Binary Index Tree Tutorial I read so I would suggest looking at that if you want to learn more. There are probably other structures or algorithms that solve this better but that was the best I found in my search today.

## Discussion (0)