Create Sorted Array through Instructions — LeetCode 1649 Python Solution

HardBinary Indexed TreeSegment TreeArrayBinary SearchDivide and ConquerOrdered SetMerge Sort

Problem: #1649
Pattern: Monotonic Stack
Reading time: 5 min
Source: leetcode.com

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.

Example

Input: instructions = [1,5,6,2]
Output: 1
Explanation: Begin with nums = [].

Python solution

Python

class BinaryIndexedTree:
    def __init__(self, n):
        self.n = n
        self.c = [0] * (n + 1)

    def update(self, x: int, v: int):
        while x <= self.n:
            self.c[x] += v
            x += x & -x

    def query(self, x: int) -> int:
        s = 0
        while x:
            s += self.c[x]
            x -= x & -x
        return s


class Solution:
    def createSortedArray(self, instructions: List[int]) -> int:
        m = max(instructions)
        tree = BinaryIndexedTree(m)
        ans = 0
        mod = 10**9 + 7
        for i, x in enumerate(instructions):
            cost = min(tree.query(x - 1), i - tree.query(x))
            ans += cost
            tree.update(x, 1)
        return ans % mod

Complexity

Measure	Complexity
Time	O(log n) or O(n log n)
Space	O(1) auxiliary

Pattern: Monotonic Stack

Answer "what is the next greater element" for every position in one pass. LeetCode 1649. Create Sorted Array through Instructions is filed here because the reference solution below belongs to the algorithm family this hub collects, even though its LeetCode tags point elsewhere.

The monotonic stack guide has the Python template for the pattern and the 225 LeetCode problems that use it.

Frequently asked questions

How hard is LeetCode 1649. Create Sorted Array through Instructions?: LeetCode 1649. Create Sorted Array through Instructions is rated Hard on LeetCode.
What topics does LeetCode 1649. Create Sorted Array through Instructions cover?: LeetCode 1649. Create Sorted Array through Instructions is tagged Binary Indexed Tree, Segment Tree, Array, Binary Search, Divide and Conquer, Ordered Set and Merge Sort on LeetCode.