1887. Reduction Operations to Make the Array Elements Equal

problem.md

1887. Reduction Operations to Make the Array Elements Equal

Given an integer array nums, your goal is to make all elements in nums equal. To complete one operation, follow these steps:

1. Find the largest value in nums. Let its index be i (0-indexed) and its value be largest. If there are multiple elements with the largest value, pick the smallest i.
2. Find the next largest value in nums strictly smaller than largest. Let its value be nextLargest.
3. Reduce nums[i] to nextLargest.

Return the number of operations to make all elements in nums equal.

Example 1:

• Input: nums = [5,1,3]
• Output: 3
• Explanation: It takes 3 operations to make all elements in nums equal:

1. largest = 5 at index 0. nextLargest = 3. Reduce nums[0] to 3. nums = [3,1,3].
2. largest = 3 at index 0. nextLargest = 1. Reduce nums[0] to 1. nums = [1,1,3].
3. largest = 3 at index 2. nextLargest = 1. Reduce nums[2] to 1. nums = [1,1,1].

revisedSolution.md

const reductionOperations = (nums: number[]) => {
  const sorted = [...nums].sort((x, y) => x - y)
  const unique = [...new Set(sorted)]
  const map = new Map(unique.map((x, i) => [x, i]))

  return sorted.reduce((count, _, i) => count + (map.get(sorted[i]) || 0), 0)
}

• time complexity: $O(n logn)$
• space complexity: $O(n)$

Using a Map (hash table) rather than an array for the unique values makes the reducer more efficient. Finding the value of sorted[i] using Map.get() is O(1), where Array.indexOf() is O(n). This changes the complexity of reduce to O(n), where before it was O(n²). This means the largest complexity of the revised solution is now Array.sort(), which if we assume is using merge sort, equals O(n log(n)).

solution.md

const reductionOperations = (nums: number[]) => {
  const sorted = [...nums].sort((x, y) => x - y)
  const unique = [...new Set(sorted)]

  return sorted.reduce((count, _, i) => count + unique.indexOf(sorted[i]), 0)
}

• time complexity: $O(n²)$
• space complexity: $O(n)$

Creating an array of only unique values from a sorted nums gives you the operation count per value, where the index equals the number of operations required for the value to be reduced to the smallest value.

e.g.:

• [5, 1, 3, 1, 3] sorted equals [1, 1, 3, 3, 5]
• only the unique values of sorted equals [1, 3, 5]
• 1 is the smallest value, so it requires 0 operations to be reduced (index 0)
• 3 is the next largest value, i.e. it requires 1 more operation (1) to be reduced to the smallest value
• 5 is the next largest value, i.e. it requires 1 more operation (2) to be reduced to the smallest value
• now you can iterate through the sorted array, incrementing the operation count by the index of the current value in the unique array - [1, 1, 3, 3, 5] = 0 + 0 + 1 + 1 + 2 = 4