https://leetcode.com/problems/create-sorted-array-through-instructions

In this problem we need to keep sorted structure of some data, where we add elements one by one and calculate some property of this data structure. There are usually 3 different approaches in python, which is possible in these type of problems:

  1. Segment trees
  2. Binary indexed trees
  3. SortedList data structure

The fastest to write solution for me is the last one, because we do not need to implement anything from scratch. All we need to do is to add elements one by one and update ans. Imagine, that we already have [1, 1, 2, 2, 2, 3] list and we need to add element 2. If we use SList.bisect_left(2), result will be 1, for SList.bisect_right(2), result will be 3. Number of elements strictly less than 2 will be SList.bisect_left(2) and strictly greater than 2 will be len(SList) - SList.bisect_right(num)). So, we just choose minimum of them and add to ans.

Complexity: time complexity is O(n log n), where n is number of elements in instructions, because each add and bisect_left, bisect_right will spend O(log n) operations.

Alternative solutions: we can use BIT, with complexity O(n log M), where M is maximal number or O(n log n), if we use compression of indexes. Same is true for segment tree.

from sortedcontainers import SortedList

class Solution:
    def createSortedArray(self, instructions):
        SList = SortedList()
        ans = 0
        for num in instructions:
            ans += min(SList.bisect_left(num), len(SList) - SList.bisect_right(num))
            ans %= (10**9 + 7)
            SList.add(num)

        return ans

If you like the solution, you can upvote it on leetcode discussion section: Problem 1649