Formatted question description: https://leetcode.ca/all/1887.html
1887. Reduction Operations to Make the Array Elements Equal
Level
Medium
Description
Given an integer array nums
, your goal is to make all elements in nums
equal. To complete one operation, follow these steps:
- Find the largest value in
nums
. Let its index bei
(0-indexed) and its value belargest
. If there are multiple elements with the largest value, pick the smallesti
. - Find the next largest value in
nums
strictly smaller thanlargest
. Let its value benextLargest
. - Reduce
nums[i]
tonextLargest
.
Return the number of operations to make all elements in nums
equal.
Example 1:
Input: nums = [5,1,3]
Output: 3
Explanation: It takes 3 operations to make all elements in nums equal:
- largest = 5 at index 0. nextLargest = 3. Reduce nums[0] to 3. nums = [3,1,3].
- largest = 3 at index 0. nextLargest = 1. Reduce nums[0] to 1. nums = [1,1,3].
- largest = 3 at index 2. nextLargest = 1. Reduce nums[2] to 1. nums = [1,1,1].
Example 2:
Input: nums = [1,1,1]
Output: 0
Explanation: All elements in nums are already equal.
Example 3:
Input: nums = [1,1,2,2,3]
Output: 4
Explanation: It takes 4 operations to make all elements in nums equal:
- largest = 3 at index 4. nextLargest = 2. Reduce nums[4] to 2. nums = [1,1,2,2,2].
- largest = 2 at index 2. nextLargest = 1. Reduce nums[2] to 1. nums = [1,1,1,2,2].
- largest = 2 at index 3. nextLargest = 1. Reduce nums[3] to 1. nums = [1,1,1,1,2].
- largest = 2 at index 4. nextLargest = 1. Reduce nums[4] to 1. nums = [1,1,1,1,1].
Constraints:
1 <= nums.length <= 5 * 10^4
1 <= nums[i] <= 5 * 10^4
Solution
Use a tree map to store the elements and the number of occurrences in nums
. Each time find largest
which is the largest key in the tree map and nextLargest
which is the largest key that is less than largest
in the tree map, add the corresponding value of largest
to the number of operations and to the value of nextLargest
, and remove largest
from the tree map. Repeat the process until the tree map’s size is 1. Finally, return the number of operations.
class Solution {
public int reductionOperations(int[] nums) {
TreeMap<Integer, Integer> map = new TreeMap<Integer, Integer>();
for (int num : nums)
map.put(num, map.getOrDefault(num, 0) + 1);
int operations = 0;
while (map.size() > 1) {
int largest = map.lastKey();
int nextLargest = map.floorKey(largest - 1);
int curOperations = map.get(largest);
operations += curOperations;
map.remove(largest);
map.put(nextLargest, map.get(nextLargest) + curOperations);
}
return operations;
}
}