Problem Description

You are given an integer array nums. Your goal is to make all elements in the array equal through a series of reduction operations.

Each operation works as follows:

1. Find the largest value in nums. If multiple elements have the same largest value, choose the one with the smallest index i.

2. Find the next largest value in nums that is strictly smaller than the largest value. Call this value nextLargest.

3. Reduce nums[i] (the largest element) to nextLargest.

You need to return the total number of operations required to make all elements in nums equal.

For example, if nums = [5, 1, 3]:

• Operation 1: Largest is 5 (at index 0), next largest is 3, so reduce 5 to 3. Array becomes [3, 1, 3].
• Operation 2: Largest is 3 (at index 0), next largest is 1, so reduce 3 to 1. Array becomes [1, 1, 3].
• Operation 3: Largest is 3 (at index 2), next largest is 1, so reduce 3 to 1. Array becomes [1, 1, 1].
• Total operations: 3

The key insight is that each distinct value above the minimum will need to be reduced step by step through all intermediate values until it reaches the minimum value.

Intuition

Let's think about what happens when we perform these operations. Each operation reduces the largest element to the next largest distinct value. This means elements can only decrease, never increase.

Consider a sorted array like [1, 1, 2, 2, 2, 3, 4]. The value 4 needs to be reduced to 3, then to 2, then to 1 - that's 3 operations. The value 3 needs to be reduced to 2, then to 1 - that's 2 operations. The three 2's each need to be reduced to 1 - that's 1 operation each.

The key observation is that if we sort the array, we can see exactly how many "levels" each element needs to drop. The number of levels is determined by how many distinct values are smaller than it.

When we traverse the sorted array from left to right, every time we encounter a new distinct value, all elements from that point onward will need one additional operation to eventually reach the minimum value.

For example, in [1, 1, 2, 2, 2, 3, 4]:

• At index 2, we see value 2 (different from 1), so cnt becomes 1. All remaining elements need at least 1 operation.
• At index 5, we see value 3 (different from 2), so cnt becomes 2. All remaining elements need at least 2 operations.
• At index 6, we see value 4 (different from 3), so cnt becomes 3. This element needs 3 operations.

By accumulating cnt for each position, we get the total number of operations: elements at positions 2,3,4 contribute 1 each, element at position 5 contributes 2, and element at position 6 contributes 3, giving us 1+1+1+2+3 = 8 total operations.

Learn more about Sorting patterns.

Solution Approach

The solution uses a sorting approach combined with a counting technique to efficiently calculate the total number of operations.

Step 1: Sort the array
First, we sort nums in ascending order. This allows us to easily identify distinct values and understand how many levels each element needs to drop.

Step 2: Count operations using pairwise comparison
We initialize two variables:

• ans: accumulates the total number of operations
• cnt: tracks the current number of distinct values seen so far (excluding the minimum)

Step 3: Iterate through consecutive pairs
Using pairwise(nums), we examine each consecutive pair (a, b) in the sorted array:

• If a != b, it means we've encountered a new distinct value, so we increment cnt. This represents that all elements from this point onward need one additional operation to reach the minimum.
• For each position, we add cnt to ans. This is because the element at the current position needs cnt operations to be reduced to the minimum value.

Implementation walkthrough:

nums.sort()  # Sort array: e.g., [5,1,3] becomes [1,3,5]
ans = cnt = 0
for a, b in pairwise(nums):  # Compare consecutive elements
    if a != b:  # New distinct value found
        cnt += 1  # Increment the level counter
    ans += cnt  # Add operations needed for current element
return ans

For example, with nums = [1, 3, 5] after sorting:

• Compare (1,3): different, so cnt = 1, ans = 0 + 1 = 1
• Compare (3,5): different, so cnt = 2, ans = 1 + 2 = 3
• Total operations: 3

The time complexity is O(n log n) due to sorting, and the space complexity is O(1) if we don't count the sorting space.

Example Walkthrough

Let's walk through the solution with nums = [5, 1, 3]:

Step 1: Sort the array

• Original: [5, 1, 3]
• After sorting: [1, 3, 5]

Step 2: Initialize variables

• ans = 0 (total operations counter)
• cnt = 0 (distinct value level counter)

