aboutsummaryrefslogtreecommitdiff
path: root/create_sorted_arr_instr.py
blob: b354c736438cb967f4157d3a3cc26f4647e827b7 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
# 1649. Create Sorted Array through Instructions

"""
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]'. return the total cost to insert all
elements from 'instructions' into 'nums'. since the answer may be large,
return it modulo 10^9 + 7
"""


class Solution(object):
    def createSortedArray(self, instructions):
        """
        :type instructions: List[int]
        :rtype: int
        """
        m = max(instructions)
        arr = [0] * (m + 1)

        def update(x):
            while x <= m:
                arr[x] += 1
                x += x & -x

        def get(x):
            res = 0
            while x > 0:
                res += arr[x]
                x -= x & -x
            return res

        ans = 0
        for i, j in enumerate(instructions):
            ans += min(get(j - 1), i - get(j))
            update(j)
        return ans % (10**9 + 7)


if __name__ == "__main__":
    obj = Solution()
    print(obj.createSortedArray(instructions=[1, 5, 6, 2]))
    print(obj.createSortedArray(instructions=[1, 2, 3, 6, 5, 4]))
    print(obj.createSortedArray(instructions=[1, 3, 3, 3, 2, 4, 2, 1, 2]))