medium Reduction Operations to Make the Array Elements Equal

Problem Statement

Given an array of integers nums, return the number of operations required to make all elements in nums equal. To perform one operation, you can follow the below steps:

• Select the maximum element of nums. If there are multiple occurrences of the maximum element, choose the element which has lowest index i.
• Select the second largest element of nums.
• Replace the element at index i with the second largest element.

Examples

Example 1:

• Input: [3, 5, 5, 2]
• Expected output: 5
• Justification:
  • The largest element is 5. Reducing both 5s to 3 requires two operations.
  • Update array will be [3, 3, 3, 2].
  • Three more operations are needed to reduce the 3 to 2. The updated array will be [2, 2, 2, 2].
  • A total five operations make all elements equal to 2.

Example 2:

• Input: [11, 9, 7, 5, 3]
• Expected output: 10
• Justification:
  • Each number needs to be reduced stepwise to the next smaller number until all are equal to the smallest number 3.
  • 1 operation is required to convert 11 to 9. The updated array will be [9, 9, 7, 5, 3].
  • 2 operations are required to convert 9 to 7. The updated array will be [7, 7, 7, 5, 3].
  • 3 operations are required to convert 7 to 5. The updated array will be [5, 5, 5, 5, 3].
  • 4 operations are required to convert 5 to 3. The updated array will be [3, 3, 3, 3, 3].
  • Tota numbers of operations: 1 + 2 + 3 + 4 = 10.

Example 3:

• Input: [8, 8, 8, 8]
• Expected output: 0
• Justification: All elements are already equal, so no operations are needed.

Constraints:

• 1 <= nums.length <= 5 * 10⁴
• 1 <= nums[i] <= 5 * 10⁴

Solution

To solve this problem, the most effective approach involves sorting the array and leveraging the sorted structure to determine the reduction operations efficiently. The solution is driven by identifying and counting the number of elements that must be reduced to each unique lesser value until all elements are the same. The frequency of each distinct value in the array provides a clear path for determining the number of necessary operations.

By sorting the array, we can work backwards, starting from the largest element, and reduce it step by step to match the next distinct element in the sorted order. This method ensures that the number of operations is minimized since we always reduce the largest elements first and in bulk, which decreases the number of total operations.

Step-by-step Algorithm

1. Sort the Array:

   • Begin by sorting the given array of integers in non-decreasing order. This will organize the array such that the smallest elements are at the beginning and the largest at the end, facilitating efficient traversal for reductions.

2. Initialize Variables:

   • Initialize a variable, operations, to zero. This will keep track of the total number of operations performed.
   • Initialize a variable, count, to one. This will count the number of occurrences of the current largest value we are reducing.

3. Traverse the Sorted Array from the End to the Start:

   • Start from the last element of the array (which is the largest due to sorting) and move towards the first element.
   • Check if the current element is different from the previous one:
     • If it is, add the value of count to operations. This addition accounts for the operations needed to reduce all occurrences of the current largest element to the next largest element.
     • Increase the count by one for each step back through the array. This increment reflects that one more element (the previous element in the sorted array) will need to be reduced in the next round of operations.

4. Return the Result:

   • Once the traversal is complete, return the operations variable, which now contains the total number of operations required to make all elements equal.

Algorithm Walkthrough

Let's consider the input: nums = [11, 9, 7, 5, 3]

1. Sort the Array:

   • The array is already sorted in non-decreasing order: [3, 5, 7, 9, 11].

2. Initialize Variables:

   • operations = 0
   • count = 1

3. Traverse the Sorted Array:

   • Start from the end of the array (index 4, value 11).

   • Index 4 (value 11):

     • Compare with the next element towards the start (index 3, value 9).
     • They are different, so add count to operations (0 + 1 = 1).
     • Increment count to 2.

   • Index 3 (value 9):

     • Compare with the next element towards the start (index 2, value 7).
     • They are different, add count to operations (1 + 2 = 3).
     • Increment count to 3.

   • Index 2 (value 7):

     • Compare with the next element towards the start (index 1, value 5).
     • They are different, add count to operations (3 + 3 = 6).
     • Increment count to 4.

   • Index 1 (value 5):

     • Compare with the next element towards the start (index 0, value 3).
     • They are different, add count to operations (6 + 4 = 10).
     • Increment count to 5.

4. Complete Traversal:

   • All elements have been checked, and operations needed to reduce each to the next smallest value have been counted.

5. Return the Result:

   • The final value of operations is 10, indicating the total operations needed.

Code

import java.util.Arrays;

public class Solution {

  // Method to calculate the minimum number of operations to reduce the array
  public int reductionOperations(int[] nums) {
    Arrays.sort(nums); // Sort the array in ascending order
    int operations = 0,
      count = 1;
    for (int i = nums.length - 1; i > 0; i--) {
      // Loop through the array from the end
      if (nums[i] != nums[i - 1]) {
        // If the current number is different from the previous one
        operations += count; // Increment the total operations by the current count
      }
      count++; // Increment the count for the next number
    }
    return operations; // Return the total number of operations
  }

  public static void main(String[] args) {
    Solution solution = new Solution();
    // Test cases
    System.out.println(solution.reductionOperations(new int[] { 3, 5, 5, 2 })); // 5
    System.out.println(
      solution.reductionOperations(new int[] { 11, 9, 7, 5, 3 })
    ); // 10
    System.out.println(solution.reductionOperations(new int[] { 8, 8, 8, 8 })); // 0
  }
}

Complexity Analysis

Time Complexity

• Sorting the array: The most computationally intensive operation here is sorting the array, which has a time complexity of , where (n) is the number of elements in the array.
• Traversing the sorted array: Once the array is sorted, the algorithm performs a single pass through the array to count the required operations, which is .

Thus, the overall time complexity of the algorithm is .

Space Complexity

• Space for sorting: Sorting the array in place requires no additional space beyond the input array itself in some implementations like heapsort, but for languages or methods that use mergesort (like Java), this might require space.
• Counters: Only a few additional variables are used, which are constant space, .

Therefore, the space complexity is if the sorting is done in place, or if extra space is used for sorting.