Reduction Operations to Make the Array Elements Equal solution and explanation
9 more videos on this problem
Reduction Operations to Make the Array Elements Equal | Intuition | Leetcode-1887codestorywithMIK · 13:54 · 4K views
[Leetcode] 1887. Reduction Operations to Make the Array Elements Equal羅油膩GO工程師頻道 · 7:17 · 1K views
Leetcode 1887 | Reduction Operations to Make the Array Elements EqualSandip Jana · 5:00 · 1K views
1887. Reduction Operations to Make the Array Elements Equal | Priority Queue | SortingAryan Mittal · 10:12 · 1K views
Reduction Operations to Make the Array Elements Equal | LeetCode Weekly Contest 244 | Coders CampCoders Camp · 6:51 · 897 views
✅ Reduction Operations to Make the Array Elements Equal - Modified Counting Sort - LeetCode 1887Leet Logics · 8:26 · 542 views
1887. Reduction Operations to Make the Array Elements Equal (Leetcode Medium)Programming Live with Larry · 5:49 · 420 views
Daily Leetcode #1328: Nov 19, 2023 - 1887. Reduction Operations to Make the Array Elements EqualProgramming Live with Larry · 10:00 · 248 views
Solving LeetCode 1887 Reduction Operations to Make the Array Elements Equal | Array | IntuitiveCode Harmony · 9:47 · 215 views
Reduction Operations to Make the Array Elements Equal - LeetCode 1887 - PythonAlpha-Code · 11:29 · 159 views
The problem
Given an integer array nums, your goal is to make all elements in nums equal. To complete one operation, follow these steps:
- Find the largest value in
nums. Let its index bei(0-indexed) and its value belargest. If there are multiple elements with the largest value, pick the smallesti. - Find the next largest value in
numsstrictly smaller thanlargest. Let its value benextLargest. - Reduce
nums[i]tonextLargest.
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].
Example 2:
Input: nums = [1,1,1] Output: 0 Explanation: All elements in nums are already equal.
Example 3:
Input: nums = [1,1,2,2,3] Output: 4 Explanation: It takes 4 operations to make all elements in nums equal: 1. largest = 3 at index 4. nextLargest = 2. Reduce nums[4] to 2. nums = [1,1,2,2,2]. 2. largest = 2 at index 2. nextLargest = 1. Reduce nums[2] to 1. nums = [1,1,1,2,2]. 3. largest = 2 at index 3. nextLargest = 1. Reduce nums[3] to 1. nums = [1,1,1,1,2]. 4. largest = 2 at index 4. nextLargest = 1. Reduce nums[4] to 1. nums = [1,1,1,1,1].
Constraints:
1 <= nums.length <= 5 * 1041 <= nums[i] <= 5 * 104
Approach overview
Problem Overview: You are given an array of integers. In one operation, you pick the largest value and reduce it to the next smaller distinct value in the array. The goal is to compute the minimum number of operations required to make all elements equal.
Approach 1: Sorting and Iteration (Time: O(n log n), Space: O(1))
Sort the array so equal values are grouped and larger numbers appear later. While scanning the sorted array from left to right, each time you encounter a new distinct value, every element to its right will eventually require one additional reduction step. Track the index i and whenever nums[i] != nums[i-1], add i to the total operations. The insight: each distinct level of value introduces another layer of reductions for all larger elements. Sorting simplifies the comparison logic and avoids repeatedly simulating operations.
This approach works well in practice because the algorithm becomes a single pass after sorting. The implementation is concise and uses only constant extra space beyond the input array. The main cost comes from sorting, which takes O(n log n). See more patterns like this in sorting and array problems.
Approach 2: Counting and Aggregating (Time: O(n log k), Space: O(k))
Instead of sorting the entire array, count the frequency of each distinct value using a map or counting structure. Let k be the number of unique values. Sort the unique keys and process them from smallest to largest. Maintain a running count of how many elements are greater than the current value. Each time you move to the next larger value level, all elements above it require one additional reduction operation.
The key idea is aggregating reductions by value groups rather than by individual elements. Frequencies allow you to compute how many elements participate in each reduction layer. This reduces repeated work and keeps the algorithm efficient when the number of unique values is small. The complexity becomes O(n) to build the frequency map plus O(k log k) to sort unique values.
Recommended for interviews: The sorting and iteration approach is typically expected. It is simple, easy to reason about, and directly models how reduction layers accumulate across distinct values. Interviewers often want to see the insight that each new distinct value contributes operations equal to the number of elements already processed. The counting approach demonstrates stronger optimization thinking when discussing alternatives.
Approach 1: Approach 1: Sorting and Iteration
To solve this problem, we can first sort the array. After sorting, for each distinct number except the smallest one, count how many times smaller numbers need to be stepped up to equal the larger ones. Iterate over the sorted array and accumulate these steps until all numbers are equal.
def reduction_operations(nums):
nums.sort()
operations = 0
distinct_count = 0
for i in range(1, len(nums)):
if nums[i] != nums[i - 1]:
distinct_count += 1
operations += distinct_count
return operations
print(reduction_operations([5, 1, 3]))import java.util.Arrays;
public class Solution {
public int reductionOperations(int[] nums) {
Arrays.sort(nums);
int operations = 0, distinctCount = 0;
for (int i = 1; i < nums.length; i++) {
if (nums[i] != nums[i - 1]) {
distinctCount++;
}
operations += distinctCount;
}
return operations;
}
public static void main(String[] args) {
Solution solution = new Solution();
int[] nums = {5, 1, 3};
System.out.println(solution.reductionOperations(nums));
}
}#include <iostream>
#include <vector>
#include <algorithm>
int reductionOperations(std::vector<int>& nums) {
std::sort(nums.begin(), nums.end());
int operations = 0, distinctCount = 0;
for (int i = 1; i < nums.size(); i++) {
if (nums[i] != nums[i - 1]) {
distinctCount++;
}
operations += distinctCount;
}
return operations;
}
int main() {
std::vector<int> nums = {5, 1, 3};
std::cout << reductionOperations(nums) << std::endl;
return 0;
}function reductionOperations(nums) {
nums.sort((a, b) => a - b);
let operations = 0;
let distinctCount = 0;
for (let i = 1; i < nums.length; i++) {
if (nums[i] !== nums[i - 1]) {
distinctCount++;
}
operations += distinctCount;
}
return operations;
}
console.log(reductionOperations([5, 1, 3]));#include <stdio.h>
#include <stdlib.h>
int compare(const void *a, const void *b) {
return (*(int*)a - *(int*)b);
}
int reductionOperations(int* nums, int numsSize) {
qsort(nums, numsSize, sizeof(int), compare);
int operations = 0, distinctCount = 0;
for (int i = 1; i < numsSize; i++) {
if (nums[i] != nums[i - 1]) {
distinctCount++;
}
operations += distinctCount;
}
return operations;
}
int main() {
int nums[] = {5, 1, 3};
int size = sizeof(nums) / sizeof(nums[0]);
printf("%d\n", reductionOperations(nums, size));
return 0;
}using System;
public class Solution {
public int ReductionOperations(int[] nums) {
Array.Sort(nums);
int operations = 0, distinctCount = 0;
for (int i = 1; i < nums.Length; i++) {
if (nums[i] != nums[i - 1]) {
distinctCount++;
}
operations += distinctCount;
}
return operations;
}
public static void Main(string[] args) {
Solution solution = new Solution();
int[] nums = {5, 1, 3};
Console.WriteLine(solution.ReductionOperations(nums));
}
}In Python, we use the list sort method to order elements, then traverse through the sorted list while counting distinct numbers. This determines how many operations are needed by incrementing the operations count based on distinct elements.
Time Complexity: O(n log n) from sorting, Space Complexity: O(1).
Approach 2: Approach 2: Counting and Aggregating
This approach involves counting the duplicates of each number without explicitly sorting. By iterating from the maximum value to the minimum, we calculate how many numbers need to be converted at each step by leveraging the array structure and gaps between numbers.
def reduction_operations(nums):
count = [0] * 50001
for num in nums:
count[num] += 1
operations = total = 0
for i in range(50000, 0, -1):
if count[i] > 0:
operations += total
total += count[i]
return operations
print(reduction_operations([5, 1, 3]))public class Solution {
public int reductionOperations(int[] nums) {
int[] count = new int[50001];
for (int num : nums) {
count[num]++;
}
int operations = 0, total = 0;
for (int i = 50000; i > 0; i--) {
if (count[i] != 0) {
operations += total;
total += count[i];
}
}
return operations;
}
public static void main(String[] args) {
Solution solution = new Solution();
int[] nums = {5, 1, 3};
System.out.println(solution.reductionOperations(nums));
}
}#include <iostream>
#include <vector>
int reductionOperations(std::vector<int>& nums) {
std::vector<int> count(50001, 0);
for (int num : nums) {
count[num]++;
}
int operations = 0, total = 0;
for (int i = 50000; i > 0; i--) {
if (count[i]) {
operations += total;
total += count[i];
}
}
return operations;
}
int main() {
std::vector<int> nums = {5, 1, 3};
std::cout << reductionOperations(nums) << std::endl;
return 0;
}function reductionOperations(nums) {
let count = Array(50001).fill(0);
for (let num of nums) {
count[num]++;
}
let operations = 0, total = 0;
for (let i = 50000; i > 0; i--) {
if (count[i] > 0) {
operations += total;
total += count[i];
}
}
return operations;
}
console.log(reductionOperations([5, 1, 3]));#include <stdio.h>
int reductionOperations(int* nums, int numsSize) {
int count[50001] = {0};
for (int i = 0; i < numsSize; i++) {
count[nums[i]]++;
}
int operations = 0, total = 0;
for (int i = 50000; i > 0; i--) {
if (count[i]) {
operations += total;
total += count[i];
}
}
return operations;
}
int main() {
int nums[] = {5, 1, 3};
int size = sizeof(nums) / sizeof(nums[0]);
printf("%d\n", reductionOperations(nums, size));
return 0;
}using System;
public class Solution {
public int ReductionOperations(int[] nums) {
int[] count = new int[50001];
foreach (int num in nums) {
count[num]++;
}
int operations = 0, total = 0;
for (int i = 50000; i > 0; i--) {
if (count[i] > 0) {
operations += total;
total += count[i];
}
}
return operations;
}
public static void Main(string[] args) {
Solution solution = new Solution();
int[] nums = {5, 1, 3};
Console.WriteLine(solution.ReductionOperations(nums));
}
}This Python solution initializes a list of zeros, counting the frequency of each element. By iterating from maximum value downwards, it computes the number of necessary operations by effectively using cumulative frequency of encountered elements.
Time Complexity: O(n + k), Space Complexity: O(k).
Approach 3: Sorting
We first sort the array nums, then iterate from the second element of the array. If the current element is not equal to the previous element, we increment cnt, indicating the number of operations needed to reduce the current element to the minimum value. Then we add cnt to ans and continue to the next element.
The time complexity is O(n times log n), and the space complexity is O(log n). Here, n is the length of the array nums.
function reductionOperations(nums: number[]): number {
nums.sort((a, b) => a - b);
let [ans, cnt] = [0, 0];
for (let i = 1; i < nums.length; ++i) {
if (nums[i] !== nums[i - 1]) {
++cnt;
}
ans += cnt;
}
return ans;
}func reductionOperations(nums []int) (ans int) {
sort.Ints(nums)
cnt := 0
for i, x := range nums[1:] {
if x != nums[i] {
cnt++
}
ans += cnt
}
return
}Complexity comparison
| Approach | Complexity |
|---|---|
| Approach 1: Sorting and Iteration | Time Complexity: O(n log n) from sorting, Space Complexity: O(1). |
| Approach 2: Counting and Aggregating | Time Complexity: O(n + k), Space Complexity: O(k). |
| Sorting | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Sorting and Iteration | O(n log n) | O(1) | General case. Simple implementation and commonly expected in interviews. |
| Counting and Aggregating | O(n log k) | O(k) | When the number of distinct values is much smaller than n and frequency aggregation is convenient. |
Frequently asked questions
Is Reduction Operations to Make the Array Elements Equal easy or hard?
LeetCode classifies this problem as Medium. The challenge is recognizing that each distinct value level contributes reductions for all larger elements. Once that pattern is identified, the implementation becomes a straightforward sorting and counting pass.
Reduction Operations to Make the Array Elements Equal Python/Java solution
In Python or Java, the standard solution sorts the array and iterates once. Whenever nums[i] differs from nums[i-1], add i to the operation count. This concise logic works the same across languages like Python, Java, C++, and JavaScript.
How to solve Reduction Operations to Make the Array Elements Equal in O(n)?
An almost linear approach uses a frequency map to count occurrences of each value, then processes unique values in sorted order. Building the map is O(n), and operations are aggregated using counts of larger elements. The total complexity becomes O(n + k log k), where k is the number of distinct values.
What is the best approach for Reduction Operations to Make the Array Elements Equal?
The most common approach sorts the array and scans it once. Every time a new distinct value appears at index i, you add i operations because all larger elements must eventually be reduced through this level. This produces an O(n log n) time solution with O(1) extra space and is the method most interviewers expect.
Is Reduction Operations to Make the Array Elements Equal asked at Google/Amazon/Meta?
This problem reflects common interview patterns around sorting and counting reductions across value groups. Similar problems appear in interviews at companies like Amazon and Google where candidates must recognize patterns involving sorted arrays and cumulative operations.
What data structure is used in Reduction Operations to Make the Array Elements Equal?
The primary data structures are arrays and optionally a hash map for counting frequencies. The sorting-based approach works directly on the array, while the counting approach stores value frequencies before aggregating operations across distinct numbers.
What is the time complexity of Reduction Operations to Make the Array Elements Equal?
The typical solution runs in O(n log n) time due to sorting the array. After sorting, the algorithm performs a single linear scan to accumulate operations. Space complexity is O(1) if sorting is done in place, aside from the input array.