# Reduction Operations to Make the Array Elements Equal
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/reduction-operations-to-make-the-array-elements-equal)
Canonical: https://scaleengineer.com/dsa/problems/reduction-operations-to-make-the-array-elements-equal
**Algorithms:** [Sorting](https://scaleengineer.com/algorithms/sorting)
**Data structures:** Array
---
## 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 in_ `nums` _equal_.

**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 * 104`
* `1 <= nums[i] <= 5 * 104`

# Approaches
## Brute-force Simulation
This approach directly simulates the process described in the problem. In a loop, we repeatedly find the largest element and the next largest element, perform the reduction, and count the operation. The loop terminates when all elements in the array become equal.
**Time:** O(Ops * N), where `Ops` is the total number of operations and `N` is the length of the array. Each operation requires O(N) time to find the largest and next largest values. The number of operations can be very large, leading to a very high overall time complexity that is not feasible for the given constraints. · **Space:** O(1), as the array is modified in-place and only a few extra variables are used.
**Pros:** Simple to understand and implement as it directly models the problem statement.
**Cons:** Extremely inefficient due to repeated linear scans of the array inside a loop.; Will result in a 'Time Limit Exceeded' error for the given constraints.
### Explanation
This method follows the problem description literally. It enters a loop that continues as long as the array's elements are not all equal. In each step of the loop, it performs a full scan to find the largest element and its index, and another scan to find the next largest element. Then, it performs the reduction and increments the operation count. This process is repeated until the array's maximum and minimum elements are the same.

```java
class Solution {
    public int reductionOperations(int[] nums) {
        int operations = 0;
        while (true) {
            int maxVal = Integer.MIN_VALUE;
            int minVal = Integer.MAX_VALUE;
            int maxIdx = -1;

            for (int i = 0; i < nums.length; i++) {
                if (nums[i] > maxVal) {
                    maxVal = nums[i];
                    maxIdx = i;
                }
                if (nums[i] < minVal) {
                    minVal = nums[i];
                }
            }

            if (maxVal == minVal) {
                break; // All elements are equal
            }

            int nextLargestVal = -1;
            for (int num : nums) {
                if (num < maxVal && num > nextLargestVal) {
                    nextLargestVal = num;
                }
            }

            nums[maxIdx] = nextLargestVal;
            operations++;
        }
        return operations;
    }
}
```
### Algorithm
- Initialize `operations = 0`.
- Start an infinite loop.
- In each iteration, find the maximum value `maxVal`, its first index `maxIdx`, and the minimum value `minVal` in the array.
- If `maxVal` equals `minVal`, all elements are equal, so break the loop.
- Find the next largest value `nextLargestVal` strictly smaller than `maxVal`. A simple way is to initialize `nextLargestVal` to `minVal` and iterate through the array, updating it with any value `num` such that `nextLargestVal < num < maxVal`.
- Reduce the element at `maxIdx` by setting `nums[maxIdx] = nextLargestVal`.
- Increment `operations`.
- After the loop, return `operations`.

## Sorting-based Approach
A more efficient approach is to realize that the total number of operations depends on the counts and relative order of unique values, not their specific positions. By sorting the array, we can easily count the operations. The core idea is that for each "step up" in value in the sorted array, all subsequent elements will need one additional reduction operation.
**Time:** O(N log N), dominated by the sorting step. The subsequent loop to count operations runs in O(N). · **Space:** O(log N) to O(N), depending on the space used by the sorting algorithm's implementation. For instance, Java's `Arrays.sort` for primitives uses a dual-pivot quicksort which takes O(log N) space on average.
**Pros:** Much more efficient than simulation.; Correctly solves the problem within typical time limits.; Conceptually elegant.
**Cons:** The O(N log N) time complexity is not the most optimal, as a linear time solution exists.
### Explanation
The problem can be rephrased as: how many times do we need to reduce an element? An element `x` needs to be reduced as many times as there are unique values smaller than `x` in the array. Sorting the array `nums` allows us to process the numbers in increasing order. When we iterate through the sorted array, if we encounter a number `nums[i]` that is greater than the previous one `nums[i-1]`, it means we have found a new, higher value. All elements from this point to the end of the array (`n-i` elements) belong to a "higher tier". To bring all these elements down to the level of `nums[i-1]`, each of them requires one operation. Thus, we add `n-i` to our total count. We repeat this for every step up in value.

```java
import java.util.Arrays;

class Solution {
    public int reductionOperations(int[] nums) {
        Arrays.sort(nums);
        int n = nums.length;
        int totalOperations = 0;
        for (int i = 1; i < n; i++) {
            if (nums[i] > nums[i-1]) {
                // We have found a new distinct number.
                // All elements from index i to the end (n-i elements)
                // need to be reduced to match the previous element's level.
                // This accounts for one level of reduction for all these elements.
                totalOperations += (n - i);
            }
        }
        return totalOperations;
    }
}
```
### Algorithm
- Sort the input array `nums` in non-decreasing order.
- Initialize a variable `totalOperations` to 0.
- Iterate through the sorted array from the second element, i.e., from `i = 1` to `n-1`.
- In each iteration, compare `nums[i]` with `nums[i-1]`.
- If `nums[i] > nums[i-1]`, it signifies a step up to a new distinct value. All the `n-i` elements from `nums[i]` to `nums[n-1]` must be reduced at least one more time than the elements before. Therefore, add `n-i` to `totalOperations`.
- After the loop finishes, `totalOperations` will hold the result.

## Optimal Approach using Counting
This is the most efficient approach, leveraging the fact that the values in the array are within a limited range. Instead of sorting the entire array, we can count the frequency of each number. The total number of operations can then be calculated by considering the distinct numbers in increasing order.
**Time:** O(N + M), where N is the number of elements in `nums` and M is the range of values. It takes O(N) to build the frequency map and O(M) to iterate through it. · **Space:** O(M), where M is the maximum possible value in `nums`. We use an array of size M+2 to store frequencies.
**Pros:** The most efficient solution with linear time complexity.; Avoids the O(N log N) cost of sorting.
**Cons:** Requires extra space proportional to the range of values, which might be a concern if the range is extremely large. However, it is fine for this problem's constraints.
### Explanation
The key insight is that an element with value `x` must be reduced once for every unique value smaller than `x`. If there are `k` unique values smaller than `x`, then every occurrence of `x` contributes `k` operations to the total. We can implement this by first counting the frequency of all numbers. Then, we iterate through the numbers in increasing order. We maintain a count of how many unique numbers we've seen so far (`levels`). When we encounter a new number `i` with frequency `freq[i]`, we know that all `freq[i]` elements must be reduced `levels` times. We add `levels * freq[i]` to our total and then increment `levels` for the next distinct number.

```java
class Solution {
    public int reductionOperations(int[] nums) {
        int[] freq = new int[50002]; // Values are 1 to 50000
        for (int num : nums) {
            freq[num]++;
        }

        int totalOperations = 0;
        int levels = 0;
        for (int i = 1; i < freq.length; i++) {
            if (freq[i] > 0) {
                // For each number present, its contribution to the total operations
                // is its frequency multiplied by the number of smaller unique elements found so far.
                totalOperations += levels * freq[i];
                levels++;
            }
        }
        return totalOperations;
    }
}
```
### Algorithm
- Create a frequency array `freq` of size `50002` (since values are up to `5 * 10^4`) and initialize it to zeros.
- Iterate through the input array `nums` and populate the `freq` array with the counts of each number.
- Initialize `totalOperations = 0` and `levels = 0`. The `levels` variable will track the number of unique values encountered so far.
- Iterate through the `freq` array from index 1 to 50001.
- If `freq[i]` is greater than 0, it means the number `i` exists in the input array.
- For each occurrence of `i`, it must be reduced `levels` times (once for each smaller unique value). So, add `levels * freq[i]` to `totalOperations`.
- Increment `levels` as we have now processed another unique value.
- After iterating through all possible values, return `totalOperations`.

# Solutions
### CSharp

```csharp
public class Solution { public int ReductionOperations ( int [] nums ) { Array . Sort ( nums ); int ans = 0 , up = 0 ; for ( int i = 1 ; i < nums . Length ; i ++) { if ( nums [ i ] != nums [ i - 1 ]) { up ++; } ans += up ; } return ans ; } }
```

### Java

```java
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;
  }
}

```

### JavaScript

```javascript
/** * @param {number[]} nums * @return {number} */ var reductionOperations =
  function (nums) {
    nums.sort((a, b) => a - b);
    let [ans, cnt] = [0, 0];
    for (let i = 1; i < nums.length; ++i) {
      if (nums[i] !== nums[i - 1]) {
        ++cnt;
      }
      ans += cnt;
    }
    return ans;
  };

```

### Python

```python
class Solution:
    def reductionOperations(self, nums: List[int]) -> int: nums . sort() ans = cnt = 0 for i, v in enumerate(nums[1:]): if v != nums[i]: cnt += 1 ans += cnt return ans

```

### CPP

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

```