The Problem
Given an integer array
instructions
, you are asked to create a sorted array from the elements ininstructions
. You start with an empty containernums
. For each element from left to right ininstructions
, insert it intonums
. The cost of each insertion is the minimum of the following:
- The number of elements currently in
nums
that are strictly less thaninstructions[i]
.- The number of elements currently in
nums
that are strictly greater thaninstructions[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.
Top comments (0)