## DEV Community is a community of 620,183 amazing developers

We're a place where coders share, stay up-to-date and grow their careers.

# Day 10 - Create Sorted Array through Instructions

Ruairí O'Brien Updated on ・4 min read

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

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

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