Make Array Empty - Video Solutions

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.