2870. Minimum Number of Operations to Make Array Empty

MediumGreedyArrayHash TableCounting

Problem Description

You're provided with an array of positive integers, each of which has an index starting from 0. To make the array empty, you can perform two kinds of operations any number of times:

Select two elements with the same value and remove them from the array.
Select three elements with the same value and remove them from the array.

The goal is to find the minimum number of these operations needed to empty the entire array. If it's impossible to empty the array using these operations, the answer should be -1.

Intuition

To solve this problem efficiently, we need a way to keep track of how many times each element occurs in the array. A hash table is perfect for this, as it allows us to count the occurrences of each element quickly. Once we know the count of each element, we can use a greedy approach to solve the problem.

Using the greedy method, for each unique element in the array, we repeatedly perform the deletion operation that removes the most elements. Since removing three elements is better than removing two to minimize operations, we prefer to perform the operation of removing three elements whenever possible. If an element occurs only once, it's impossible to perform either operation, so we immediately know we must return -1.

For any element occurring a number of times greater than one, we can perform the deletion operation as many times as this formula allows: $\lfloor \frac{c+2}{3} \rfloor$ , where $c$ is the number of occurrences. This formula ensures we always perform the optimal number of three-element deletions while accounting for leftovers that might only allow for a two-element deletion.

Finally, we sum up the operations for all elements to get the minimum number of operations required. If any element's count is one, we return -1. If not, we return the total sum of operations.

Learn more about Greedy patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

Given a sorted array of integers and an integer called target, find the element that equals to the target and return its index. Select the correct code that fills the ___ in the given code snippet.

1def binary_search(arr, target):
2    left, right = 0, len(arr) - 1
3    while left ___ right:
4        mid = (left + right) // 2
5        if arr[mid] == target:
6            return mid
7        if arr[mid] < target:
8            ___ = mid + 1
9        else:
10            ___ = mid - 1
11    return -1
12

1public static int binarySearch(int[] arr, int target) {
2    int left = 0;
3    int right = arr.length - 1;
4
5    while (left ___ right) {
6        int mid = left + (right - left) / 2;
7        if (arr[mid] == target) return mid;
8        if (arr[mid] < target) {
9            ___ = mid + 1;
10        } else {
11            ___ = mid - 1;
12        }
13    }
14    return -1;
15}
16

1function binarySearch(arr, target) {
2    let left = 0;
3    let right = arr.length - 1;
4
5    while (left ___ right) {
6        let mid = left + Math.trunc((right - left) / 2);
7        if (arr[mid] == target) return mid;
8        if (arr[mid] < target) {
9            ___ = mid + 1;
10        } else {
11            ___ = mid - 1;
12        }
13    }
14    return -1;
15}
16

<=, left, right<, left, right<=, right, left<, right, left

I don’t know

Solution Approach

The solution implements a hash table using Python's Counter from the collections module, which creates a dictionary where each key is a unique element from the array, and its corresponding value is the count of how many times that element appears in the array.

The next step in the solution is to iterate over each unique element's count in the hash table. The iteration checks the count for each element:

If an element appears exactly once, (c == 1), the function immediately returns -1, since it's impossible to perform either of the two allowed deletion operations.
For other cases, where the count c is greater than one, it calculates the minimum number of operations needed to delete each element using the formula (c + 2) // 3. The addition of 2 before the integer division by 3 effectively rounds up to the nearest whole number that isn't greater than c / 3, allowing us to make the maximal use of the operation that removes three elements at a time.

After processing all elements, the solution sums up all individual minimum operation counts and returns the total as the answer. This way, it ensures the use of the most efficient deletions while coping with differing element counts.

In summary, the algorithm makes intelligent use of a hash table to count occurrences and applies a greedy strategy by maximizing the use of the more efficient three-element deletion where possible, and then taking the leftover element pairs—if any—for two-element deletions.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Which of these properties could exist for a graph but not a tree?

Contain cyclesThere are multiple ways to traverseConnectedHas no cycle

I don’t know

