1887. Reduction Operations to Make the Array Elements Equal

Problem Description

The goal of the given problem is to perform a series of operations on an integer array nums until all the elements in the array are equal. An operation consists of three steps:

Find the largest value in the array, denoted as largest. If there are multiple elements with the largest value, we select the one with the smallest index i.
Find the next largest value that is strictly smaller than largest, denoted as nextLargest.
Replace the element at index i with nextLargest.

The problem asks us to return the number of operations required to make all elements in the array equal.

Quick Interview Experience

Help others by sharing your interview experience

Have you seen this problem before?

Intuition

To solve this problem, a key insight is that sorting the array will make it easier to track the reductions needed to equalize all elements. After sorting:

The largest element will be at the end of the sorted array, and the next largest will be right before it.
Subsequent steps involve moving down the sorted array and reducing the largest remaining element to the next largest.

By maintaining a sorted array, we can avoid repeatedly searching for the largest and next largest elements, thus optimizing the process.

Here's the process of the solution approach:

First, sort the array in non-decreasing order. This will ensure that each subsequent value from left to right will be greater than or equal to the previous one.
Then, iterate through the sorted array from the second element onwards, comparing the current element with the previous one:
- If they are the same, no operation is needed for this step, but we keep a count of how many times we would have had to reduce other elements to the current value.
- If the current value is larger, it means an operation was needed to get from the previous value to this one. We increment the operation count (cnt) and add it to the total answer (ans) because we will need that number of operations for each element that needs to be reduced to this current value.

Each increment of cnt represents a step in which all larger elements need one more operation to reach equality, and by adding cnt to the answer every time, you account for the operations needed to reduce all larger elements to the current one. The final answer is the total count of operations needed.

Learn more about Sorting patterns.

Solution Approach

The given Python solution follows a straightforward approach, leveraging simple algorithms and data structure manipulation to arrive at the answer. Here's a breakdown of how the solution is implemented:

Algorithm: The primary algorithm used here is sorting, which is an integral part of the solution. Python's built-in sorting is typically implemented as Timsort, which is efficient for the given task.
Data Structures: The solution primarily works with the list data structure in Python, which is essentially an array.
Pattern Used: The approach follows a pattern similar to counting, where for each unique value in the sorted array, we track how many operations are needed if we want to reduce the larger numbers to this number.

Let's examine the implementation step by step:

