{x}
blog image

Reduction Operations to Make the Array Elements Equal

Given an integer array nums, your goal is to make all elements in nums equal. To complete one operation, follow these steps:

  1. Find the largest value in nums. Let its index be i (0-indexed) and its value be largest. If there are multiple elements with the largest value, pick the smallest i.
  2. Find the next largest value in nums strictly smaller than largest. Let its value be nextLargest.
  3. Reduce nums[i] to nextLargest.

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:
1. largest = 5 at index 0. nextLargest = 3. Reduce nums[0] to 3. nums = [3,1,3].
2. largest = 3 at index 0. nextLargest = 1. Reduce nums[0] to 1. nums = [1,1,3].
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:
1. largest = 3 at index 4. nextLargest = 2. Reduce nums[4] to 2. nums = [1,1,2,2,2].
2. largest = 2 at index 2. nextLargest = 1. Reduce nums[2] to 1. nums = [1,1,1,2,2].
3. largest = 2 at index 3. nextLargest = 1. Reduce nums[3] to 1. nums = [1,1,1,1,2].
4. largest = 2 at index 4. nextLargest = 1. Reduce nums[4] to 1. nums = [1,1,1,1,1].

 

Constraints:

  • 1 <= nums.length <= 5 * 104
  • 1 <= nums[i] <= 5 * 104

Solution Explanation: Reduction Operations to Make Array Elements Equal

This problem asks us to find the minimum number of operations required to make all elements in an integer array equal. Each operation involves finding the largest element, identifying the next largest distinct element, and then reducing the largest element to the value of the next largest.

The most efficient approach is to leverage sorting. Here's a breakdown of the solution:

1. Sorting:

The core idea is to sort the input array nums in ascending order. Sorting allows us to easily identify the largest element and the next largest distinct element in each iteration.

2. Iterative Counting:

After sorting, we iterate through the sorted array, starting from the second element (nums[1]). We maintain a counter cnt to track the number of operations.

  • For each element nums[i], we compare it to the previous element nums[i-1].
  • If nums[i] is different from nums[i-1], it means we've encountered a new distinct value. This requires additional operations to reduce all larger elements to this value. Therefore, we increment cnt.
  • The current value of cnt represents the number of operations needed to reduce the current element and all larger elements to the current element's value. We add cnt to the total number of operations (ans).

3. Return Value:

Finally, the accumulated ans represents the total number of operations needed to make all elements equal. We return this value.

Time Complexity Analysis:

  • Sorting the array takes O(n log n) time, where n is the length of the array.
  • The subsequent iteration takes O(n) time.
  • Therefore, the overall time complexity is dominated by the sorting step, resulting in O(n log n).

Space Complexity Analysis:

  • In-place sorting algorithms can be used, resulting in O(1) space complexity in some implementations. However, depending on the sorting algorithm used (e.g., merge sort), the space complexity could be O(log n) or O(n) in the worst case. Many implementations use O(log n) space for sorting.

Code Examples (Python and Java):

Python:

from itertools import pairwise
 
class Solution:
    def reductionOperations(self, nums: List[int]) -> int:
        nums.sort()
        ans = cnt = 0
        for a, b in pairwise(nums):  # Efficient pairwise comparison using itertools
            if a != b:
                cnt += 1
            ans += cnt
        return ans

Java:

import java.util.Arrays;
 
class Solution {
    public int reductionOperations(int[] nums) {
        Arrays.sort(nums);
        int ans = 0;
        int cnt = 0;
        for (int i = 1; i < nums.length; ++i) {
            if (nums[i] != nums[i - 1]) {
                cnt++;
            }
            ans += cnt;
        }
        return ans;
    }
}

The other languages (C++, Go, TypeScript, JavaScript, C#) follow a very similar structure, reflecting the core algorithm described above. The primary difference lies in the syntax and libraries used for sorting and iteration. The time and space complexity remain consistent across all implementations.