Day 10 - Create Sorted Array through Instructions
Tags: leetcode, python, challenge
Published: 2021-01-10 16:11:24

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

__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

[Link to code](https://github.com/ruarfff/leetcode-jan-2021)


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

```python
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](https://www.topcoder.com/community/competitive-programming/tutorials/binary-indexed-trees/) as a good option. 

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

![Alt Text](https://dev-to-uploads.s3.amazonaws.com/i/l03o1t37u9xaogaryfwx.png)

![Alt Text](https://dev-to-uploads.s3.amazonaws.com/i/zv2a9ef7lmc6ola1y3kg.png)

## 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](https://www.topcoder.com/community/competitive-programming/tutorials/binary-indexed-trees/) 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.