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.
The iterative approach involves using a loop to solve the problem step by step. This is typically straightforward and avoids the overhead of recursion, making it suitable for problems where the iterative process is clear and manageable.
This C program defines a simple iterative function to print numbers from 0 to n-1. The main function initializes n and calls the iterative function.
Time Complexity: O(n)
Space Complexity: O(1)
The recursive approach leverages function calls to perform repeated operations. It is often cleaner in implementation for problems with natural recursive structures like tree traversal or the Fibonacci sequence.
This C program uses a recursive function to print numbers from 0 to n-1. The recursion prints numbers in ascending order by first reaching the base case before printing.
Time Complexity: O(n)
Space Complexity: O(n) due to recursive call stack
First, we use a hash table pos to record the position of each element in array nums. Then, we sort array nums. The initial answer is the position of the minimum element in array nums plus 1, which is ans = pos[nums[0]] + 1.
Next, we traverse the sorted array nums, the indexes of the two adjacent elements a and b are i = pos[a], j = pos[b]. The number of operations needed to move the second element b to the first position of the array and delete it is equal to the interval between the two indexes, minus the number of indexes deleted between the two indexes, and add the number of operations to the answer. We can use a Fenwick tree or an ordered list to maintain the deleted indexes between two indexes, so that we can find the number of deleted indexes between two indexes in O(log n) time. Note that if i \gt j, then we need to increase n - k operations, where k is the current position.
After the traversal is over, return the number of operations ans.
The time complexity is O(n times log n), and the space complexity is O(n). Where n is the length of array nums.
Python
Java
C++
Go
TypeScript
Python
| Approach | Complexity |
|---|---|
| Iterative Approach | Time Complexity: O(n) |
| Recursive Approach | Time Complexity: O(n) |
| Hash Table + Sorting + Fenwick Tree | — |
| Default Approach | — |
| 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 |
Leetcode biweekly 103 Solution l make array empty (hard) l Hindi • Pawan Kumar Giri • 2,967 views views
Watch 5 more video solutions →Practice Make Array Empty with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor