#1887

Medium

LeetCode Problem Workspace

Reduction Operations to Make the Array Elements Equal

Find the minimum number of operations to make all array elements equal by reducing the largest elements to the next smaller number.

array sorting

Problem Statement

You are given an integer array nums. Your goal is to perform operations to make all elements of the array equal. In each operation, you choose the largest element in the array and reduce it to the next smaller distinct element. You need to determine how many such operations are necessary to make all elements in nums equal.

Return the minimum number of operations to achieve the desired outcome. For example, in nums = [5, 1, 3], three operations are needed: reducing 5 to 3, then 3 to 1, and finally reducing 3 to 1.

Examples

Example 1

Input: nums = [5,1,3]

Output: 3

It takes 3 operations to make all elements in nums equal:

largest = 5 at index 0. nextLargest = 3. Reduce nums[0] to 3. nums = [3,1,3].
largest = 3 at index 0. nextLargest = 1. Reduce nums[0] to 1. nums = [1,1,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

All elements in nums are already equal.

Example 3

Input: nums = [1,1,2,2,3]

Output: 4

It takes 4 operations to make all elements in nums equal:

largest = 3 at index 4. nextLargest = 2. Reduce nums[4] to 2. nums = [1,1,2,2,2].
largest = 2 at index 2. nextLargest = 1. Reduce nums[2] to 1. nums = [1,1,1,2,2].
largest = 2 at index 3. nextLargest = 1. Reduce nums[3] to 1. nums = [1,1,1,1,2].
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

Solution Approach

Sort the Array

Start by sorting the array in ascending order. This will allow you to efficiently identify the largest and next largest elements for reduction.

Track Number of Operations

After sorting, count how many times each distinct number appears in the array. The number of operations needed is determined by the count of elements larger than each distinct number.

Minimize Operations

The goal is to minimize the operations, which is achieved by reducing the larger elements in the sorted array. Every time an element is reduced, adjust the count of remaining elements to minimize unnecessary operations.

Complexity Analysis

Metric	Value
Time	O(n \cdot \log{}n)
Space	O(\log n)

The time complexity of the solution is O(n log n) due to sorting the array, where n is the length of the array. The space complexity is O(log n) because of the space used for sorting and tracking the distinct elements during operations.

What Interviewers Usually Probe

Candidate efficiently utilizes sorting to reduce time complexity.
Candidate demonstrates a clear understanding of reducing elements and tracking operations.
Candidate ensures the solution is optimal by focusing on minimizing the number of operations.

Common Pitfalls or Variants

Common pitfalls

Not sorting the array before attempting to reduce elements.
Forgetting to track the number of operations correctly, leading to inefficient solutions.
Overcomplicating the problem by using unnecessary data structures or operations.

Follow-up variants

What if the array contains only one element?
How does the solution behave with arrays containing repeated elements?
How would the solution scale if the array had significantly more elements?

FAQ

How do I approach the "Reduction Operations to Make the Array Elements Equal" problem?

Start by sorting the array, then track the number of operations required to reduce elements by comparing the largest and next largest numbers.

What is the time complexity of the solution?

The time complexity is O(n log n), driven by the sorting step, where n is the length of the array.

What happens if the array already contains equal elements?

If all elements are already equal, no operations are needed, and the answer is 0.

What if the array contains only one element?

With a single element, no operations are needed, and the answer is 0.

Can the array contain duplicates?

Yes, the array can contain duplicates, and the solution must correctly handle reducing those duplicates to make the array elements equal.

terminal

Solution

Solution 1: Sorting

We first sort the array $\textit{nums}$, then iterate from the second element of the array. If the current element is not equal to the previous element, we increment $\textit{cnt}$, indicating the number of operations needed to reduce the current element to the minimum value. Then we add $\textit{cnt}$ to $\textit{ans}$ and continue to the next element.

1

2

3

4

5

6

7

8

9

class Solution:
    def reductionOperations(self, nums: List[int]) -> int:
        nums.sort()
        ans = cnt = 0
        for a, b in pairwise(nums):
            if a != b:
                cnt += 1
            ans += cnt
        return ans

Continue Practicing

#1889 minimum space wasted from packaging #1878 get biggest three rhombus sums in a grid #1877 minimize maximum pair sum in array