Reduction Operations to Make the Array Elements Equal

Medium
1145.

Reduction Operations to Make the Array Elements Equal

Reduction Operations to Make the Array Elements Equal is a medium coding problem on arrays and sorting, asked in Amazon and Google interviews.

You repeatedly apply the following operation to nums until all its elements are equal:

  1. Find the largest value largest. If several elements share it, take the one with the smallest index i.
  2. Find nextLargest, the largest value strictly smaller than largest.
  3. 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^4
  • 1 <= nums[i] <= 5 * 10^4
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums
 * @return {number}
 */
var reductionOperations = function(nums) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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:

  1. Find the largest value largest. If several elements share it, take the one with the smallest index i.
  2. Find nextLargest, the largest value strictly smaller than largest.
  3. 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^4
  • 1 <= nums[i] <= 5 * 10^4

Hints for Reduction Operations to Make the Array Elements Equal

  1. Hint 1

    An element only ever steps down through the distinct values below it, one distinct value per operation.

  2. Hint 2

    So an element ends up costing exactly the number of distinct values that are smaller than it.

  3. 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

  1. Sort nums ascending.
  2. Keep levels, the number of distinct values seen strictly below the current element: increase it whenever a[i] != a[i - 1].
  3. Add levels to the answer for every element.
  4. 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 ops

Java

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