Reduction Operations to Make the Array Elements Equal

Problem

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 innums equal.

Examples

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 * 10^4
• 1 <= nums[i] <= 5 * 10^4

Solution

Method 1 – Sort and Count Unique Levels

Intuition

Each time we reduce the largest value to the next largest, we perform an operation for every occurrence of the current largest. The total number of operations is the sum of the counts of all elements above the minimum, weighted by their position in the sorted unique list.

Approach

1. Sort the array.
2. For each unique value (from smallest to largest), count how many numbers are greater than it.
3. For each group, add the number of operations needed (which is the count of numbers before it in the sorted order).
4. Return the total operations.

Code

C++

class 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) {
            if (nums[i] != nums[i-1]) ++cnt;
            ans += cnt;
        }
        return ans;
    }
};

Go

import "sort"
func reductionOperations(nums []int) int {
    sort.Ints(nums)
    ans, cnt := 0, 0
    for i := 1; i < len(nums); i++ {
        if nums[i] != nums[i-1] {
            cnt++
        }
        ans += cnt
    }
    return ans
}

Java

import java.util.*;
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;
    }
}

Kotlin

class Solution {
    fun reductionOperations(nums: IntArray): Int {
        nums.sort()
        var ans = 0
        var cnt = 0
        for (i in 1 until nums.size) {
            if (nums[i] != nums[i-1]) cnt++
            ans += cnt
        }
        return ans
    }
}

Python

class Solution:
    def reductionOperations(self, nums: list[int]) -> int:
        nums.sort()
        ans = cnt = 0
        for i in range(1, len(nums)):
            if nums[i] != nums[i-1]:
                cnt += 1
            ans += cnt
        return ans

Rust

impl Solution {
    pub fn reduction_operations(mut nums: Vec<i32>) -> i32 {
        nums.sort();
        let mut ans = 0;
        let mut cnt = 0;
        for i in 1..nums.len() {
            if nums[i] != nums[i-1] { cnt += 1; }
            ans += cnt;
        }
        ans
    }
}

TypeScript

class Solution {
    reductionOperations(nums: number[]): number {
        nums.sort((a, b) => a - b);
        let ans = 0, cnt = 0;
        for (let i = 1; i < nums.length; ++i) {
            if (nums[i] !== nums[i-1]) ++cnt;
            ans += cnt;
        }
        return ans;
    }
}

Complexity

• ⏰ Time complexity: O(n log n), due to sorting the array.
• 🧺 Space complexity: O(1) (or O(n) if sorting is not in-place), as only a few variables are used after sorting.