Get started

Minimum Number of Operations to Make Array Empty — Medium Problem & Solution

You may repeatedly remove two elements with equal value, or three elements with equal value.

  • Difficulty: Medium
  • Topics: Hash Table, Greedy, Counting
  • Asked at: Amazon, Google, Swiggy
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

You may repeatedly remove two elements with equal value, or three elements with equal value.

Return the minimum number of operations that empties the array, or -1 if it cannot be emptied.

Example 1

Input: nums = [2,3,3,2,2,4,2,3,4]
Output: 4
Explanation: Four 2s, three 3s and two 4s take 2 + 1 + 1 operations.

Example 2

Input: nums = [2,1,2,2,3,3]
Output: -1
Explanation: The single 1 can never be removed.

Example 3

Input: nums = [14,12,14,14,12,14,14,12,12,12,12,14,14,12,14,14,14,12,12]
Output: 7

Constraints

  • 2 <= nums.length <= 100000
  • 1 <= nums[i] <= 1000000

How to solve Minimum Number of Operations to Make Array Empty

Group by value and solve each pile independently. Emptying a pile of f items with moves of 2 and 3 takes ceil(f / 3) operations, and only f = 1 is impossible.

Approach

  1. Tally the frequency of each distinct value.
  2. If any frequency is exactly 1, return -1.
  3. Otherwise add ceil(f / 3) for every frequency and return the sum.

Why it works

Each operation removes at most 3 items, so at least ceil(f / 3) are needed. That many suffice: write f = 3q + r. For r = 0 use q threes; for r = 1 (and f >= 4) use q - 1 threes and two twos, which is q + 1 = ceil(f/3); for r = 2 use q threes and one two, again q + 1. Only f = 1 has no decomposition.

Complexity

  • Time — O(n)
  • Space — O(n)

Pitfalls

  • ceil(f / 3) in integer arithmetic is (f + 2) / 3, not f / 3 + 1.
  • Returning -1 only at the end after summing wastes work but is also fine; returning 0 for an impossible input is not.
  • Greedily using twos first is not optimal — threes remove more per operation.

Reference solution

Python

from typing import List

def minOperationsEmpty(nums: List[int]) -> int:
    count = {}
    for x in nums:
        count[x] = count.get(x, 0) + 1
    ops = 0
    for f in count.values():
        if f == 1:
            return -1
        ops += (f + 2) // 3
    return ops

JavaScript

var minOperationsEmpty = function(nums) {
    var count = {};
    for (var i = 0; i < nums.length; i++) {
        var k = String(nums[i]);
        count[k] = (count[k] === undefined ? 0 : count[k]) + 1;
    }
    var ops = 0;
    var keys = Object.keys(count);
    for (var j = 0; j < keys.length; j++) {
        var f = count[keys[j]];
        if (f === 1) return -1;
        ops += Math.floor((f + 2) / 3);
    }
    return ops;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 202 hash table problems · the whole catalogue