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 indexi
. - Find the next largest value that is strictly smaller than
largest
, denoted asnextLargest
. - Replace the element at index
i
withnextLargest
.
The problem asks us to return the number of operations required to make all elements in the array equal.
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 usingnums.sort()
. -
A
for
loop withenumerate
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 at0
because no operations are performed at the first element.ans
: This accumulates the total number of operations.
-
Inside the loop, each element
v
at indexi
(wherei
starts from1
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 forv
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 incrementcnt
by1
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 toans
. -
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:
1class Solution:
2 def reductionOperations(self, nums: List[int]) -> int:
3 nums.sort() # [Sorting](/problems/sorting_summary) the array in non-decreasing order
4 ans = cnt = 0 # Initialize counters to zero
5 for i, v in enumerate(nums[1:]): # Iterate through the array, skipping the first element
6 if v != nums[i]: # If current element is greater than the previous one (not equal)
7 cnt += 1 # Increment the number of operations needed
8 ans += cnt # Add to total answer
9 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 EvaluatorExample Walkthrough
Let's walk through a small example using the solution approach described above. Consider the following array of integers:
1nums = [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:
1Sort 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
andans = 0
. - Start iterating from the second element of
nums
(since we need to compare each element with its previous one).
- Initialize our counters:
-
Iteration:
- Compare
3
with1
. Since3
is greater, we found a new value. So,cnt
becomes1
andans
becomes1
. - Compare the second
3
with the first3
. They are equal, no new operation is needed,cnt
stays1
andans
becomes2
. - Compare
5
with3
.5
is greater, socnt
becomes2
(indicating each5
needs two operations to become a3
) andans
becomes4
. - Compare the second
5
with the first5
. They are equal, socnt
stays2
andans
becomes6
.
- Compare
-
Final count:
- After the loop concludes,
ans = 6
, which represents the total number of operations needed to make all elements equal.
- After the loop concludes,
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)
, wheren
is the length of thenums
list. This is because the Timsort algorithm, which is the sorting algorithm used by Python'ssort()
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 ofO(1)
. -
The variables
ans
andcnt
use a constant amount of space, thus contributingO(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 takesO(n-1)
space, which simplifies toO(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.
How would you design a stack which has a function min
that returns the minimum element in the stack, in addition to push
and pop
? All push
, pop
, min
should have running time O(1)
.
Recommended Readings
Sorting Summary Comparisons We presented quite a few sorting algorithms and it is essential to know the advantages and disadvantages of each one The basic algorithms are easy to visualize and easy to learn for beginner programmers because of their simplicity As such they will suffice if you don't know any advanced
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first