# Make Array Empty
**Difficulty:** HARD
[External](https://leetcode.com/problems/make-array-empty)
Canonical: https://scaleengineer.com/dsa/problems/make-array-empty
**Patterns:** [Greedy](https://scaleengineer.com/dsa/patterns/greedy)
**Algorithms:** [Binary Search](https://scaleengineer.com/algorithms/binary-search), [Sorting](https://scaleengineer.com/algorithms/sorting)
**Data structures:** Array, Binary Indexed Tree, Segment Tree, Ordered Set
**Companies:** [Zepto](https://scaleengineer.com/companies/zepto)
---
## Problem
You are given an integer array `nums` containing **distinct** numbers, and you can perform the following operations **until the array is empty**:

* If the first element has the **smallest** value, remove it
* Otherwise, put the first element at the **end** of the array.

Return _an integer denoting the number of operations it takes to make_ `nums` _empty._

**Example 1:**

**Input:** nums = [3,4,-1]
**Output:** 5

| Operation | Array        |
| --------- | ------------ |
| 1         | \[4, -1, 3\] |
| 2         | \[-1, 3, 4\] |
| 3         | \[3, 4\]     |
| 4         | \[4\]        |
| 5         | \[\]         |

**Example 2:**

**Input:** nums = [1,2,4,3]
**Output:** 5

| Operation | Array       |
| --------- | ----------- |
| 1         | \[2, 4, 3\] |
| 2         | \[4, 3\]    |
| 3         | \[3, 4\]    |
| 4         | \[4\]       |
| 5         | \[\]        |

**Example 3:**

**Input:** nums = [1,2,3]
**Output:** 3

| Operation | Array    |
| --------- | -------- |
| 1         | \[2, 3\] |
| 2         | \[3\]    |
| 3         | \[\]     |

**Constraints:**

* `1 <= nums.length <= 105`
* `-109 <= nums[i] <= 109`
* All values in `nums` are **distinct**.

# Approaches
## Direct Simulation
This approach directly simulates the process described in the problem. We use a data structure that efficiently supports adding an element to the end and removing an element from the front, such as a `Deque` (Double-Ended Queue) or a `LinkedList`.
**Time:** O(N^2), where N is the number of elements in `nums`. In each step of removing an element, we might need to find the minimum value, which takes O(K) time where K is the current size of the deque. Since we do this N times, the total time complexity is the sum of K from N down to 1, which is O(N^2). · **Space:** O(N) to store the elements in the `Deque`.
**Pros:** Simple to understand and implement.; Follows the problem description directly.
**Cons:** Inefficient for large inputs due to the repeated search for the minimum element, leading to a quadratic time complexity.
### Explanation
The simulation proceeds step by step until the array becomes empty. In each step, we need to determine if the first element of the current array is the minimum. 

1. Initialize a `Deque` with the elements from the input array `nums`.
2. Initialize a counter for operations to zero.
3. Loop until the `Deque` is empty:
    a. Find the minimum value in the current `Deque`. This requires iterating through all elements of the `Deque`.
    b. Peek at the first element of the `Deque`.
    c. If the first element is the minimum, remove it from the front. This is one operation.
    d. If the first element is not the minimum, move it from the front to the back. This is also one operation.
    e. Increment the operation counter in either case.

This process is repeated until the `Deque` is empty. The final value of the operation counter is the answer.

```java
import java.util.ArrayDeque;
import java.util.Collections;
import java.util.Deque;

class Solution {
    public long countOperationsToEmptyArray(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }

        Deque<Integer> deque = new ArrayDeque<>();
        for (int num : nums) {
            deque.add(num);
        }

        long operations = 0;
        while (!deque.isEmpty()) {
            int minVal = Collections.min(deque);
            int firstElement = deque.peekFirst();

            operations++;
            if (firstElement == minVal) {
                deque.pollFirst();
            } else {
                deque.addLast(deque.pollFirst());
            }
        }

        return operations;
    }
}
```
### Algorithm
Create a `Deque` and populate it with the elements of `nums`.
Initialize `operations = 0`.
While the `Deque` is not empty:
  Find the minimum element in the `Deque` by iterating through it.
  Get the first element from the `Deque`.
  Increment `operations`.
  If the first element is the minimum, remove it from the front.
  Otherwise, move the first element to the end of the `Deque`.
Return `operations`.

## Optimized Approach using Sorting and Fenwick Tree
The brute-force simulation is slow because finding the minimum at each step is costly. We can observe that elements are always removed in increasing order of their value. This suggests we can pre-sort the numbers to determine the removal sequence. The main challenge then becomes calculating the number of operations for each removal without actually simulating the queue movements.
**Time:** O(N log N). Sorting the pairs takes O(N log N). The main loop runs N times, and each iteration involves a constant number of Fenwick Tree operations (update and query), each taking O(log N) time. Thus, the loop also takes O(N log N). · **Space:** O(N). We need O(N) space to store the `(value, index)` pairs and O(N) space for the Fenwick Tree.
**Pros:** Highly efficient and can handle large inputs.; Solves the problem by transforming it into a counting problem on ranges, which is a powerful technique.
**Cons:** More complex to understand and implement than the direct simulation.; Requires knowledge of advanced data structures like Fenwick Trees or Segment Trees.
### Explanation
The total number of operations is the sum of operations for each removal. An operation is either a 'move to back' or a 'remove'. There will be exactly `N` removal operations. So, the problem reduces to finding the total number of 'move to back' operations.

A 'move to back' operation occurs when the element at the front is not the current minimum. The number of moves required to bring the minimum to the front is equal to its 0-indexed position in the current conceptual queue.

The core idea is to determine this position for each element in its removal turn.

1.  **Determine Removal Order:** Create pairs of `(value, original_index)` and sort them by value. This gives us the order in which elements are removed, specified by their original indices `idx_0, idx_1, ..., idx_{N-1}`.

2.  **Calculate Moves:** We process the elements in their removal order. For each element, we calculate how many moves are needed. The number of moves is the number of elements that are currently before it in the conceptual circular queue. 
    - Let's say we just removed the element at original index `last_idx`. The conceptual queue now starts with elements that were originally after `last_idx`.
    - When we need to remove the element at `current_idx`, the number of moves depends on the relative positions of `current_idx` and `last_idx` and which elements between them have already been removed.

3.  **Efficiently Count Unremoved Elements:** To find the number of moves, we need to count how many elements are still present in certain ranges of original indices. A Fenwick Tree (or Binary Indexed Tree, BIT) is a perfect data structure for this. We can use a BIT to keep track of the indices of elements that have been removed. 
    - `update(idx, 1)`: Mark the element at `idx` as removed.
    - `query(range)`: Get the count of removed elements in a range.
    The number of *unremoved* elements in a range is `range_size - query(range)`.

**Algorithm:**
1.  Store `(value, index)` pairs and sort them to get the removal sequence of indices `idx_0, ..., idx_{N-1}`.
2.  Initialize `total_ops = N` (for `N` removals).
3.  Initialize a Fenwick Tree of size `N` to all zeros.
4.  The moves for the first element `idx_0` is simply `idx_0`. Add this to `total_ops`. Mark `idx_0` as removed in the BIT.
5.  Iterate from the second element (`i=1` to `N-1`):
    a. Let `last_idx = idx_{i-1}` and `current_idx = idx_i`.
    b. Calculate the number of unremoved elements between `last_idx` and `current_idx` in a cyclic manner using the BIT. This gives the number of moves for the current step.
    c. Add these moves to `total_ops`.
    d. Mark `current_idx` as removed in the BIT.

This approach avoids the costly simulation of the queue, leading to a much more efficient solution.

```java
import java.util.Arrays;
import java.util.Comparator;

class Solution {
    public long countOperationsToEmptyArray(int[] nums) {
        int n = nums.length;
        Integer[] indices = new Integer[n];
        for (int i = 0; i < n; i++) {
            indices[i] = i;
        }

        Arrays.sort(indices, Comparator.comparingInt(i -> nums[i]));

        FenwickTree ft = new FenwickTree(n);
        long totalOps = 0;
        int lastIdx = -1; // Represents the start of the circular array before any removal

        for (int i = 0; i < n; i++) {
            int currentIdx = indices[i];
            long moves;
            if (lastIdx == -1) { // First element to be removed
                moves = currentIdx;
            } else if (currentIdx > lastIdx) {
                // Number of elements between lastIdx and currentIdx
                long totalBetween = currentIdx - lastIdx - 1;
                // Number of already removed elements in that range
                long removedBetween = ft.query(lastIdx + 1, currentIdx - 1);
                moves = totalBetween - removedBetween;
            } else { // currentIdx < lastIdx, wrap-around
                // Unremoved elements from lastIdx+1 to end
                long totalAfter = (n - 1) - lastIdx;
                long removedAfter = ft.query(lastIdx + 1, n - 1);
                long unremovedAfter = totalAfter - removedAfter;

                // Unremoved elements from start to currentIdx-1
                long totalBefore = currentIdx;
                long removedBefore = ft.query(0, currentIdx - 1);
                long unremovedBefore = totalBefore - removedBefore;

                moves = unremovedAfter + unremovedBefore;
            }
            
            // Each step costs moves + 1 (for removal)
            // The size of the array for this pass is (n - i)
            // The number of operations for this pass is moves + 1
            // Another way to see it: total ops = n (removals) + total moves
            // Here we sum up (moves + 1) for each step
            totalOps += moves + 1;

            ft.update(currentIdx, 1);
            lastIdx = currentIdx;
        }

        return totalOps;
    }
}

class FenwickTree {
    private int[] bit;
    private int size;

    public FenwickTree(int n) {
        this.size = n;
        this.bit = new int[n + 1];
    }

    public void update(int index, int delta) {
        index++; // 1-based index
        while (index <= size) {
            bit[index] += delta;
            index += index & -index;
        }
    }

    public int query(int index) {
        index++; // 1-based index
        int sum = 0;
        while (index > 0) {
            sum += bit[index];
            index -= index & -index;
        }
        return sum;
    }

    public int query(int left, int right) {
        if (left > right) return 0;
        return query(right) - query(left - 1);
    }
}
```
### Algorithm
Create pairs of `(value, original_index)` from the input `nums` array.
Sort these pairs based on the value to get the order of removal by original index.
Initialize a Fenwick Tree (BIT) of size `N` to keep track of removed elements.
Initialize `total_operations = 0` and `last_removed_index`.
Iterate through the sorted indices:
  For each `current_index`, calculate the number of 'move' operations required.
  This is the count of unremoved elements between `last_removed_index` and `current_index` in a cyclic manner.
  Use the BIT to find the count of already removed elements in the relevant ranges to calculate the unremoved count.
  Add `moves + 1` to `total_operations`.
  Update the BIT to mark `current_index` as removed.
  Update `last_removed_index` to `current_index`.
Return `total_operations`.

# Solutions
### Java

```java
class BinaryIndexedTree { private int n ; private int [] c ; public BinaryIndexedTree ( int n ) { this . n = n ; c = new int [ n + 1 ]; } public void update ( int x , int delta ) { while ( x <= n ) { c [ x ] += delta ; x += x & - x ; } } public int query ( int x ) { int s = 0 ; while ( x > 0 ) { s += c [ x ]; x -= x & - x ; } return s ; } } class Solution { public long countOperationsToEmptyArray ( int [] nums ) { int n = nums . length ; Map < Integer , Integer > pos = new HashMap <>(); for ( int i = 0 ; i < n ; ++ i ) { pos . put ( nums [ i ], i ); } Arrays . sort ( nums ); long ans = pos . get ( nums [ 0 ]) + 1 ; BinaryIndexedTree tree = new BinaryIndexedTree ( n ); for ( int k = 0 ; k < n - 1 ; ++ k ) { int i = pos . get ( nums [ k ]), j = pos . get ( nums [ k + 1 ]); long d = j - i - ( tree . query ( j + 1 ) - tree . query ( i + 1 )); ans += d + ( n - k ) * ( i > j ? 1 : 0 ); tree . update ( i + 1 , 1 ); } return ans ; } }
```

### CPP

```cpp
class BinaryIndexedTree { public: BinaryIndexedTree ( int _n ) : n ( _n ) , c ( _n + 1 ) {} void update ( int x , int delta ) { while ( x <= n ) { c [ x ] += delta ; x += x & - x ; } } int query ( int x ) { int s = 0 ; while ( x ) { s += c [ x ]; x -= x & - x ; } return s ; } private: int n ; vector < int > c ; }; class Solution { public: long long countOperationsToEmptyArray ( vector < int >& nums ) { unordered_map < int , int > pos ; int n = nums . size (); for ( int i = 0 ; i < n ; ++ i ) { pos [ nums [ i ]] = i ; } sort ( nums . begin (), nums . end ()); BinaryIndexedTree tree ( n ); long long ans = pos [ nums [ 0 ]] + 1 ; for ( int k = 0 ; k < n - 1 ; ++ k ) { int i = pos [ nums [ k ]], j = pos [ nums [ k + 1 ]]; long long d = j - i - ( tree . query ( j + 1 ) - tree . query ( i + 1 )); ans += d + ( n - k ) * int ( i > j ); tree . update ( i + 1 , 1 ); } return ans ; } };
```

### Python

```python
from sortedcontainers import SortedList class Solution : def countOperationsToEmptyArray ( self , nums : List [ int ]) -> int : pos = { x : i for i , x in enumerate ( nums )} nums . sort () sl = SortedList () ans = pos [ nums [ 0 ]] + 1 n = len ( nums ) for k , ( a , b ) in enumerate ( pairwise ( nums )): i , j = pos [ a ], pos [ b ] d = j - i - sl . bisect ( j ) + sl . bisect ( i ) ans += d + ( n - k ) * int ( i > j ) sl . add ( i ) return ans
```