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

Make Array Empty

Number: 2765

Difficulty: Hard

Paid? No

Companies: TikTok

Problem Description

Given an integer array nums with distinct numbers, you can perform the following operations repeatedly until the array becomes empty:

  • If the first element is the smallest element in the array, remove it.
  • Otherwise, move the first element to the end of the array. Return the total number of operations required to make nums empty.

Key Insights

  • The removal order is determined by the relative order of the elements when sorted in ascending order.
  • Instead of simulating the process (which could be too slow for large arrays), calculate the number of operations needed using the positions of each element.
  • Use a Binary Indexed Tree (BIT) (also known as a Fenwick Tree) to dynamically query and update the number of remaining elements to efficiently determine the “effective position” of an element in the circular array.
  • Maintain a pointer representing the current start position in the effective (remaining) array.
  • When processing each element in sorted order, calculate the cost (number of operations) depending on whether the effective position is ahead of or behind the current pointer (circular traversal).

Space and Time Complexity

Time Complexity: O(n log n) – O(n log n) for sorting and O(n log n) for BIT operations over n elements. Space Complexity: O(n) – for the BIT and additional arrays.

Solution

The approach is to process the removals in the order of increasing value. For each element (in sorted order):

  1. Determine its original index in the array.
  2. Using a BIT, compute its effective index among the remaining elements (i.e. how many elements before the given index are still present).
  3. Calculate the number of operations needed to rotate from the current pointer to this effective index. If the effective index is not reachable by just moving forward (because of the circular nature), wrap around.
  4. Add one additional operation for the removal itself.
  5. Update the BIT to indicate that this element has been removed, and set the current pointer to the effective index of the removed element (adjusting for wrap‐around). This design avoids an O(n^2) simulation in favor of efficient BIT queries and updates.

Code Solutions

# Python solution using Binary Indexed Tree (Fenwick Tree)
class BIT:
    def __init__(self, n):
        # Initialize BIT with given size n+1 (1-indexed)
        self.n = n
        self.tree = [0] * (n + 1)
    
    def update(self, i, delta):
        # Increase value at index i by delta in BIT
        while i <= self.n:
            self.tree[i] += delta
            i += i & -i
            
    def query(self, i):
        # Returns the prefix sum from index 1 to i
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s

def makeArrayEmpty(nums):
    n = len(nums)
    # Pair each element with its original index
    indexed = [(num, i) for i, num in enumerate(nums)]
    # Sort the pairs by the element value
    indexed.sort()  # Sorted in ascending order

    # Build BIT with initial frequency 1 for each position (1-indexed)
    bit = BIT(n)
    for i in range(1, n+1):
        bit.update(i, 1)

    operations = 0
    # cur represents the current pointer in the effective order of remaining elements
    cur = 0
    # Process elements in increasing order because removals will happen in that order.
    for _, original_index in indexed:
        # Get effective index of the target element among remaining 
        # BIT uses 1-indexing so we query (original_index + 1)
        effective_index = bit.query(original_index + 1) - 1
        total_remaining = bit.query(n)
        if effective_index >= cur:
            # If the target is ahead of the current pointer, simple difference
            operations += effective_index - cur + 1
        else:
            # If the target is behind the current pointer, we need to rotate (wrap-around)
            operations += total_remaining - cur + effective_index + 1
        # Remove the element from the BIT
        bit.update(original_index + 1, -1)
        # Set cur to the effective index of the just removed element.
        # After removal, if it is at the end, reset to the beginning
        cur = effective_index
        if cur == total_remaining - 1:
            cur = 0

    return operations

# Example usage:
nums = [3, 4, -1]
print(makeArrayEmpty(nums))  # Expected output: 5
← Back to All Questions