Make Array Empty

Make Array Empty

What is this problem about?

The Make Array Empty problem provides an array of integers. You are tasked with emptying the array using specific operations. In one operation, you can either remove the first element of the array if it is the absolute smallest element currently in the array, or you can move the first element to the very end of the array. You need to find the total number of operations required to completely empty the array.

Why is this asked in interviews?

This is a Hard-level optimization problem. Simulating the movement of elements to the back of the array is essentially simulating a Queue. However, doing this literally takes $O(N^2)$ time. Interviewers ask this to evaluate your ability to use advanced data structures—like a Binary Indexed Tree (Fenwick Tree) or a Segment Tree—to count shifts efficiently in $O(N \log N)$ time.

Algorithmic pattern used

The best approach leverages Sorting and a Binary Indexed Tree (BIT) (or Fenwick Tree) for efficient point updates and range sum queries.

1. Note the original index of each element.
2. Sort the elements by their values.
3. Use a BIT (initialized with 1s) to track the "active" elements in the array.
4. When you need to remove the next smallest element, the cost is the number of active elements between your current position and the target element's original position. You query this sum using the BIT, add it to your total operations, and then update the BIT to mark that element as removed (0).

Example explanation

Imagine array: [3, 4, -1] Original indices: 3 at 0, 4 at 1, -1 at 2. Sorted: [-1, 3, 4]. BIT tracks active indices: [1, 1, 1] (indices 0, 1, 2 are active). Current position = 0.

• Need to remove -1 (original index 2). We must shift from 0 to 2. Active elements are at 0, 1, 2. Cost = 3 operations. Remove -1. BIT becomes [1, 1, 0]. Current position = 2.
• Need to remove 3 (original index 0). We must shift from 2 wrapping around to 0. Cost is active elements from 2 to end, plus start to 0. Active elements are just index 0. Cost = 2 operations. Remove 3. BIT becomes [0, 1, 0]. Current pos = 0.
• Need to remove 4 (original index 1). Shift from 0 to 1. Active elements = 1. Cost = 1 operation. Total operations = $3 + 2 + 1 = 6$.

Common mistakes candidates make

The most common mistake is writing a literal Queue and simulating the shift and push operations. While logically sound, the array size can be up to $10^5$, meaning the queue simulation will severely Time Limit Exceed. Another mistake when using the mathematical approach is mishandling the "wrap-around" logic when the next smallest element's original index is physically behind your current conceptual position in the array.

Interview preparation tip

To excel at the Make Array Empty coding problem, you must understand how a Binary Indexed Tree acts as a dynamic frequency counter. Practice writing a BIT that can add(index, val) and query(left, right). This allows you to instantly answer the question "How many items are still left in the array between my current pointer and my destination pointer?" in $O(\log N)$ time.