Reduction Operations to Make the Array Elements Equal Solution
Reduction Operations to Make the Array Elements Equal solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.
Reduction Operations to Make the Array Elements Equal is a medium coding problem on arrays and sorting, asked in Amazon and Google interviews.
- Difficulty: Medium
- Topics: Arrays, Sorting
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
You repeatedly apply the following operation to nums until all its elements are equal:
- Find the largest value
largest. If several elements share it, take the one with the smallest indexi. - Find
nextLargest, the largest value strictly smaller thanlargest. - Set
nums[i] = nextLargest.
Return the number of operations performed.
Example 1
Input: nums = [4,4,2]
Output: 2
Explanation: Each 4 is lowered to 2 in turn.
Example 2
Input: nums = [6,6,6]
Output: 0
Example 3
Input: nums = [1,2,2,3]
Output: 4
Explanation: `3 -> 2` once, then each of the three 2s becomes 1.
Constraints
1 <= nums.length <= 5 * 10^41 <= nums[i] <= 5 * 10^4
Hints for Reduction Operations to Make the Array Elements Equal
Hint 1
An element only ever steps down through the distinct values below it, one distinct value per operation.
Hint 2
So an element ends up costing exactly the number of distinct values that are smaller than it.
Hint 3
Sort the array and walk it, counting how many times the value has changed so far; add that count for each element.
How to solve Reduction Operations to Make the Array Elements Equal
Each operation moves one element down by exactly one distinct-value level, and every element must reach the minimum — so an element costs the number of distinct values below it.
Approach
- Sort
numsascending. - Keep
levels, the number of distinct values seen strictly below the current element: increase it whenevera[i] != a[i - 1]. - Add
levelsto the answer for every element. - Return the answer.
Why it works
nextLargest is the next distinct value below the current maximum, so an operation never skips a level. An element with k distinct values beneath it is lowered exactly k times before it equals the minimum; the order in which the operations happen does not change these per-element counts.
Complexity
- Time —
O(n log n) - Space —
O(1) beyond the sort
Pitfalls
- Counting the plain rank (index) of each element overcounts when values repeat — use distinct levels.
- Elements equal to the minimum cost nothing.
- The total is at most about n^2 / 2 for all-distinct values, roughly 1.25 * 10^9 at the bounds — still inside 32 bits.
Reference solution
Python
from typing import List
def reductionOperations(nums: List[int]) -> int:
a = sorted(nums)
ops = 0
levels = 0
for i in range(1, len(a)):
if a[i] != a[i - 1]:
levels += 1
ops += levels
return opsJava
public static int reductionOperations(int[] nums) {
int[] a = nums.clone();
Arrays.sort(a);
int ops = 0, levels = 0;
for (int i = 1; i < a.length; i++) {
if (a[i] != a[i - 1]) levels++;
ops += levels;
}
return ops;
}C++
int reductionOperations(vector<int>& nums) {
vector<int> a(nums);
sort(a.begin(), a.end());
int ops = 0, levels = 0;
for (size_t i = 1; i < a.size(); i++) {
if (a[i] != a[i - 1]) levels++;
ops += levels;
}
return ops;
}JavaScript
var reductionOperations = function(nums) {
var a = nums.slice().sort(function(x, y) { return x - y; });
var ops = 0, levels = 0;
for (var i = 1; i < a.length; i++) {
if (a[i] !== a[i - 1]) levels++;
ops += levels;
}
return ops;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Sorting Algorithms