Step 3: Process consecutive pairs

We'll examine each consecutive pair in the sorted array:

Pair 1: (1, 3)

• Compare: 1 != 3 → We found a new distinct value
• Update: cnt = 0 + 1 = 1 (one level above minimum)
• Add operations: ans = 0 + 1 = 1
• This means the element at index 1 (value 3) needs 1 operation to reach value 1

Pair 2: (3, 5)

• Compare: 3 != 5 → We found another new distinct value
• Update: cnt = 1 + 1 = 2 (two levels above minimum)
• Add operations: ans = 1 + 2 = 3
• This means the element at index 2 (value 5) needs 2 operations to reach value 1

Result: Total operations = 3

Verification with actual operations:

1. Original array: [5, 1, 3]
   • Reduce 5→3: [3, 1, 3] (1 operation)
2. Array: [3, 1, 3]
   • Reduce first 3→1: [1, 1, 3] (1 operation)
3. Array: [1, 1, 3]
   • Reduce last 3→1: [1, 1, 1] (1 operation)

Total: 3 operations ✓

The key insight: In the sorted array [1, 3, 5], the value 3 is one level above the minimum (1), so it needs 1 operation. The value 5 is two levels above the minimum (through 3, then to 1), so it needs 2 operations. Total: 1 + 2 = 3.

Solution Implementation

Time and Space Complexity

The time complexity is O(n × log n), where n is the length of the array nums. This is dominated by the sorting operation nums.sort(), which takes O(n × log n) time. The subsequent iteration through the sorted array using pairwise(nums) takes O(n) time, but this is absorbed by the larger sorting complexity.

The space complexity is O(log n). While the pairwise() function creates an iterator that generates pairs on-the-fly without storing them all in memory (taking O(1) space), the sorting operation typically uses O(log n) space for the recursive call stack in algorithms like Timsort (Python's default sorting algorithm). The variables ans and cnt only require O(1) additional space.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall 1: Misunderstanding the Operation Count Logic

The Problem: A common mistake is thinking that each element needs to be reduced by the difference between its value and the minimum value. For instance, if we have [1, 3, 5], one might incorrectly calculate:

• Element 3 needs (3-1) = 2 operations
• Element 5 needs (5-1) = 4 operations
• Total = 6 operations

This is wrong because the reduction must go through intermediate values step by step.

The Correct Understanding: Each element must be reduced through every distinct value between itself and the minimum:

• Element 5 must go: 5 → 3 → 1 (2 operations)
• Element 3 must go: 3 → 1 (1 operation)
• Total = 3 operations

Solution: The code correctly handles this by counting distinct values (distinct_count) and accumulating operations. Each time we encounter a new distinct value, we know all subsequent elements need one additional operation level.

Pitfall 2: Forgetting to Sort the Array

The Problem: Without sorting, it's difficult to identify distinct values and count operations efficiently. Processing an unsorted array would require repeatedly finding the maximum and next maximum values, leading to inefficient O(n²) complexity.

Solution: Always sort the array first. This enables linear traversal to count distinct values and calculate operations in O(n) time after the O(n log n) sort.

Pitfall 3: Off-by-One Errors in Counting

The Problem: Some implementations might incorrectly initialize distinct_count = 1 or add the count before checking if values are different, leading to overcounting operations.

# Incorrect approach
distinct_count = 1  # Wrong initialization
for prev_num, curr_num in pairwise(nums):
    total_operations += distinct_count  # Adding before checking
    if prev_num != curr_num:
        distinct_count += 1

Solution: Initialize distinct_count = 0 and increment it only when encountering a new distinct value. The order matters: check for distinct values first, update the count, then add to total operations.

Pitfall 4: Handling Edge Cases

The Problem: Not considering edge cases like:

• Array with all identical elements (should return 0)
• Array with only one element (should return 0)
• Array already sorted vs unsorted

Solution: The current implementation handles these cases naturally:

• If all elements are equal, prev_num != curr_num is never true, so distinct_count stays 0, returning 0
• For single element arrays, pairwise() returns no pairs, so the loop doesn't execute, returning 0
• Sorting ensures consistent behavior regardless of initial order