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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Create Sorted Array through Instructions

Number: 1772

Difficulty: Hard

Paid? No

Companies: Akuna Capital

Problem Description

Given an integer array instructions, the goal is to insert each element from instructions into an initially empty array nums such that nums remains sorted. For every insertion, the cost is defined as the minimum between:

  • The number of elements in nums that are strictly less than the current element.
  • The number of elements in nums that are strictly greater than the current element. Return the total cost modulo (10^9 + 7).

Key Insights

  • To efficiently count elements less than or greater than a given value as nums grows, use a data structure that supports fast range-sum queries and point updates.
  • A Binary Indexed Tree (Fenwick Tree) or Segment Tree is ideal for this purpose.
  • The overall approach is to process each instruction one by one, updating the data structure and summing up the insertion cost.
  • Keep in mind that the current index in the instructions (i.e., the current number of inserted elements) can help determine the number of elements greater than the current element by subtracting the prefix count from i.

Space and Time Complexity

Time Complexity: O(n log m), where n is the number of instructions and m is the maximum value in instructions.
Space Complexity: O(m), for the binary indexed tree.

Solution

The solution uses a Binary Indexed Tree (Fenwick Tree) to maintain counts of inserted numbers efficiently. For each element in instructions:

  1. Query the BIT to get the count of numbers strictly less than the current number.
  2. Calculate the count of numbers strictly greater than the current number by subtracting the count of numbers less-than or equal to the current number from the total numbers processed so far.
  3. The insertion cost is the minimum of these two counts.
  4. Update the BIT to include the new number. This approach ensures that both update and query operations run in O(log m) time, making it efficient even for large inputs.

Code Solutions

# Fenwick Tree (Binary Indexed Tree) implementation in Python
class FenwickTree:
    def __init__(self, size):
        self.size = size  # maximum value possible
        self.tree = [0] * (size + 1)  # BIT uses 1-indexing

    # Update BIT at specified index by delta
    def update(self, index, delta):
        while index <= self.size:
            self.tree[index] += delta
            index += index & -index

    # Query the prefix sum up to the given index
    def query(self, index):
        s = 0
        while index > 0:
            s += self.tree[index]
            index -= index & -index
        return s

class Solution:
    def createSortedArray(self, instructions):
        mod = 10**9 + 7
        max_val = max(instructions)
        bit = FenwickTree(max_val)
        cost = 0
        
        # Process each number in instructions
        for i, num in enumerate(instructions):
            # Get count of numbers strictly less than num
            count_less = bit.query(num - 1)
            # Get count of numbers strictly greater than num using total count processed so far
            count_greater = i - bit.query(num)
            cost = (cost + min(count_less, count_greater)) % mod
            # Update BIT with the current number
            bit.update(num, 1)
        return cost

# Example usage:
sol = Solution()
print(sol.createSortedArray([1, 5, 6, 2]))
← Back to All Questions