Day 10 - Create Sorted Array through Instructions

#leetcode #python #challenge

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

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.

DEV Community