Example Walkthrough

Let us walk through an example to illustrate the solution approach:

Assume we are given the following array of positive integers: [3, 3, 3, 3, 3, 1, 1, 2, 2, 2, 2, 2].

Step 1: Count the occurrences of each unique element using a hash table (Counter in Python).

The counts would be: {3: 5, 1: 2, 2: 5}.

Step 2: Evaluate the possibility of removing the elements using the described operations:

For element 3, the count is 5. According to our formula, the minimum number of operations needed is (5 + 2) // 3 = 7 // 3 = 2. We can remove three '3s' in one operation and the remaining two '3s' in another operation.
For element 1, the count is 2. We can remove both '1s' using one operation of the second kind, as (2 + 2) // 3 = 4 // 3 = 1. If instead there was only one '1', we would have had to return -1 since it's impossible to remove a single occurrence.
For element 2, analogous to element 3, the count is 5. So, taking the formula (5 + 2) // 3, we get 7 // 3 = 2 operations for element 2 as well.

Step 3: Sum up all of the operations required.

The total minimum number of operations would be 2 (for 3s) + 1 (for 1s) + 2 (for 2s) = 5.

Therefore, for the given array [3, 3, 3, 3, 3, 1, 1, 2, 2, 2, 2, 2], the minimum number of operations required to empty the entire array is 5.

Solution Implementation

1from collections import Counter
2
3class Solution:
4    def minOperations(self, nums: List[int]) -> int:
5        # Create a counter object to count occurrences of each number in the list
6        num_counts = Counter(nums)
7      
8        # Initialize operations counter to 0
9        operations = 0
10      
11        for count in num_counts.values():
12            # If any number occurs only once, it's impossible to form a sequence,
13            # so return -1 according to the problem statement.
14            if count == 1:
15                return -1
16          
17            # Calculate the minimum number of operations needed to form a sequence
18            # Each operation can decrease a number by either 1 or 2.
19            # So the formula "(count + 2) // 3" is used to find the minimum operations 
20            # for each group of identical numbers, assuming the best action is taken.
21            operations += (count + 2) // 3
22      
23        # Return the total number of operations
24        return operations
25

1class Solution {
2    public int minOperations(int[] nums) {
3        // Create a map to store the frequencies of each number
4        Map<Integer, Integer> frequencyMap = new HashMap<>();
5        // Populate the map with the frequencies
6        for (int num : nums) {
7            frequencyMap.merge(num, 1, Integer::sum);
8        }
9
10        // Initialize operations counter
11        int operations = 0;
12      
13        // Iterate over the values in the frequency map
14        for (int frequency : frequencyMap.values()) {
15            // If the frequency is less than 2, it's not possible to perform operations.
16            if (frequency < 2) {
17                return -1;
18            }
19            // Calculate the remainder and quotient of dividing the frequency by 3
20            int remainder = frequency % 3;
21            int quotient = frequency / 3;
22          
23            // Use switch expression to determine the number of operations needed
24            switch (remainder) {
25                // If there is no remainder, the number of operations is equal to the quotient
26                case 0 -> operations += quotient;
27                // For any remainder, an additional operation is needed
28                default -> operations += quotient + 1;
29            }
30        }
31      
32        // Return the total numberOfOperations required
33        return operations;
34    }
35}
36

1#include <vector>
2#include <unordered_map>
3
4class Solution {
5public:
6    // Function to find the minimum number of operations required
7    int minOperations(std::vector<int>& nums) {
8        // Create a hash map to store the frequency of each number
9        std::unordered_map<int, int> frequencyMap;
10      
11        // Count the frequency of each number in the vector
12        for (int num : nums) {
13            ++frequencyMap[num];
14        }
15      
16        int operations = 0; // Initialize the number of operations to 0
17
18        // Iterate through the frequency map
19        for (auto& keyValue : frequencyMap) {
20            int count = keyValue.second;  // Get the frequency count
21
22            // If there's a number with less than 2 occurrences, we cannot perform the operation
23            if (count < 2) {
24                return -1;
25            }
26
27            // Find the minimum number of operations required
28            // The number of operations for each number is (count + 2) / 3
29            operations += (count + 2) / 3;
30        }
31
32        // Return the total number of operations needed
33        return operations;
34    }
35};
36

