Sponsored
Sponsored
This approach leverages the frequency count of each number to determine the minimum number of operations needed. We will iterate over the frequency list and for each number, calculate the possible number of operations (either removing two or three elements at a time).
Time Complexity: O(n), where n is the length of the array, as we are iterating through the array and frequencies. Space Complexity: O(n) for storing the frequency count.
1import java.util.HashMap;
2
3public class Solution {
4 public int minOperations(int[] nums) {
5 HashMap<Integer, Integer> freq = new HashMap<>();
6 for (int num : nums) {
7 freq.put(num, freq.getOrDefault(num, 0) + 1);
8 }
9 int operations = 0;
10 for (int count : freq.values()) {
11 if (count == 1) return -1;
12 operations += (count + 2) / 3;
13 }
14 return operations;
15 }
16}Java's HashMap is used to track frequencies. For each frequency, if it is not possible to remove either pairs or triples, i.e., count equals one, it's impossible to remove and the method returns -1. By using (count + 2) / 3, we essentially find the ceiling of count divided by three, giving us the minimal operations required per number.
This approach targets optimizing operations by prioritizing pair removals wherever possible, then triples. The main idea is to use as many pair removals as possible, and only use triples to fill gaps that pairs cannot cover fully.
Time Complexity: O(n), both for listing and iterating through frequencies. Space Complexity: O(n) for the frequency map.
1import
This Java version follows a greedy pattern where frequency counts are adjusted using pair and triplet removals to achieve minimal operations by prioritizing larger removals with triplets first, pairs only when fitting in end cases.