The nums list is sorted in non-decreasing order using nums.sort().
A for loop with enumerate is set to iterate through the array (excluding the first element, as there’s nothing to compare it to). Two variables are maintained:
- cnt: This keeps count of how many different operations are performed. It starts at 0 because no operations are performed at the first element.
- ans: This accumulates the total number of operations.
Inside the loop, each element v at index i (where i starts from 1 since we skipped the first element) is compared to its predecessor (nums[i]):
- If v equals the previous element (nums[i]), it means that no new operation is needed for v to become equal to the previous element (as it's already equal).
- If v is different (meaning it is larger since the array is sorted), then we found a new value that wasn't seen before. Therefore, we increment cnt by 1 since all occurrences of this new value would require an additional operation to be reduced to the previous smaller value.
After assessing each pair of elements, the value of cnt (which indicates the cumulative operations required to reduce the current and all previous larger values) is added to ans.
Finally, after the loop completes, ans holds the total number of operations required to make all elements equal and is returned as the result.

Here is the critical part of the code with added comments for clarity:

class Solution:
    def reductionOperations(self, nums: List[int]) -> int:
        nums.sort()  # [Sorting](/problems/sorting_summary) the array in non-decreasing order
        ans = cnt = 0  # Initialize counters to zero
        for i, v in enumerate(nums[1:]):  # Iterate through the array, skipping the first element
            if v != nums[i]:  # If current element is greater than the previous one (not equal)
                cnt += 1  # Increment the number of operations needed
            ans += cnt  # Add to total answer
        return ans  # Return the total

Notice that the enumerate function in the loop is used with the sublist nums[1:] which effectively shifts the indices of the enumerated items by one, meaning nums[i] actually refers to the element immediately preceding v.

To summarize, the use of sorting simplifies the identification of unique values that require operations, and the counting mechanism properly aggregates the steps needed to reach the desired equal state of the nums array.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's walk through a small example using the solution approach described above. Consider the following array of integers:

nums = [5, 1, 3, 3, 5]

We want to perform operations until all the elements in this array are equal, following the given steps: sort the array, identify the largest and next largest elements, and replace occurrences of the largest element with the next largest until the array is homogenized.

Here is the breakdown of how we apply our algorithm to the example:

Sort the array:
```
Sort the `nums` array: nums = [1, 3, 3, 5, 5]
```
After sorting the array in non-decreasing order, we can easily identify which elements need to be replaced in each operation.
Initial setup:
- Initialize our counters: cnt = 0 and ans = 0.
- Start iterating from the second element of nums (since we need to compare each element with its previous one).
Iteration:
- Compare 3 with 1. Since 3 is greater, we found a new value. So, cnt becomes 1 and ans becomes 1.
- Compare the second 3 with the first 3. They are equal, no new operation is needed, cnt stays 1 and ans becomes 2.
- Compare 5 with 3. 5 is greater, so cnt becomes 2 (indicating each 5 needs two operations to become a 3) and ans becomes 4.
- Compare the second 5 with the first 5. They are equal, so cnt stays 2 and ans becomes 6.
Final count:
- After the loop concludes, ans = 6, which represents the total number of operations needed to make all elements equal.

Through this walkthrough, we find that a total of 6 operations are required to make all elements of the array [5, 1, 3, 3, 5] equal. The sorted form, [1, 3, 3, 5, 5], simplifies the identification of which elements need to be replaced, and our counting mechanism effectively calculates the necessary steps to achieve uniformity across the array.

Solution Implementation

1class Solution:
2    def reductionOperations(self, nums: List[int]) -> int:
3        # Sort the list of numbers in non-decreasing order.
4        nums.sort()
5      
6        # Initialize the number of operations required to 0.
7        operations_count = 0
8      
9        # This variable keeps track of the number of different elements encountered.
10        different_elements_count = 0
11      
12        # Iterate through the sorted list of numbers, starting from the second element.
13        for i in range(1, len(nums)):
14            # Check if the current number is different from the previous one,
15            # as only unique numbers will contribute to new operations.
16            if nums[i] != nums[i - 1]:
17                # If it's different, increment the count of different elements.
18                different_elements_count += 1
19          
20            # Add the count of different elements to the total operations count.
21            # This accounts for the operations required to reduce this number
22            # to the next lower number in the list.
23            operations_count += different_elements_count
24      
25        # Return the total count of reduction operations required.
26        return operations_count
27
28# Usage example:
29# solution = Solution()
30# result = solution.reductionOperations([5,1,3])
31# print(result) # Output would be the number of operations required.
32

1class Solution {
2    public int reductionOperations(int[] nums) {
3        // Sort the array in non-decreasing order
4        Arrays.sort(nums);
5      
6        // Initialize a variable to count the number of operations needed
7        int operationsCount = 0;
8        // Initialize a variable to count the distinct elements processed
9        int distinctElementsCount = 0;
10      
11        // Iterate over the sorted array, starting from the second element
12        for (int i = 1; i < nums.length; ++i) {
13            // Check if the current element is different from the previous one
14            if (nums[i] != nums[i - 1]) {
15                // Increment the distinct elements count since a new value has been encountered
16                ++distinctElementsCount;
17            }
18            // Add the current distinct elements count to the total operations
19            // This represents making the current element equal to the previous one
20            operationsCount += distinctElementsCount;
21        }
22      
23        // Return the total count of reduction operations required
24        return operationsCount;
25    }
26}
27

1// This solution utilizes sorting and then counts the steps required to reduce elements to make all equal.
2class Solution {
3public:
4    int reductionOperations(vector<int>& nums) {
5        // Sort the nums vector in non-decreasing order
6        sort(nums.begin(), nums.end());
7
8        // Initialize the answer and count variables
9        int operations = 0; // Number of operations needed to make all elements equal
10        int stepCounter = 0; // Number of steps needed to decrement to the next lower number
11
12        // Iterate through the sorted vector starting from index 1
13        for (int i = 1; i < nums.size(); ++i) {
14            // If the current number is different from the one before it,
15            // it means a new decrement step is needed.
16            if (nums[i] != nums[i - 1]) {
17                stepCounter++;
18            }
19
20            // Add the number of steps to the total operations
21            operations += stepCounter;
22        }
23
24        // Return the total number of operations required
25        return operations;
26    }
27};
28

1function reductionOperations(nums: number[]): number {
2    // Sort the given array in non-decreasing order.
3    nums.sort((a, b) => a - b);
4
5    // Initialize a variable `result` to keep the count of operations.
6    let result = 0;
7    // Initialize a variable `countDistinct` to track the number of distinct elements encountered.
8    let countDistinct = 0;
9
10    // Iterate through the sorted array, starting from the second element.
11    for (let i = 1; i < nums.length; ++i) {
12        // If the current element is different from the previous one, increment the distinct count.
13        if (nums[i] !== nums[i - 1]) {
14            countDistinct++;
15        }
16      
17        // Add the current count of distinct elements to the result.
18        // This represents the number of operations needed for each element to reach the previous smaller element.
19        result += countDistinct;
20    }
21  
22    // Return the total number of operations needed to make all elements equal.
23    return result;
24}
25

Time and Space Complexity

Time Complexity

The given code has two main operations: sorting the nums array and iterating through the sorted array to calculate the ans.

Sorting the array has a time complexity of O(n log n), where n is the length of the nums list. This is because the Timsort algorithm, which is the sorting algorithm used by Python's sort() function, typically has this complexity.
The for loop iterates through the array once, which gives a time complexity of O(n) for this part of the code.

Since the sorting operation is likely to dominate the overall time complexity, the final time complexity of the code is O(n log n).

Space Complexity

The space complexity concerns the amount of extra space or temporary space that an algorithm uses.

The nums.sort() operation sorts the list in-place, which means it does not require additional space proportional to the size of the input (nums). Thus, this part of the operation has a space complexity of O(1).
The variables ans and cnt use a constant amount of space, thus contributing O(1) to the space complexity.
The enumeration in the for loop does not create a new list but rather an iterator over the sliced list (nums[1:]). The slice operation in Python creates a new list object, so this operation takes O(n-1) space, which simplifies to O(n).

Therefore, the space complexity of the code is O(n) due to the list slicing operation.

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

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Which algorithm should you use to find a node that is close to the root of the tree?

Depth First Search

Breadth First Search

I don't know