Code Implementation

class Solution:
    def reductionOperations(self, nums):
        nums.sort()
        res = 0
        prev_ops = 0
        for i in range(1, len(nums)):
            if nums[i] != nums[i-1]:
                prev_ops += 1
            res += prev_ops
        return res
      

class Solution {
public:
    int reductionOperations(vector& nums) {
        sort(nums.begin(), nums.end());
        int res = 0, prev_ops = 0;
        for (int i = 1; i < nums.size(); ++i) {
            if (nums[i] != nums[i-1]) {
                prev_ops++;
            }
            res += prev_ops;
        }
        return res;
    }
};
      

import java.util.Arrays;
class Solution {
    public int reductionOperations(int[] nums) {
        Arrays.sort(nums);
        int res = 0, prev_ops = 0;
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] != nums[i-1]) {
                prev_ops++;
            }
            res += prev_ops;
        }
        return res;
    }
}
      

var reductionOperations = function(nums) {
    nums.sort((a, b) => a - b);
    let res = 0, prev_ops = 0;
    for (let i = 1; i < nums.length; i++) {
        if (nums[i] !== nums[i-1]) {
            prev_ops++;
        }
        res += prev_ops;
    }
    return res;
};
      

Problem Description

Given an array of integers nums, you can perform an operation where you choose any element and decrease it to any strictly smaller value present in the array. The goal is to make all elements in nums equal using the minimum number of such operations.

• Each operation must decrease an element to a value already present in nums.
• You can perform the operation any number of times on any element.
• Return the minimum number of operations required to make all elements equal.
• Constraints: 1 <= nums.length <= 5 * 10^4, 1 <= nums[i] <= 10^5.

Thought Process

At first, it might seem like we need to simulate each operation, choosing which element to reduce at every step. However, this would be inefficient for large arrays. Instead, let's observe that each operation reduces an element to a smaller value already present in the array. Eventually, all elements must become the smallest value in the array.

Rather than performing each operation, we can focus on how many times each unique value (except the minimum) must be reduced to reach the minimum value. By sorting the array, we can track how many unique values there are and how many elements need to be reduced at each step. This leads to a more efficient and systematic approach.

Solution Approach

• Step 1: Sort the Array
  • Sorting groups equal values together and arranges them in ascending order.
• Step 2: Track Operations
  • Initialize two variables: res (the total operations) and prev_ops (the number of unique values seen so far, excluding the minimum).
  • Iterate through the array from the second element onwards.
  • Each time you encounter a new unique value (i.e., nums[i] != nums[i-1]), increment prev_ops.
  • For every element, add prev_ops to res. This represents the cumulative number of reductions needed for all elements greater than the minimum.
• Step 3: Return the Result
  • After processing, res will contain the minimum number of operations required.

This method works efficiently because it leverages the sorted order to count reductions by unique levels, rather than simulating each operation individually.

Example Walkthrough

Let's walk through an example with nums = [5, 1, 3, 3, 2].

1. Sort the Array: [1, 2, 3, 3, 5]
2. Initialize: res = 0, prev_ops = 0
3. Iterate:
   • i = 1: nums[1]=2 is not equal to nums[0]=1 → prev_ops = 1, res = 1
   • i = 2: nums[2]=3 is not equal to nums[1]=2 → prev_ops = 2, res = 3
   • i = 3: nums[3]=3 is equal to nums[2]=3 → prev_ops = 2, res = 5
   • i = 4: nums[4]=5 is not equal to nums[3]=3 → prev_ops = 3, res = 8
4. Result: res = 8

This means 8 operations are required to make all elements equal to 1.

Time and Space Complexity

• Brute-force approach:
  • Would involve repeatedly selecting and reducing elements, potentially O(n^2) time, as each operation could require scanning the array.
• Optimized approach (current solution):
  • Sorting the array: O(n log n)
  • Single pass through the array: O(n)
  • Total Time Complexity: O(n log n)
  • Space Complexity: O(1) extra space (or O(n) if sorting in-place is not allowed)

Summary

The key insight is that each unique value above the minimum requires a number of operations proportional to its frequency and its "distance" from the minimum. By sorting and counting unique values, we efficiently calculate the total operations needed without simulating each reduction. This turns a potentially slow brute-force problem into a fast, elegant solution using sorting and simple counting.