Make Array Empty - Solution & Explanation

Q: 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.

Q: 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.

Q: 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.

Q: 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).

Q: 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.

Q: 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).

Q: 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.

HardArray Binary Search Greedy Binary Indexed Tree16 min readAsked at: Google, Zepto

Practice this problem

Problem Statement

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.

Approach Overview

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 1: Iterative Approach

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.

Code

C C++Java Python C#JavaScript

C++

Java

Python

JavaScript

Complexity

Time Complexity: O(n)
Space Complexity: O(1)

Try this approach in the editor →

Approach 2: Recursive Approach

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.

Code

C C++Java Python C#JavaScript

C++

Java

Python

JavaScript

Complexity

Time Complexity: O(n)
Space Complexity: O(n) due to recursive call stack

Try this approach in the editor →

Approach 3: Hash Table + Sorting + Fenwick Tree

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.

Code

Python Java C++Go TypeScript

Python

Java

C++

TypeScript

Try this approach in the editor →

Approach 4: Default Approach

Code

Python

Try this approach in the editor →

Complexity Comparison

Approach	Complexity
Iterative Approach	Time Complexity: O(n) Space Complexity: O(1)
Recursive Approach	Time Complexity: O(n) Space Complexity: O(n) due to recursive call stack
Hash Table + Sorting + Fenwick Tree	—
Default Approach	—

Detailed Complexity Analysis

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

Video Solution

Leetcode biweekly 103 Solution l make array empty (hard) l Hindi • Pawan Kumar Giri • 3,024 views views

Watch 5 more video solutions →

Frequently Asked Questions

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.

Ready to solve this problem?

Practice Make Array Empty with our built-in code editor and test cases.

Practice on FleetCode

Two Sum

Median of Two Sorted Arrays

Problem Info

DifficultyHard

Acceptance26.8%

Approaches4

Reading time16 min

Asked at

Google Zepto

Practice this problem

Open in Editor

Problem Statement

Approach Overview

Approach 1: Iterative Approach

Code

Complexity

Approach 2: Recursive Approach

Code

Complexity

Approach 3: Hash Table + Sorting + Fenwick Tree

Code

Approach 4: Default Approach

Code

Complexity Comparison

Detailed Complexity Analysis

Video Solution

Frequently Asked Questions

Related Problems

Ready to solve this problem?

Problem Info

Table of Contents