medium Minimum Number of Operations to Make Array Empty

Problem Statement

You are given an array nums consisting of positive integers.

You can perform below two operations on the array multiple times:

• Select two elements with equal values and delete them from the array.
• Select 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.

Examples

Example 1:

• Input: nums = [1, 3, 2, 1, 2, 2, 3]
• Expected Output: 3
• Justification: We can perform the following operations:
  • Remove the two 1s (one operation).
  • Remove the three 2s (second operation).
  • Remove the two 3s (third operation). Thus, the array can be emptied in 3 operations.

Example 2:

• Input: nums = [4, 4, 2, 5, 3, 2, 5, 3]
• Expected Output: 4
• Justification: We can perform operations such as removing pairs of 4, 2, 5, and 3 in successive steps, each taking one step. This results in the array being emptied in 4 operations.

Example 3:

• Input: nums = [7, 8, 7]
• Expected Output: -1
• Justification: It is not possible to make the array empty as we can't remove 8 by performing any of 2 operations.

Solution

To solve this problem, we start by counting the occurrences of each integer in the given array, which is crucial for determining the feasible operations we can perform. This counting process involves traversing the array once and maintaining a frequency count for each distinct element in a hash map or an object. The key insight here is that by knowing the exact count of each number, we can decide on the optimal combination of operations (removing pairs or triplets of numbers) to minimize the total number of operations required to empty the array. The decision to remove pairs or triplets is guided by the aim to perform the least number of operations, which directly depends on how these counts are distributed among the numbers in the array.

Once the counts are established, we iterates over these counts to calculate the total operations needed. For each element's count, if there is only one occurrence, the array cannot be made empty according to the rules, and we return -1. Otherwise, we employ a simple mathematical operation: divide each count by 3 and round up the result to determine the minimum number of operations required for each number. This approach ensures that we efficiently utilize the allowed operations to minimize the total count, leveraging the fact that removing three elements in one operation or two in another is the most efficient way to reduce the array size.

Step-by-Step Algorithm

1. Initialize a hash map or an object to store the count of each unique element in the input array.
2. Iterate over the input array, updating the count for each element in the hash map.
3. Initialize a variable to keep track of the total number of operations required.
4. Iterate over the counts stored in the hash map:
   • If any count is exactly 1, return -1 immediately, as it's impossible to remove this element through the given operations.
   • For each count, add to the total number of operations the result of dividing the count by 3 and rounding up. This calculation aligns with the allowed operations (removing either two or three elements of the same value at a time).
5. After processing all counts, return the total number of operations as the result.

Algorithm Walkthrough

Let's consider the Input [4, 4, 2, 5, 3, 2, 5, 3]

1. Count occurrences: The counts are {1: 2, 3: 2, 2: 3}.
2. Calculate operations for 1: Count is 2. Removing both 1s in one operation, total operations now are 1.
3. Calculate operations for 3: Count is 2. Removing both 3s in one operation, total operations increase to 2.
4. Calculate operations for 2: Count is 3. Removing all three 2s in one operation, total operations become 3.
5. No counts of 1 left: It's possible to make the array empty with the given operations.
6. Return total operations: The final answer is 3, as calculated, meaning the array can be emptied in 3 operations.

Code

import java.util.HashMap;

public class Solution {

  public int minOperations(int[] nums) {
    var elementCount = new HashMap<Integer, Integer>(); // Changed from 'counter' to 'elementCount' for clarity
    for (int num : nums) {
      elementCount.put(num, elementCount.getOrDefault(num, 0) + 1);
    }
    int totalOperations = 0; // Changed from 'ans' to 'totalOperations' for clarity
    for (int count : elementCount.values()) {
      if (count == 1) {
        return -1; // It's not possible to make the array empty
      }
      totalOperations += Math.ceil((double) count / 3);
    }
    return totalOperations;
  }

  public static void main(String[] args) {
    Solution solution = new Solution();
    System.out.println(
      solution.minOperations(new int[] { 1, 3, 2, 1, 2, 2, 3 })
    ); // Expected: 3
    System.out.println(
      solution.minOperations(new int[] { 4, 4, 2, 5, 3, 2, 5, 3 })
    ); // Expected: 4
    System.out.println(solution.minOperations(new int[] { 7, 8, 7 })); // Expected: -1
  }
}

Complexity Analysis

Time Complexity

• : This is because each element in the array nums is processed exactly once to count occurrences. The n here represents the total number of elements in the input array.
• The iteration over the hash map (or dictionary) to calculate the total operations has a complexity of , where u is the number of unique elements in the array. Since u <= n, this does not exceed in terms of the overall impact on time complexity.

Space Complexity

• : The space complexity is determined by the size of the hash map (or dictionary) used to count the occurrences of each unique element. In the worst case, where all elements are unique, this would be O(n), but typically u <= n, making the space complexity .