Make Array Empty solution and explanation
Google
5 more videos on this problem
Leetcode biweekly 103 Solution l make array empty (hard) l HindiPawan Kumar Giri · 21:20 · 3K views
Make Array Empty | Biweekly Contest 103codingMohan · 31:51 · 2K views
2659. Make Array Empty (Leetcode Hard)Programming Live with Larry · 36:28 · 1K views
【每日一题】LeetCode 2659. Make Array EmptyHuifeng Guan · 20:08 · 839 views
2659 Make Array Empty (LeetCode Hard)WYCode · 9:00 · 425 views
Day 564: LeetCode Problem 2659. Make Array Empty - SwiftiOSxBank · 9:52 · 35 views
The problem
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 <= 105-109 <= nums[i] <= 109- All values in
numsare 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.
def iterative_example(n):
for i in range(n):
print(i, end=' ')
n = 10
iterative_example(n)public class IterativeExample {
public static void main(String[] args) {
int n = 10;
iterativeExample(n);
}
public static void iterativeExample(int n) {
for (int i = 0; i < n; i++) {
System.out.print(i + " ");
}
}
}#include <iostream>
void iterativeExample(int n) {
for (int i = 0; i < n; i++) {
std::cout << i << " ";
}
}
int main() {
int n = 10;
iterativeExample(n);
return 0;
}function iterativeExample(n) {
for (let i = 0; i < n; i++) {
process.stdout.write(i + ' ');
}
}
let n = 10;
iterativeExample(n);#include <stdio.h>
void iterativeExample(int n) {
for (int i = 0; i < n; i++) {
printf("%d ", i);
}
}
int main() {
int n = 10;
iterativeExample(n);
return 0;
}using System;
class IterativeExample {
static void Main() {
int n = 10;
iterativeExample(n);
}
static void iterativeExample(int n) {
for (int i = 0; i < n; i++) {
Console.Write(i + " ");
}
}
}This Python function uses a for loop to iterate through numbers from 0 to n-1 and print them.
Time Complexity: O(n)
Space Complexity: O(1)
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.
def recursive_example(n):
if n <= 0:
return
recursive_example(n - 1)
print(n-1, end=' ')
n = 10
recursive_example(n)public class RecursiveExample {
public static void main(String[] args) {
int n = 10;
recursiveExample(n);
}
public static void recursiveExample(int n) {
if (n <= 0) return;
recursiveExample(n - 1);
System.out.print((n-1) + " ");
}
}#include <iostream>
void recursiveExample(int n) {
if (n <= 0) return;
recursiveExample(n - 1);
std::cout << n-1 << " ";
}
int main() {
int n = 10;
recursiveExample(n);
return 0;
}function recursiveExample(n) {
if (n <= 0) return;
recursiveExample(n - 1);
process.stdout.write((n-1) + ' ');
}
let n = 10;
recursiveExample(n);#include <stdio.h>
void recursiveExample(int n) {
if (n <= 0) return;
recursiveExample(n - 1);
printf("%d ", n-1);
}
int main() {
int n = 10;
recursiveExample(n);
return 0;
}using System;
class RecursiveExample {
static void Main() {
int n = 10;
recursiveExample(n);
}
static void recursiveExample(int n) {
if (n <= 0) return;
recursiveExample(n - 1);
Console.Write(n-1 + " ");
}
}This Python function uses recursion to print numbers from 0 to n-1. The output is achieved in ascending order due to the recursive base-case first pattern.
Time Complexity: O(n)
Space Complexity: O(n) due to recursive call stack
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.
class BinaryIndexedTree {
private n: number;
private c: number[];
constructor(n: number) {
this.n = n;
this.c = Array(n + 1).fill(0);
}
public update(x: number, v: number): void {
while (x <= this.n) {
this.c[x] += v;
x += x & -x;
}
}
public query(x: number): number {
let s = 0;
while (x > 0) {
s += this.c[x];
x -= x & -x;
}
return s;
}
}
function countOperationsToEmptyArray(nums: number[]): number {
const pos: Map<number, number> = new Map();
const n = nums.length;
for (let i = 0; i < n; ++i) {
pos.set(nums[i], i);
}
nums.sort((a, b) => a - b);
const tree = new BinaryIndexedTree(n);
let ans = pos.get(nums[0])! + 1;
for (let k = 0; k < n - 1; ++k) {
const i = pos.get(nums[k])!;
const j = pos.get(nums[k + 1])!;
let d = j - i - (tree.query(j + 1) - tree.query(i + 1));
if (i > j) {
d += n - k;
}
ans += d;
tree.update(i + 1, 1);
}
return ans;
}type BinaryIndexedTree struct {
n int
c []int
}
func newBinaryIndexedTree(n int) *BinaryIndexedTree {
c := make([]int, n+1)
return &BinaryIndexedTree{n, c}
}
func (this *BinaryIndexedTree) update(x, delta int) {
for x <= this.n {
this.c[x] += delta
x += x & -x
}
}
func (this *BinaryIndexedTree) query(x int) int {
s := 0
for x > 0 {
s += this.c[x]
x -= x & -x
}
return s
}
func countOperationsToEmptyArray(nums []int) int64 {
n := len(nums)
pos := map[int]int{}
for i, x := range nums {
pos[x] = i
}
sort.Ints(nums)
tree := newBinaryIndexedTree(n)
ans := pos[nums[0]] + 1
for k := 0; k < n-1; k++ {
i, j := pos[nums[k]], pos[nums[k+1]]
d := j - i - (tree.query(j+1) - tree.query(i+1))
if i > j {
d += n - k
}
ans += d
tree.update(i+1, 1)
}
return int64(ans)
}Complexity comparison
| Approach | Complexity |
|---|---|
| Iterative Approach | Time Complexity: O(n) |
| Recursive Approach | Time Complexity: O(n) |
| Hash Table + Sorting + Fenwick Tree | – |
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 |
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.