1function minOperations(nums: number[]): number {
2    // A map to store the frequency of each number in the `nums` array.
3    const frequencyMap: Map<number, number> = new Map();
4
5    // Populate the frequencyMap with the frequency of each number in the `nums` array.
6    for (const num of nums) {
7        frequencyMap.set(num, (frequencyMap.get(num) ?? 0) + 1);
8    }
9
10    // Initialize the minimum number of operations required.
11    let minOperationsRequired = 0;
12
13    // Iterate through the frequencyMap to calculate the total operations.
14    for (const frequency of frequencyMap.values()) {
15        // If any number occurs only once, it's not possible to form a strictly increasing sequence.
16        if (frequency < 2) {
17            return -1;
18        }
19
20        // Calculate the number of operations needed for the current frequency and add to the total.
21        // The operation is equivalent to divide by 3, round down, which is achieved by bitwise OR with 0.
22        minOperationsRequired += (Math.floor((frequency + 2) / 3));
23    }
24
25    // Return the minimum number of operations required to make the `nums` array strictly increasing.
26    return minOperationsRequired;
27}
28

Not Sure What to Study? Take the 2-min Quiz：

What is the space complexity of the following code?

1int sum(int n) {
2  if (n <= 0) {
3    return 0;
4  }
5  return n + sum(n - 1);
6}

O(1)O(log n)O(sqrt(n))O(n)

I don’t know

Time and Space Complexity

The given Python code snippet defines a function minOperations that aims to determine the minimum number of operations required to ensure that every number appears more than once in the given list nums.

Time Complexity

The time complexity of the function is O(n) where n is the length of the array nums. This is because the function iterates over the elements in nums just once in order to create the count dictionary using Counter(nums), which is O(n), and then iterates over the values of the count dictionary to calculate ans. In the worst case, all elements in nums are unique, meaning the count dictionary also has n entries and thereby iterating over the count.values() would take O(n).

Space Complexity

The space complexity of the function is O(n). This is due to the use of Counter(nums) which can potentially store each unique element from nums as a key, leading to a space usage proportional to the number of unique elements, which, in the worst case, can be as large as n.

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

Which algorithm is best for finding the shortest distance between two points in an unweighted graph?

Depth-First SearchBreadth-First SearchBinary SearchPriority Queue

I don’t know

Overview

Basic Data Structures

Basic Algorithms

Overview

Sorted Array

Implicitly Sorted Array

Advanced

Speedrun

Introduction

DFS on Tree

Binary Search Tree

Advanced

Combinatorial Search

Pruning

Additional States

Aggregation and Memoization

Dedup

Additional Practices

Speedrun

Introduction

BFS on Tree

Introduction

Vanilla BFS

Matrix as Graph

Implicit Graph

Directed Graph / Topological Sort

Weighted Graph

Minimum Spanning Tree

Speedrun

Introduction

Same Direction

Opposite Direction

Sliding Window

Prefix Sum

Cycle Finding

Advanced

Speedrun

Introduction

Top K

Moving Best

Multiple Heaps

Introduction

Grid

Dynamic number of subproblems

Interval

Dual-Sequence

Knapsack

Bitmask

Additional Practices

Disjoint Set Union | Union Find

Trie

Data Structure Design

Segment Tree

Interval

Monotonic Stack

Divide and Conquer

Line Sweep

Tree Traversal without Recursion

Greedy

Math

Matrix

Classics

Concepts

Projects

Amazon OA

Microsoft OA

Google OA

Twitter OA

Editorials

2870. Minimum Number of Operations to Make Array Empty

Problem Description

Intuition

Solution Approach

Example Walkthrough

Solution Implementation

Time and Space Complexity

Time Complexity

Space Complexity

Recommended Readings