Watch 6 video solutions for Make Array Empty, a hard level problem involving Array, Binary Search, Greedy. This walkthrough by Pawan Kumar Giri has 2,967 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
You are given an integer array nums containing distinct numbers, and you can perform the following operations until the array is empty:
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] <= 109nums are distinct.Problem Overview: You repeatedly remove the smallest remaining element from the array. If that element is not at the front, you rotate the array by moving the first element to the end until the target reaches the front. The task is to count how many operations are required to remove every element.
Approach 1: Direct Simulation (O(n^2) time, O(n) space)
The most straightforward idea is to simulate the process exactly as described. Store elements in a queue or list, repeatedly find the smallest remaining value, and rotate the structure until that value reaches the front. Each rotation counts as one operation, and removing the element counts as another. Because finding the minimum and rotating can take up to O(n) per removal, the overall complexity becomes O(n^2). This approach is useful for understanding the mechanics but does not scale to large inputs.
Approach 2: Iterative with Sorting + Fenwick Tree (O(n log n) time, O(n) space)
A faster approach avoids literal rotation. First pair each value with its original index and sort by value using sorting. Then process elements in increasing order. The key observation: the number of rotations equals how many active elements lie between the current pointer and the target index in the circular array. A Binary Indexed Tree (Fenwick Tree) tracks which indices are still present. For each element, query how many remaining indices lie in the range from the previous position to the target. If the target index is before the previous index, wrap around and sum two ranges. After counting, mark that index as removed in the tree. Each update and query takes O(log n), giving total complexity O(n log n).
Approach 3: Recursive Simulation with Indexed Structure (O(n log n) time, O(n) space)
The same logic can be expressed recursively. Process the sorted elements one by one while carrying the previous index as state. Each recursive step queries how many elements remain between positions using a Fenwick Tree or ordered set. After computing the operations needed to reach the next index, remove that index from the structure and recurse for the next element. Although recursion changes the control flow, the underlying work remains identical: range queries and updates on a dynamic index set. The complexity stays O(n log n).
Recommended for interviews: Interviewers typically expect the sorting + Fenwick Tree approach. Showing the brute-force simulation demonstrates you understand the problem mechanics, but the optimal O(n log n) solution proves you can convert a rotation process into range counting using efficient data structures.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Direct Simulation | O(n^2) | O(n) | Useful for understanding the rotation process or when constraints are very small |
| Sorting + Fenwick Tree (Iterative) | O(n log n) | O(n) | General optimal solution for large arrays where you must efficiently count remaining indices |
| Recursive with Fenwick Tree / Ordered Set | O(n log n) | O(n) | When recursion is preferred for clarity while still using efficient indexed data structures |