Minimum Operations to Make Array Equal - Solution & Explanation
Problem Statement
You have an array arr of length n where arr[i] = (2 * i) + 1 for all valid values of i (i.e., 0 <= i < n).
In one operation, you can select two indices x and y where 0 <= x, y < n and subtract 1 from arr[x] and add 1 to arr[y] (i.e., perform arr[x] -=1 and arr[y] += 1). The goal is to make all the elements of the array equal. It is guaranteed that all the elements of the array can be made equal using some operations.
Given an integer n, the length of the array, return the minimum number of operations needed to make all the elements of arr equal.
Example 1:
Input: n = 3 Output: 2 Explanation: arr = [1, 3, 5] First operation choose x = 2 and y = 0, this leads arr to be [2, 3, 4] In the second operation choose x = 2 and y = 0 again, thus arr = [3, 3, 3].
Example 2:
Input: n = 6 Output: 9
Constraints:
1 <= n <= 104
Approach Overview
Problem Overview: You start with an array of size n where arr[i] = 2*i + 1. In one operation you choose two indices and decrease one value by 1 while increasing the other by 1. The goal is to make every element equal using the minimum number of operations.
Approach 1: Brute Force Simulation (Inefficient but Useful for Understanding) (Time: O(n^2), Space: O(1))
This approach literally simulates the balancing process. Generate the array [1, 3, 5, ..., 2n-1], then repeatedly move units from larger elements to smaller ones until every value becomes the same. Conceptually, you push values toward the middle by transferring 1 unit from the right side of the array to the left side. Each transfer counts as one operation.
The simulation works because the final value must be the average of the array, which is exactly n. You keep adjusting pairs until both sides meet this target. Although easy to reason about, it becomes slow because each imbalance may require multiple step-by-step transfers. With nested adjustments across elements, the time complexity grows to O(n^2). This method is mostly useful for understanding the mechanics of the operation rather than for efficient implementation.
Approach 2: Balanced Operations Towards Median (Math Insight) (Time: O(n) or O(1), Space: O(1))
The array is already symmetric: [1, 3, 5, ..., 2n-1]. The target value for every element must be the mean, which equals n. Instead of simulating operations, count how far elements on the left side are below this value. Each unit of deficit requires exactly one operation transferred from the right side.
For the first half of the array, compute how much each element needs to increase to reach n. For index i, the value is 2*i + 1, so the deficit is n - (2*i + 1). Summing these deficits gives the exact number of operations needed. Because the array is symmetric, the right side automatically provides the required decreases.
This observation leads to a clean mathematical formula. The total operations simplify to floor(n^2 / 4). You can either compute it directly in O(1) time or iterate through half the array in O(n). The solution relies purely on math reasoning and the structure of the array, avoiding any actual simulation.
Recommended for interviews: Interviewers expect the mathematical balancing insight. Starting with the brute force explanation shows you understand the mechanics of the operation, but recognizing the symmetry and reducing it to a formula demonstrates strong problem-solving and mathematical optimization. The optimal implementation runs in constant time and uses no extra memory.
Approach 1: Balanced operations towards median
The array arr follows the pattern (2 * i) + 1, making it an arithmetic sequence of odd numbers. The median of the arithmetic sequence is the middle element for odd n and the average of two middle elements for even n. Since operations have to balance the values to become equal, the number of operations required is essentially the sum of steps needed to make the greater half equal to this median, iterating from the middle outwards.
The function calculates how many operations are needed by focusing on one half of the array to compute the total steps the elements in this half must take to equalize. The variable half represents the number of operations contributed by each of these elements.
Complexity
Time Complexity: O(1), since the solution simply computes a formula.
Space Complexity: O(1), as no additional space is required.
Approach 2: Brute Force Simulation (Inefficient but Useful for Understanding)
This approach demonstrates a naive simulation of operations: iteratively balance the array elements by focusing on reducing extreme disparities between elements. This is not intended for efficiency but understanding the process.
This technique creates the array and iteratively applies moves to gradually level the array. It evaluates each pairing of elements in a nested loop fashion, conducting operations until all elements stabilize at the target value.
Complexity
Time Complexity: O(n^2), due to nested iterations looking for disparities.
Space Complexity: O(n), to store the array.
Approach 3: Mathematics
According to the problem description, the array arr is an arithmetic sequence with the first term as 1 and the common difference as 2. Therefore, the sum of the first n terms of the array is:
$
\begin{aligned}
S_n &= \frac{n}{2} times (a_1 + a_n) \
&= \frac{n}{2} times (1 + (2n - 1)) \
&= n^2
\end{aligned}
Since in one operation, one number is decreased by one and another number is increased by one, the sum of all elements in the array remains unchanged. Therefore, when all elements in the array are equal, the value of each element is S_n / n = n. Hence, the minimum number of operations required to make all elements in the array equal is:
sum_{i=0}^{\frac{n}{2}} (n - (2i + 1))
The time complexity is O(n), where n is the length of the array. The space complexity is O(1)$.
Code
Python
Java
C++
Go
TypeScript
Complexity Comparison
| Approach | Complexity |
|---|---|
| Balanced operations towards median | Time Complexity: O(1), since the solution simply computes a formula. |
| Brute Force Simulation (Inefficient but Useful for Understanding) | Time Complexity: O(n^2), due to nested iterations looking for disparities. |
| Mathematics | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Simulation | O(n^2) | O(1) | Learning the mechanics of balancing operations step by step |
| Balanced Operations Towards Median (Math) | O(n) or O(1) | O(1) | Optimal interview solution using symmetry and mathematical formula |
Video Solution
Minimum Operations to Make Array Equal | Leetcode - 1551 • Algorithms Made Easy • 25,214 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Minimum Operations to Make Array Equal easy or hard?
Minimum Operations to Make Array Equal Python/Java solution
How to solve Minimum Operations to Make Array Equal in O(n)?
What is the best approach for Minimum Operations to Make Array Equal?
Is Minimum Operations to Make Array Equal asked at Google/Amazon/Meta?
What data structure is used in Minimum Operations to Make Array Equal?
What is the time complexity of Minimum Operations to Make Array Equal?
Ready to solve this problem?
Practice Minimum Operations to Make Array Equal with our built-in code editor and test cases.
Practice on FleetCodeTable of Contents
Practice this problem
Open in Editor