Reduction Operations to Make the Array Elements Equal

Given an integer array nums, in one operation you find the largest element, find the next largest value strictly smaller than it, and replace all occurrences of that largest element with the next value. You keep doing this until every element is the same. Return the total number of operations performed.

This is LeetCode 1887: Reduction Operations to Make the Array Elements Equal, a medium problem that rewards you for thinking about what sorting reveals. Simulating the process directly works but is slow. Once you sort the array and count distinct value levels, the answer falls out in a single linear scan.

Why this problem matters

Sorting an array to expose structure is one of the most broadly useful patterns in algorithm design. Many problems that seem to require simulation or repeated passes can be solved in O(n log n) once you realize that sorted order makes the relevant quantities easy to compute.

This problem specifically trains you to think about "how many levels does each element need to descend?" Once you can answer that per element, you just sum them up. That same "count the levels" reasoning appears in problems about reducing values, merging intervals, and computing prefix sums over distinct groups. Getting comfortable translating a simulation into a counting argument is a skill that transfers everywhere.

The brute force approach

The most direct approach is to simulate the process exactly as described. Find the largest value, find the next smaller value, replace all occurrences of the largest, count one operation per replacement, and repeat until all elements are equal.

def reductionOperations_brute(nums):
    ops = 0
    while len(set(nums)) > 1:
        largest = max(nums)
        vals = sorted(set(nums))
        next_val = vals[vals.index(largest) - 1]
        for i in range(len(nums)):
            if nums[i] == largest:
                nums[i] = next_val
                ops += 1
    return ops

This works but it is slow. Each round scans the array to find the max, builds a set to find the next value, then scans again to do the replacements. In the worst case you have O(n) distinct values and each round processes all of them, giving O(n^2) time. For arrays up to 50,000 elements, that is too slow.

The key insight

Instead of simulating the process, think about it from each element's perspective. After sorting, the smallest element is already at the target value and needs zero operations. Each time you encounter a new distinct value (moving left to right through the sorted array), that value sits one "level" higher than the previous one. An element at level k needs k operations to be reduced all the way down to the minimum, because it must pass through each intermediate level one at a time.

So the algorithm is: sort the array, scan left to right, and maintain a counter called steps that increments every time the value changes from the previous element. For each element, add steps to the running total. That is the entire solution.

Walking through it step by step

Let's trace through nums = [5, 1, 3]. The expected answer is 3.

After sorting we get [1, 3, 5]. The first element (value 1) is already at the minimum, contributing 0. The second element (value 3) is one level above the minimum, contributing 1. The third element (value 5) is two levels above the minimum, contributing 2. The total is 0 + 1 + 2 = 3.

The complete solution

def reductionOperations(nums):
    nums.sort()
    total = 0
    steps = 0
    for i in range(1, len(nums)):
        if nums[i] != nums[i - 1]:
            steps += 1
        total += steps
    return total

Here is what each piece does:

1. Sort the array in ascending order. This groups equal values together and arranges them from smallest to largest.
2. Initialize total = 0 (the answer) and steps = 0 (the number of distinct levels above the minimum seen so far).
3. Scan from index 1 to n-1. Each time nums[i] differs from nums[i - 1], we have entered a new level, so increment steps. Then add steps to total, because this element must be reduced through steps levels to reach the minimum.
4. Return total.

Notice that duplicate values at the same level each contribute the same steps count. If there are three copies of value 3, all three contribute 1 operation each. The counter only increments when the value actually changes.

Complexity analysis

The sort dominates the time complexity. The linear scan afterward is O(n). Space depends on the sorting algorithm. Python's Timsort uses O(n) auxiliary space, but languages with in-place sorts can achieve O(1) extra space.

Building blocks

This problem is built on two reusable patterns that CodeBricks drills independently.

1. Sort to reveal structure

Many problems become trivial once the array is sorted. Sorting groups equal elements together, makes neighbor comparisons meaningful, and lets you compute cumulative properties in a single pass. Here, sorting turns a simulation problem into a counting problem. The same idea powers solutions for problems like Two Sum (with the two-pointer variant), 3Sum, Merge Intervals, and Meeting Rooms.

2. Counting distinct levels with a running counter

The technique of scanning a sorted array and incrementing a counter each time the value changes is a fundamental building block. It gives you the "rank" or "level" of each element in O(n) time. This pattern appears whenever you need to know how many distinct values precede the current one, or when you need to compute prefix counts over groups of equal elements.

Edge cases

Before submitting, make sure your solution handles these:

• All elements equal [4, 4, 4]: steps never increments because no value differs from the previous one. Total = 0. No operations needed.
• Already sorted ascending [1, 2, 3, 4]: each element introduces a new level. Total = 0 + 1 + 2 + 3 = 6.
• Already sorted descending [4, 3, 2, 1]: after sorting you get [1, 2, 3, 4], same as above. Total = 6.
• Two distinct values [1, 1, 5, 5]: sorted is [1, 1, 5, 5]. steps increments once at index 2. Total = 0 + 0 + 1 + 1 = 2.
• Single element [7]: the loop does not execute. Total = 0.
• Large array with many duplicates [3, 3, 3, 5, 5, 1]: sorted is [1, 3, 3, 3, 5, 5]. Steps increments at index 1 and index 4. Total = 0 + 1 + 1 + 1 + 2 + 2 = 7.

Common mistakes

1. Simulating the reduction process directly. The brute force simulation works but runs in O(n^2) for large inputs. Recognizing that sorting lets you count operations in one pass is the whole point of the problem.

2. Forgetting that duplicates each contribute separately. If three elements share the same value, each one needs to be reduced through the same number of levels. You must add steps for every element, not just once per distinct value.

3. Starting the scan at index 0 instead of index 1. The first element in the sorted array is the minimum. It contributes 0 operations and serves as the baseline. Starting at index 0 and comparing to a nonexistent nums[-1] leads to index errors or incorrect counts.

4. Incrementing steps for every element instead of only on value changes. The steps counter should only increase when nums[i] != nums[i - 1]. Incrementing it unconditionally would overcount operations for duplicates.

From understanding to recall

You have read the sorting plus level counting solution and it makes sense. One sort, one scan, one counter. But will you remember the details in an interview?

The critical pieces are: sort first, start scanning at index 1, increment steps only when the value changes (not for every element), and add steps to the total at every index. These are small details, but getting any one of them wrong produces a subtly incorrect answer.

Spaced repetition locks these details into long-term memory. You write the solution from scratch at increasing intervals until the pattern is automatic. When you see "reduce elements to equal" or "count operations to flatten an array," you immediately reach for sort plus level counting without hesitation.

Related posts

• Candy - Another problem where sorting reveals the structure
• Group Anagrams - Sorting as a canonicalization step
• Kth Largest Element - Understanding sorted order and element positioning

CodeBricks breaks the reduction operations problem into its sort-to-reveal-structure and level-counting building blocks, then drills them independently with spaced repetition. You type each piece from scratch until the pattern is automatic. When a sorting-based counting question shows up in your interview, you do not think about it. You just write it.