LeetCode 1887 - Reduction Operations to Make the Array Elements Equal

Difficulty: 🟡 Medium
Topics: Array, Sorting

Solution

Problem Understanding

This problem asks us to make all elements in an integer array equal by repeatedly reducing the largest elements to the next largest element in the array. The input is an array nums of integers, where each operation requires identifying the current largest element and reducing it to the value of the next largest element strictly smaller than it. The output is the total number of such operations needed until all elements are equal.

The constraints 1 <= nums.length <= 5 * 10^4 and 1 <= nums[i] <= 5 * 10^4 indicate that the array can be fairly large, so any naive approach that repeatedly scans the array to find the largest element could be too slow. Edge cases include arrays where all elements are initially equal, arrays with all distinct elements, or arrays with many duplicates.

The problem guarantees non-empty arrays with positive integers, which simplifies handling empty or zero-value arrays.

Approaches

Brute Force Approach

A brute force solution would repeatedly scan the array to find the largest element, then reduce it to the next largest. We would count each operation until all elements are equal. While this approach is correct, it is inefficient. Each operation requires finding the largest and second-largest elements, which is O(n) per operation. If the array contains many distinct elements, the total time complexity could be O(n^2), which is unacceptable for n up to 50,000.

Optimal Approach

The key observation is that the number of operations needed for each element is determined by its rank in the set of unique values. If we sort the array, each element only needs to be reduced to the next smaller unique value repeatedly. Specifically, the largest unique element contributes 0 operations for itself initially, the second largest contributes count of elements greater than it operations, and so on. We can compute the total operations by summing contributions of each unique element based on their rank in the sorted unique array.

This avoids repeatedly scanning the array, and instead relies on counting occurrences of each value and iterating over sorted unique values.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n^2)	O(1)	Repeatedly scan array to reduce largest elements
Optimal	O(n log n)	O(n)	Sort unique values and count operations based on ranks

Algorithm Walkthrough

Count the frequency of each number in the array using a hash map. This helps us quickly determine how many elements are greater than any given element.
Extract the unique elements from the array and sort them in ascending order. Sorting is required to establish the "next largest" relationships between numbers.
Initialize a variable operations to 0. This will accumulate the total number of reduction operations.
Initialize a variable runningSum to 0. This represents the cumulative count of elements greater than the current number.
Iterate over the sorted unique elements starting from the second smallest element:
For each element, add runningSum to operations. This accounts for the number of times elements larger than the current element must be reduced to it.
Update runningSum by adding the frequency of the current element. This ensures the next iteration considers the cumulative effect of all larger elements.
Return operations as the final result.

Why it works: By iterating over sorted unique elements and tracking cumulative counts of larger elements, we ensure each element's contribution to the total operations is counted exactly once. The algorithm leverages the fact that the reduction operations always move elements toward smaller values along the sorted unique sequence.

Python Solution

from typing import List
from collections import Counter

class Solution:
    def reductionOperations(self, nums: List[int]) -> int:
        freq = Counter(nums)
        unique_nums = sorted(freq)
        operations = 0
        running_sum = 0
        for num in unique_nums[1:]:
            running_sum += freq[unique_nums[unique_nums.index(num)-1]]
            operations += running_sum
        return operations

Explanation: We first count frequencies using Counter. We sort the unique numbers and iterate from the second smallest element. For each element, we add the cumulative sum of frequencies of all larger elements to operations and update running_sum to include the previous element’s count. This mirrors the reduction operations described in the problem.

Go Solution

import (
    "sort"
)

func reductionOperations(nums []int) int {
    freqMap := make(map[int]int)
    for _, num := range nums {
        freqMap[num]++
    }
    
    uniqueNums := make([]int, 0, len(freqMap))
    for num := range freqMap {
        uniqueNums = append(uniqueNums, num)
    }
    
    sort.Ints(uniqueNums)
    
    operations := 0
    runningSum := 0
    
    for i := 1; i < len(uniqueNums); i++ {
        prevNum := uniqueNums[i-1]
        runningSum += freqMap[prevNum]
        operations += runningSum
    }
    
    return operations
}

Explanation: The Go implementation mirrors the Python logic. We use a map to count frequencies, collect and sort unique numbers, and compute the operations using a cumulative sum. Differences include explicit map handling and indexing, but the algorithmic logic is identical.

Worked Examples

Example 1: `nums = [5,1,3]`

Sorted unique numbers: [1,3,5]

Frequencies: {1:1, 3:1, 5:1}

Step	Element	Running Sum	Operations
1	3	1	1
2	5	2	3

Total operations = 3

Example 2: `nums = [1,1,1]`

Sorted unique numbers: [1]

No operations needed as all elements are already equal.

Example 3: `nums = [1,1,2,2,3]`

Sorted unique numbers: [1,2,3]

Frequencies: {1:2, 2:2, 3:1}

Step	Element	Running Sum	Operations
1	2	2	2
2	3	4	4

Total operations = 4

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n log n)	Counting frequencies is O(n), sorting unique elements is O(k log k), where k ≤ n
Space	O(n)	Frequency map and unique element list both require O(n) space

The sorting dominates the complexity when the number of unique elements is large.

Test Cases

# Provided examples
assert Solution().reductionOperations([5,1,3]) == 3  # mix of elements
assert Solution().reductionOperations([1,1,1]) == 0  # all elements equal
assert Solution().reductionOperations([1,1,2,2,3]) == 4  # duplicates

# Edge cases
assert Solution().reductionOperations([1]) == 0  # single element
assert Solution().reductionOperations([2,2,2,2,2]) == 0  # all elements equal, multiple
assert Solution().reductionOperations([5,4,3,2,1]) == 10  # strictly decreasing
assert Solution().reductionOperations([1,2,3,4,5]) == 10  # strictly increasing
assert Solution().reductionOperations([1,1,2,3,3,4,4,4,5]) == 18  # mixed duplicates

Test	Why
`[5,1,3]`	Simple mix of elements
`[1,1,1]`	All elements equal, no operations
`[1,1,2,2,3]`	Multiple duplicates and reductions
`[1]`	Single element, minimal edge case
`[2,2,2,2,2]`	Multiple duplicates, no operations
`[5,4,3,2,1]`	Strictly decreasing order
`[1,2,3,4,5]`	Strictly increasing order
`[1,1,2,3,3,4,4,4,5]`	Mixed duplicates with multiple reductions

Edge Cases

Single element array: Arrays of length 1 require zero operations. The algorithm correctly handles this because the unique element list will have length 1, and the loop from index 1 will not execute.

All elements equal: If all elements are the same, no reductions are needed. The cumulative sum mechanism correctly results in zero operations.

Large number of duplicates: Arrays with many repeated values can stress naive approaches. Our algorithm handles duplicates efficiently using the frequency map and cumulative sum without scanning the array multiple times.

Strictly increasing or decreasing arrays: These cases ensure that each element contributes maximum operations. Our algorithm correctly sums the contributions by counting elements greater than the current element.

Edge numeric values: Arrays with elements at the maximum constraint value, e.g., 50,000, are handled correctly, as Python and Go support integers up to these ranges without overflow.