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
numsthat are strictly less thaninstructions[i].- The number of elements currently in
numsthat 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 <= 1051 <= 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)