How do you solve Make Array Empty on LeetCode?

Make Array Empty (LeetCode #2659) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n log n) time complexity and O(n) space complexity. Key insight: The order of removals is determined by the values in the array, not their positions.

What is the time complexity of Make Array Empty?

The optimal solution for Make Array Empty runs in O(n log n) time and uses O(n) space. The optimal solution runs in O(n log n) due to the sorting step, while the space complexity is O(n) for the index mapping.

What is the brute force solution for Make Array Empty?

The brute force approach for Make Array Empty is Brute Force, with O(n²) time complexity and O(1) space complexity. The brute force approach simulates the operations directly. We repeatedly check if the first element is the smallest and remove it, or move it to the end of the array. This is straightforward but inefficient. The optimal Optimal Solution approach improves this to O(n log n).

What are the interview tips for Make Array Empty?

Always consider if there's a way to optimize the simulation of operations. Think about how you can use data structures like maps to simplify tracking. Practice deriving formulas from operations to save time during interviews.

What are common mistakes when solving Make Array Empty?

Not recognizing that we can track indices instead of modifying the array. Overcomplicating the problem by trying to simulate every operation instead of deriving a formula.

#2659

Make Array Empty

Hard

ArrayBinary SearchGreedyBinary Indexed TreeSegment TreeSortingOrdered SetHash MapArray

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n log n)
Space	O(1)	O(n)

💡

Intuition

Time O(n log n)Space O(n)

The optimal solution leverages the fact that we can track the order of removals without actually modifying the array. By using a mapping of values to their indices, we can determine the number of operations needed efficiently.

⚙️

Algorithm

3 steps

1Step 1: Create a mapping of each number to its index.
2Step 2: Sort the numbers based on their values.
3Step 3: Iterate through the sorted list and calculate the number of operations needed based on the index positions.

solution.py7 lines

1def make_array_empty(nums):
2    index_map = {num: i for i, num in enumerate(nums)}
3    sorted_nums = sorted(nums)
4    operations = 0
5    for i in range(len(sorted_nums)):
6        operations += index_map[sorted_nums[i]] + 1 + i
7    return operations

ℹ

Complexity note: The optimal solution runs in O(n log n) due to the sorting step, while the space complexity is O(n) for the index mapping.

1The order of removals is determined by the values in the array, not their positions.
2Tracking indices allows us to compute the number of operations without physically modifying the array.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.