Reduction Operations to Make the Array Elements Equal
MedPrompt
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
Approaches
3 approaches with complexity analysis and trade-offs.
This approach directly simulates the process described in the problem. In a loop, we repeatedly find the largest element and the next largest element, perform the reduction, and count the operation. The loop terminates when all elements in the array become equal.
Algorithm
- Initialize
operations = 0. - Start an infinite loop.
- In each iteration, find the maximum value
maxVal, its first indexmaxIdx, and the minimum valueminValin the array. - If
maxValequalsminVal, all elements are equal, so break the loop. - Find the next largest value
nextLargestValstrictly smaller thanmaxVal. A simple way is to initializenextLargestValtominValand iterate through the array, updating it with any valuenumsuch thatnextLargestVal < num < maxVal. - Reduce the element at
maxIdxby settingnums[maxIdx] = nextLargestVal. - Increment
operations. - After the loop, return
operations.
Walkthrough
This method follows the problem description literally. It enters a loop that continues as long as the array's elements are not all equal. In each step of the loop, it performs a full scan to find the largest element and its index, and another scan to find the next largest element. Then, it performs the reduction and increments the operation count. This process is repeated until the array's maximum and minimum elements are the same.
class Solution { public int reductionOperations(int[] nums) { int operations = 0; while (true) { int maxVal = Integer.MIN_VALUE; int minVal = Integer.MAX_VALUE; int maxIdx = -1; for (int i = 0; i < nums.length; i++) { if (nums[i] > maxVal) { maxVal = nums[i]; maxIdx = i; } if (nums[i] < minVal) { minVal = nums[i]; } } if (maxVal == minVal) { break; // All elements are equal } int nextLargestVal = -1; for (int num : nums) { if (num < maxVal && num > nextLargestVal) { nextLargestVal = num; } } nums[maxIdx] = nextLargestVal; operations++; } return operations; }}Complexity
Time
O(Ops * N), where `Ops` is the total number of operations and `N` is the length of the array. Each operation requires O(N) time to find the largest and next largest values. The number of operations can be very large, leading to a very high overall time complexity that is not feasible for the given constraints.
Space
O(1), as the array is modified in-place and only a few extra variables are used.
Trade-offs
Pros
Simple to understand and implement as it directly models the problem statement.
Cons
Extremely inefficient due to repeated linear scans of the array inside a loop.
Will result in a 'Time Limit Exceeded' error for the given constraints.
A more efficient approach is to realize that the total number of operations depends on the counts and relative order of unique values, not their specific positions. By sorting the array, we can easily count the operations. The core idea is that for each "step up" in value in the sorted array, all subsequent elements will need one additional reduction operation.
Algorithm
- Sort the input array
numsin non-decreasing order. - Initialize a variable
totalOperationsto 0. - Iterate through the sorted array from the second element, i.e., from
i = 1ton-1. - In each iteration, compare
nums[i]withnums[i-1]. - If
nums[i] > nums[i-1], it signifies a step up to a new distinct value. All then-ielements fromnums[i]tonums[n-1]must be reduced at least one more time than the elements before. Therefore, addn-itototalOperations. - After the loop finishes,
totalOperationswill hold the result.
Walkthrough
The problem can be rephrased as: how many times do we need to reduce an element? An element x needs to be reduced as many times as there are unique values smaller than x in the array. Sorting the array nums allows us to process the numbers in increasing order. When we iterate through the sorted array, if we encounter a number nums[i] that is greater than the previous one nums[i-1], it means we have found a new, higher value. All elements from this point to the end of the array (n-i elements) belong to a "higher tier". To bring all these elements down to the level of nums[i-1], each of them requires one operation. Thus, we add n-i to our total count. We repeat this for every step up in value.
import java.util.Arrays; class Solution { public int reductionOperations(int[] nums) { Arrays.sort(nums); int n = nums.length; int totalOperations = 0; for (int i = 1; i < n; i++) { if (nums[i] > nums[i-1]) { // We have found a new distinct number. // All elements from index i to the end (n-i elements) // need to be reduced to match the previous element's level. // This accounts for one level of reduction for all these elements. totalOperations += (n - i); } } return totalOperations; }}Complexity
Time
O(N log N), dominated by the sorting step. The subsequent loop to count operations runs in O(N).
Space
O(log N) to O(N), depending on the space used by the sorting algorithm's implementation. For instance, Java's `Arrays.sort` for primitives uses a dual-pivot quicksort which takes O(log N) space on average.
Trade-offs
Pros
Much more efficient than simulation.
Correctly solves the problem within typical time limits.
Conceptually elegant.
Cons
The O(N log N) time complexity is not the most optimal, as a linear time solution exists.
This is the most efficient approach, leveraging the fact that the values in the array are within a limited range. Instead of sorting the entire array, we can count the frequency of each number. The total number of operations can then be calculated by considering the distinct numbers in increasing order.
Algorithm
- Create a frequency array
freqof size50002(since values are up to5 * 10^4) and initialize it to zeros. - Iterate through the input array
numsand populate thefreqarray with the counts of each number. - Initialize
totalOperations = 0andlevels = 0. Thelevelsvariable will track the number of unique values encountered so far. - Iterate through the
freqarray from index 1 to 50001. - If
freq[i]is greater than 0, it means the numberiexists in the input array. - For each occurrence of
i, it must be reducedlevelstimes (once for each smaller unique value). So, addlevels * freq[i]tototalOperations. - Increment
levelsas we have now processed another unique value. - After iterating through all possible values, return
totalOperations.
Walkthrough
The key insight is that an element with value x must be reduced once for every unique value smaller than x. If there are k unique values smaller than x, then every occurrence of x contributes k operations to the total. We can implement this by first counting the frequency of all numbers. Then, we iterate through the numbers in increasing order. We maintain a count of how many unique numbers we've seen so far (levels). When we encounter a new number i with frequency freq[i], we know that all freq[i] elements must be reduced levels times. We add levels * freq[i] to our total and then increment levels for the next distinct number.
class Solution { public int reductionOperations(int[] nums) { int[] freq = new int[50002]; // Values are 1 to 50000 for (int num : nums) { freq[num]++; } int totalOperations = 0; int levels = 0; for (int i = 1; i < freq.length; i++) { if (freq[i] > 0) { // For each number present, its contribution to the total operations // is its frequency multiplied by the number of smaller unique elements found so far. totalOperations += levels * freq[i]; levels++; } } return totalOperations; }}Complexity
Time
O(N + M), where N is the number of elements in `nums` and M is the range of values. It takes O(N) to build the frequency map and O(M) to iterate through it.
Space
O(M), where M is the maximum possible value in `nums`. We use an array of size M+2 to store frequencies.
Trade-offs
Pros
The most efficient solution with linear time complexity.
Avoids the O(N log N) cost of sorting.
Cons
Requires extra space proportional to the range of values, which might be a concern if the range is extremely large. However, it is fine for this problem's constraints.
Solutions
Solution
public class Solution { public int ReductionOperations ( int [] nums ) { Array . Sort ( nums ); int ans = 0 , up = 0 ; for ( int i = 1 ; i < nums . Length ; i ++) { if ( nums [ i ] != nums [ i - 1 ]) { up ++; } ans += up ; } return ans ; } }class Solution {public int reductionOperations(int[] nums) { Arrays.sort(nums); int ans = 0, cnt = 0; for (int i = 1; i < nums.length; ++i) { if (nums[i] != nums[i - 1]) { ++cnt; } ans += cnt; } return ans; }}/** * @param {number[]} nums * @return {number} */ var reductionOperations = function (nums) { nums.sort((a, b) => a - b); let [ans, cnt] = [0, 0]; for (let i = 1; i < nums.length; ++i) { if (nums[i] !== nums[i - 1]) { ++cnt; } ans += cnt; } return ans; };class Solution: def reductionOperations(self, nums: List[int]) -> int: nums . sort() ans = cnt = 0 for i, v in enumerate(nums[1:]): if v != nums[i]: cnt += 1 ans += cnt return ansclass Solution {public: int reductionOperations(vector<int> &nums) { sort(nums.begin(), nums.end()); int ans = 0, cnt = 0; for (int i = 1; i < nums.size(); ++i) { cnt += nums[i] != nums[i - 1]; ans += cnt; } return ans; }};Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.