Leetcode: 1649. Create Sorted Array through Instructions

Pattern: Answer query on sorted data. For each instructions, keep the previous instructions sorted and use Binary Search to compute the number of strictly less and greater. Time complexity is \(O(n \log n)\) and space is \(O(n)\).

from sortedcontainers import SortedList
from typing import List


class Solution:
    def createSortedArray(self, instructions: List[int]) -> int:
        MOD = 10**9 + 7
        N = len(instructions)
        s = SortedList()
        ans = 0
        for i in instructions:
            l = s.bisect_left(i)
            r = len(s) - s.bisect_left(i + 1)
            ans = (ans + min(l, r)) % MOD
            s.add(i)
        return ans