Reduction Operations to Make the Array Elements Equal - Video Solutions

Problem Overview: You are given an array of integers. In one operation, you pick the largest value and reduce it to the next smaller distinct value in the array. The goal is to compute the minimum number of operations required to make all elements equal.

Approach 1: Sorting and Iteration (Time: O(n log n), Space: O(1))

Sort the array so equal values are grouped and larger numbers appear later. While scanning the sorted array from left to right, each time you encounter a new distinct value, every element to its right will eventually require one additional reduction step. Track the index i and whenever nums[i] != nums[i-1], add i to the total operations. The insight: each distinct level of value introduces another layer of reductions for all larger elements. Sorting simplifies the comparison logic and avoids repeatedly simulating operations.

This approach works well in practice because the algorithm becomes a single pass after sorting. The implementation is concise and uses only constant extra space beyond the input array. The main cost comes from sorting, which takes O(n log n). See more patterns like this in sorting and array problems.

Approach 2: Counting and Aggregating (Time: O(n log k), Space: O(k))

Instead of sorting the entire array, count the frequency of each distinct value using a map or counting structure. Let k be the number of unique values. Sort the unique keys and process them from smallest to largest. Maintain a running count of how many elements are greater than the current value. Each time you move to the next larger value level, all elements above it require one additional reduction operation.

The key idea is aggregating reductions by value groups rather than by individual elements. Frequencies allow you to compute how many elements participate in each reduction layer. This reduces repeated work and keeps the algorithm efficient when the number of unique values is small. The complexity becomes O(n) to build the frequency map plus O(k log k) to sort unique values.

Recommended for interviews: The sorting and iteration approach is typically expected. It is simple, easy to reason about, and directly models how reduction layers accumulate across distinct values. Interviewers often want to see the insight that each new distinct value contributes operations equal to the number of elements already processed. The counting approach demonstrates stronger optimization thinking when discussing alternatives.