Scale Engineer

Minimum Number of Operations to Make Array Empty

Med
#2567Time: O(N log N), where N is the length of the `nums` array. The sorting step dominates the time complexity. The subsequent linear scan to count elements takes O(N) time.Space: O(log N) to O(N). The space complexity depends on the sorting algorithm used. In Java, `Arrays.sort()` for primitive types uses a variant of Quicksort, which requires O(log N) space on average for the recursion stack, but can be O(N) in the worst case.
Patterns
GreedyCounting
Data structures
ArrayHash Table

Prompt

You are given a 0-indexed array nums consisting of positive integers.

There are two types of operations that you can apply on the array any number of times:

  • Choose two elements with equal values and delete them from the array.
  • Choose three elements with equal values and delete them from the array.

Return the minimum number of operations required to make the array empty, or -1 if it is not possible.

 

Example 1:

Input: nums = [2,3,3,2,2,4,2,3,4]
Output: 4
Explanation: We can apply the following operations to make the array empty:
- Apply the first operation on the elements at indices 0 and 3. The resulting array is nums = [3,3,2,4,2,3,4].
- Apply the first operation on the elements at indices 2 and 4. The resulting array is nums = [3,3,4,3,4].
- Apply the second operation on the elements at indices 0, 1, and 3. The resulting array is nums = [4,4].
- Apply the first operation on the elements at indices 0 and 1. The resulting array is nums = [].
It can be shown that we cannot make the array empty in less than 4 operations.

Example 2:

Input: nums = [2,1,2,2,3,3]
Output: -1
Explanation: It is impossible to empty the array.

 

Constraints:

  • 2 <= nums.length <= 105
  • 1 <= nums[i] <= 106

 

Note: This question is the same as 2244: Minimum Rounds to Complete All Tasks.

Approaches

2 approaches with complexity analysis and trade-offs.

This approach involves sorting the array first to group identical elements together. After sorting, we can iterate through the array once to count the frequency of each number and calculate the minimum operations required for each group.

Algorithm

  • Sort the input array nums to group identical elements together.
  • Initialize a variable totalOperations to 0.
  • Iterate through the sorted array from left to right.
  • For each unique element, count its occurrences. Let the count be c.
  • If c is 1, it's impossible to remove this element, so return -1.
  • To find the minimum operations for c elements, we should maximize the use of 3-element deletions. The number of operations can be calculated with the formula (c + 2) / 3.
  • Add the result to totalOperations.
  • Continue until all elements are processed.
  • Return totalOperations.

Walkthrough

The fundamental insight is that operations only apply to elements of equal value. By sorting the array, all identical elements become adjacent, which simplifies the process of counting them. We can then iterate through the sorted array, identify blocks of identical numbers, and for each block, calculate the minimum operations needed to clear it.

For a group of count identical elements:

  • If count is 1, it's impossible to clear, so we return -1.
  • Otherwise, we need to express count as 2*a + 3*b such that the total operations a + b is minimized. This is achieved by maximizing b (the number of 3-element deletions).
  • A concise mathematical formula to calculate the minimum operations for a given count > 1 is (count + 2) / 3 using integer division. This covers all cases:
    • If count % 3 == 0, ops = count / 3.
    • If count % 3 == 1 (e.g., 4), we need two 2-element ops. (4+2)/3 = 2.
    • If count % 3 == 2 (e.g., 5), we need one 3-element and one 2-element op. (5+2)/3 = 2.
import java.util.Arrays; class Solution {    public int minOperations(int[] nums) {        Arrays.sort(nums);        int totalOps = 0;        int i = 0;        while (i < nums.length) {            int j = i;            while (j < nums.length && nums[j] == nums[i]) {                j++;            }            int count = j - i;            if (count == 1) {                return -1;            }            totalOps += (count + 2) / 3;            i = j;        }        return totalOps;    }}

Complexity

Time

O(N log N), where N is the length of the `nums` array. The sorting step dominates the time complexity. The subsequent linear scan to count elements takes O(N) time.

Space

O(log N) to O(N). The space complexity depends on the sorting algorithm used. In Java, `Arrays.sort()` for primitive types uses a variant of Quicksort, which requires O(log N) space on average for the recursion stack, but can be O(N) in the worst case.

Trade-offs

Pros

  • Conceptually straightforward after realizing sorting helps group elements.

  • Can be implemented with a single pass after sorting.

Cons

  • The time complexity is dominated by the sorting step, making it less efficient than a hash map-based approach.

  • Sorting might require additional space depending on the algorithm used.

Solutions

class Solution {public  int minOperations(int[] nums) {    Map<Integer, Integer> count = new HashMap<>();    for (int num : nums) {

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem