We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Create Sorted Array through Instructions

Difficulty: Hard

Problem Description

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.

Key Insights

  • You need to maintain an ordered collection while inserting elements.
  • Efficiently count elements less than and greater than the current element is crucial for calculating insertion costs.
  • Binary Indexed Tree (Fenwick Tree) or a balanced binary search tree can be used to efficiently manage counts during insertions.

Space and Time Complexity

Time Complexity: O(N log N)
Space Complexity: O(N)

Solution

To solve this problem, we can utilize a Binary Indexed Tree (BIT) or a Fenwick Tree. This data structure allows us to efficiently update the counts of elements and query the number of elements that are less than or greater than the current instruction.

For each element in the instructions array:

  1. Query the BIT to find the number of elements less than the current element.
  2. Calculate the number of elements greater than the current element by subtracting the count of elements less than the current element from the total count of inserted elements.
  3. The insertion cost is the minimum of these two counts.
  4. Update the BIT with the current element after calculating the cost.

This method ensures that we can handle up to 100,000 insertions efficiently.

Code Solutions

class BIT:
    def __init__(self, size):
        self.size = size
        self.tree = [0] * (size + 1)

    def update(self, index, delta):
        while index <= self.size:
            self.tree[index] += delta
            index += index & -index

    def query(self, index):
        total = 0
        while index > 0:
            total += self.tree[index]
            index -= index & -index
        return total

def createSortedArray(instructions):
    MOD = 10**9 + 7
    max_val = 100000
    bit = BIT(max_val)
    total_cost = 0
    
    for i, num in enumerate(instructions):
        less_count = bit.query(num - 1)
        greater_count = i - bit.query(num)
        total_cost += min(less_count, greater_count)
        bit.update(num, 1)
    
    return total_cost % MOD
← Back to All Questions