Is Make Array Empty easy or hard?

Make Array Empty is classified as a Hard problem because it requires recognizing that array rotations can be converted into range-count queries using data structures like Fenwick Trees or ordered sets.

How to solve Make Array Empty in O(n log n)?

Sort elements by value while keeping their original indices. Maintain a Fenwick Tree storing active positions. For each next smallest element, query how many indices remain between the previous pointer and the target index, handling circular wrap when needed, then mark the index as removed.

What is the best approach for Make Array Empty?

The most efficient approach sorts elements by value and uses a Fenwick Tree (Binary Indexed Tree) to count how many elements remain between indices during circular traversal. Each removal becomes a range query plus an update, resulting in O(n log n) time and O(n) space.

What data structure is used in Make Array Empty?

The optimal solution uses a Binary Indexed Tree (Fenwick Tree) or sometimes an ordered set / segment tree to track which indices remain in the array. These structures support fast range counting and updates in O(log n).

What is the time complexity of Make Array Empty?

The optimal solution runs in O(n log n) time. Sorting the elements by value takes O(n log n), and each Fenwick Tree query or update also takes O(log n) across n elements.

Make Array Empty Python or Java solution approach?

Python and Java solutions typically implement the same algorithm: sort value-index pairs, maintain a Fenwick Tree for active indices, perform range queries to count rotations, and update the structure after each removal. The complexity remains O(n log n).

Is Make Array Empty asked at Google, Amazon, or Meta?

Problems involving circular traversal and Fenwick Tree range counting frequently appear in interviews at companies like Google, Amazon, and Meta. Variants testing Binary Indexed Trees, ordered sets, or index compression are common in senior-level algorithm interviews.

Description Hints 4 Solution Video 21:20

2659. Make Array Empty

Hard27.4% acceptance2 companies

You are given an integer array nums 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 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 <= 10⁵
-10⁹<= nums[i] <= 10⁹
All values in nums are distinct.

Asked at 2 companies

Zepto

Google

Topics

Hints open one at a time

Hint 1

Understand the order in which the indices are removed from the array.

Hint 2

We don’t really need to delete or move the elements, only the array length matters.

Hint 3

Upon removing an index, decide how many steps it takes to move to the next one.

Hint 4

Use a data structure to speed up the calculation.

21:20

Still stuck?Read 3 approaches, or watch a walkthrough.

Open solution

LanguageLoading editor…

1class Solution:
2    def countOperationsToEmptyArray(self, nums: List[int]) -> int:
3        

Starter codePython 3Spaces: 4

Examples

Case 1Case 2Case 3

Input

[3,4,-1]

Input

[1,2,4,3]

Input

[1,2,3]

Your code is saved on this device.Solution