---
# System prepended metadata

title: LC 2659. Make Array Empty
tags: [leedcode, hard, python]

---

# LC 2659. Make Array Empty

### [Problem link](https://leetcode.com/problems/make-array-empty/)

###### tags: `leedcode` `hard` `python`

You are given an integer array <code>nums</code> 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 <code>nums</code> empty.

**Example 1:** 

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

<table style="border: 2px solid black; border-collapse: collapse;">
<thead>
<tr>
<th style="border: 2px solid black; padding: 5px;">Operation</th>
<th style="border: 2px solid black; padding: 5px;">Array</th>
</tr>
</thead>
<tbody>
<tr>
<td style="border: 2px solid black; padding: 5px;">1</td>
<td style="border: 2px solid black; padding: 5px;">[4, -1, 3]</td>
</tr>
<tr>
<td style="border: 2px solid black; padding: 5px;">2</td>
<td style="border: 2px solid black; padding: 5px;">[-1, 3, 4]</td>
</tr>
<tr>
<td style="border: 2px solid black; padding: 5px;">3</td>
<td style="border: 2px solid black; padding: 5px;">[3, 4]</td>
</tr>
<tr>
<td style="border: 2px solid black; padding: 5px;">4</td>
<td style="border: 2px solid black; padding: 5px;">[4]</td>
</tr>
<tr>
<td style="border: 2px solid black; padding: 5px;">5</td>
<td style="border: 2px solid black; padding: 5px;">[]</td>
</tr>
</tbody>
</table>

**Example 2:** 

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

<table style="border: 2px solid black; border-collapse: collapse;">
<thead>
<tr>
<th style="border: 2px solid black; padding: 5px;">Operation</th>
<th style="border: 2px solid black; padding: 5px;">Array</th>
</tr>
</thead>
<tbody>
<tr>
<td style="border: 2px solid black; padding: 5px;">1</td>
<td style="border: 2px solid black; padding: 5px;">[2, 4, 3]</td>
</tr>
<tr>
<td style="border: 2px solid black; padding: 5px;">2</td>
<td style="border: 2px solid black; padding: 5px;">[4, 3]</td>
</tr>
<tr>
<td style="border: 2px solid black; padding: 5px;">3</td>
<td style="border: 2px solid black; padding: 5px;">[3, 4]</td>
</tr>
<tr>
<td style="border: 2px solid black; padding: 5px;">4</td>
<td style="border: 2px solid black; padding: 5px;">[4]</td>
</tr>
<tr>
<td style="border: 2px solid black; padding: 5px;">5</td>
<td style="border: 2px solid black; padding: 5px;">[]</td>
</tr>
</tbody>
</table>

**Example 3:** 

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

<table style="border: 2px solid black; border-collapse: collapse;">
<thead>
<tr>
<th style="border: 2px solid black; padding: 5px;">Operation</th>
<th style="border: 2px solid black; padding: 5px;">Array</th>
</tr>
</thead>
<tbody>
<tr>
<td style="border: 2px solid black; padding: 5px;">1</td>
<td style="border: 2px solid black; padding: 5px;">[2, 3]</td>
</tr>
<tr>
<td style="border: 2px solid black; padding: 5px;">2</td>
<td style="border: 2px solid black; padding: 5px;">[3]</td>
</tr>
<tr>
<td style="border: 2px solid black; padding: 5px;">3</td>
<td style="border: 2px solid black; padding: 5px;">[]</td>
</tr>
</tbody>
</table>

 **Constraints:** 

- <code>1 <= nums.length <= 10<sup>5</sup></code>
- <code>-10<sup>9</sup><= nums[i] <= 10<sup>9</sup></code>
- All values in <code>nums</code> are  **distinct** .


## Solution 1
#### Python
```python=
class Solution:
    def countOperationsToEmptyArray(self, nums: List[int]) -> int:
        pos = {val: idx for idx, val in enumerate(nums)}
        n = len(nums)
        res = n
        
        nums.sort()

        for i in range(1, n):
            if pos[nums[i - 1]] > pos[nums[i]]:
                res += n - i

        return res
```

>### Complexity
>n = nums.length
>|             | Time Complexity | Space Complexity |
>| ----------- | --------------- | ---------------- |
>| Solution 1  | O(nlogn)        | O(n)             |

## Note
[reference](https://leetcode.com/problems/make-array-empty/solutions/3466800/java-c-python-easy-sort-solution/?orderBy=most_votes)

For those who don't understand why res is initialized to n at the beggining, and why res += n-i in the for loop, here's my explanation:

So the intuition behind this algorithm is to split the process of removing smallest elements into multiple passes. What does that mean?
For better explanation, I'll use an example [1,4,5,2,8,7,6,3], where n=size of array=8
We split the process of removing smallest elements into 4 passes:
remove [1,2,3]
remove [4,5,6]
remove [7]
remove [8]

OK, so this is where the magic happens, to remove [1,2,3] from the array, we need to remove 1, move 4 to the back, move 5 to the back, remove 2, move 8 to the back, move 7 to the back, move 6 to the back, remove 3. The first pass uses n=size of array=8 operations, regardless what elements are in the first pass. This is why we initialize res to n.

Now, the remaining of the array is [4,5,8,7,6] after removing [1,2,3]
We want to remove [4,5,6] from the remaining array, we need to remove 4, remove 5, move 8 to the back, move 7 to the back, remove 6. And this pass takes 5 operations, which is equal to the size of the remaining array. This is why res += n - i. (since n - i is the size of the remaining array)

The remaining array is now [8,7]
And its the same process for the third pass of removing [7], move 8 to the back, remove 7, wihch takes 2 operaions, which is equal to the remaining size of the array

The remaining array is now [8]
Lastly, we just remove 8, which takes 1 operation

Now, how do we split this process into passes in code?
Since the array has been sorted, ex: [1,2,3,4,5,6,7,8], and we know the index of each element using hashmap, if we encounter a number with smaller index than previous number, we can split out a pass.
