Reduction Operations to Make the Array Elements Equal - Solution & Explanation
Problem Statement
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
numsstrictly 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: 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 * 1041 <= nums[i] <= 5 * 104
Approach Overview
Problem Overview: You are given an array of integers. In one operation, you pick the largest value and reduce it to the next smaller distinct value in the array. The goal is to compute the minimum number of operations required to make all elements equal.
Approach 1: Sorting and Iteration (Time: O(n log n), Space: O(1))
Sort the array so equal values are grouped and larger numbers appear later. While scanning the sorted array from left to right, each time you encounter a new distinct value, every element to its right will eventually require one additional reduction step. Track the index i and whenever nums[i] != nums[i-1], add i to the total operations. The insight: each distinct level of value introduces another layer of reductions for all larger elements. Sorting simplifies the comparison logic and avoids repeatedly simulating operations.
This approach works well in practice because the algorithm becomes a single pass after sorting. The implementation is concise and uses only constant extra space beyond the input array. The main cost comes from sorting, which takes O(n log n). See more patterns like this in sorting and array problems.
Approach 2: Counting and Aggregating (Time: O(n log k), Space: O(k))
Instead of sorting the entire array, count the frequency of each distinct value using a map or counting structure. Let k be the number of unique values. Sort the unique keys and process them from smallest to largest. Maintain a running count of how many elements are greater than the current value. Each time you move to the next larger value level, all elements above it require one additional reduction operation.
The key idea is aggregating reductions by value groups rather than by individual elements. Frequencies allow you to compute how many elements participate in each reduction layer. This reduces repeated work and keeps the algorithm efficient when the number of unique values is small. The complexity becomes O(n) to build the frequency map plus O(k log k) to sort unique values.
Recommended for interviews: The sorting and iteration approach is typically expected. It is simple, easy to reason about, and directly models how reduction layers accumulate across distinct values. Interviewers often want to see the insight that each new distinct value contributes operations equal to the number of elements already processed. The counting approach demonstrates stronger optimization thinking when discussing alternatives.
Approach 1: Approach 1: Sorting and Iteration
To solve this problem, we can first sort the array. After sorting, for each distinct number except the smallest one, count how many times smaller numbers need to be stepped up to equal the larger ones. Iterate over the sorted array and accumulate these steps until all numbers are equal.
In this C implementation, we use the qsort function to sort the array. Then, we iterate through the sorted array, counting distinct elements. Each time a new distinct element is found, it represents a level of operations needed to equalize numbers, accumulated into 'operations'.
Complexity
Time Complexity: O(n log n) due to sorting, Space Complexity: O(1) as sorting is done in place.
Approach 2: Approach 2: Counting and Aggregating
This approach involves counting the duplicates of each number without explicitly sorting. By iterating from the maximum value to the minimum, we calculate how many numbers need to be converted at each step by leveraging the array structure and gaps between numbers.
We maintain a count array for each potential value of the elements in nums. From the largest possible value, we calculate the cumulative operations needed by summing through the stored counts for all numbers greater than the current one.
Complexity
Time Complexity: O(n + k) where k is the maximum possible value in nums, Space Complexity: O(k) for the count array.
Approach 3: Sorting
We first sort the array nums, then iterate from the second element of the array. If the current element is not equal to the previous element, we increment cnt, indicating the number of operations needed to reduce the current element to the minimum value. Then we add cnt to ans and continue to the next element.
The time complexity is O(n times log n), and the space complexity is O(log n). Here, n is the length of the array nums.
Code
Python
Java
C++
Go
TypeScript
JavaScript
C#
Complexity Comparison
| Approach | Complexity |
|---|---|
| Approach 1: Sorting and Iteration | Time Complexity: O(n log n) due to sorting, Space Complexity: O(1) as sorting is done in place. |
| Approach 2: Counting and Aggregating | Time Complexity: O(n + k) where k is the maximum possible value in nums, Space Complexity: O(k) for the count array. |
| Sorting | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Sorting and Iteration | O(n log n) | O(1) | General case. Simple implementation and commonly expected in interviews. |
| Counting and Aggregating | O(n log k) | O(k) | When the number of distinct values is much smaller than n and frequency aggregation is convenient. |
Video Solution
Reduction Operations to Make the Array Elements Equal | Intuition | Leetcode-1887 • codestorywithMIK • 4,635 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Reduction Operations to Make the Array Elements Equal easy or hard?
Reduction Operations to Make the Array Elements Equal Python/Java solution
How to solve Reduction Operations to Make the Array Elements Equal in O(n)?
What is the best approach for Reduction Operations to Make the Array Elements Equal?
Is Reduction Operations to Make the Array Elements Equal asked at Google/Amazon/Meta?
What data structure is used in Reduction Operations to Make the Array Elements Equal?
What is the time complexity of Reduction Operations to Make the Array Elements Equal?
Ready to solve this problem?
Practice Reduction Operations to Make the Array Elements Equal with our built-in code editor and test cases.
Practice on FleetCode