Minimum Number of Operations to Make Array Empty

Medium
700.

Minimum Number of Operations to Make Array Empty

Minimum Number of Operations to Make Array Empty is a medium coding problem on hash table, greedy and counting, asked in Amazon, Google and Swiggy interviews.

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
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums
 * @return {number}
 */
var minOperationsEmpty = function(nums) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Minimum Number of Operations to Make Array Empty — Solution

Minimum Number of Operations to Make Array Empty solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.

Minimum Number of Operations to Make Array Empty is a medium coding problem on hash table, greedy and counting, asked in Amazon, Google and Swiggy interviews.

  • 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

Hints for Minimum Number of Operations to Make Array Empty

  1. Hint 1

    Values never mix, so each distinct value is an independent subproblem: empty a pile of f identical items using twos and threes.

  2. Hint 2

    A pile of size 1 is impossible; every other size is achievable.

  3. Hint 3

    Using as many threes as possible is optimal, and the count works out to ceil(f / 3).

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

Java

public static int minOperationsEmpty(int[] nums) {
    Map<Integer, Integer> count = new HashMap<>();
    for (int x : nums) count.put(x, count.getOrDefault(x, 0) + 1);
    int ops = 0;
    for (int f : count.values()) {
        if (f == 1) return -1;
        ops += (f + 2) / 3;
    }
    return ops;
}

C++

int minOperationsEmpty(vector<int>& nums) {
    unordered_map<int, int> count;
    for (int x : nums) count[x]++;
    int ops = 0;
    for (auto& e : count) {
        if (e.second == 1) return -1;
        ops += (e.second + 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#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 439 hash table problems · the whole catalogue

Learn the technique: Hashing: Hash Maps and Hash Sets · Greedy Algorithms