Given an array of integers nums, you can perform any number of operations on this array.
In each operation, you can:
k (which can be negative) and add k to each element in the chosen prefix.A prefix of an array is a subarray that starts from the beginning of the array and extends to any point within it.
Return the minimum number of operations required to make all elements in arr equal.
Example 1:
Input: nums = [1,4,2]
Output: 2
Explanation:
[1, 4] of length 2 and add -2 to each element of the prefix. The array becomes [-1, 2, 2].[-1] of length 1 and add 3 to it. The array becomes [2, 2, 2].Example 2:
Input: nums = [10,10,10]
Output: 0
Explanation:
Constraints:
1 <= nums.length <= 105-109 <= nums[i] <= 109Problem Overview: You are given an integer array and need to compute the minimum number of operations required to make the array satisfy a required ordering constraint. Each operation modifies an element, and the goal is to minimize the total operations across the entire array.
Approach 1: Single Pass Greedy Scan (O(n) time, O(1) space)
The most efficient strategy is a greedy single pass through the array. Traverse from left to right while tracking the previous valid value. If the current value already satisfies the required condition relative to the previous element, move forward. If it violates the condition, compute how many operations are needed to adjust it and add that to the running total. After adjustment, treat the corrected value as the new reference for the next step. This works because fixing violations locally during a single traversal guarantees the global minimum number of operations.
The key insight is that you never need to revisit earlier elements. Each element only depends on the constraint with its immediate predecessor, so a forward scan is sufficient. That eliminates the need for nested loops or backtracking. Operations accumulate based on the difference between the current value and the minimum value required to maintain the constraint.
This pattern appears frequently in array problems where you enforce ordering or monotonic properties. Greedy adjustments during iteration keep the algorithm linear while maintaining correctness.
Recommended for interviews: Interviewers expect the single pass greedy solution. A brute force approach that repeatedly scans or adjusts the array demonstrates understanding of the problem constraints, but the optimal solution shows you recognize that each element only depends on the previous state. Achieving O(n) time with O(1) extra space is the key optimization for most array traversal problems and demonstrates strong algorithmic reasoning.
We can traverse the array, and for each element, if it is not equal to the previous element, we need to perform an operation. Finally, we return the number of operations.
The time complexity is O(n), where n is the length of the array. The space complexity is O(1).
Python
Java
C++
Go
TypeScript
Rust
JavaScript
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Repeated Adjustment / Brute Force | O(n^2) | O(1) | Useful for understanding the constraint by repeatedly fixing violations in the array. |
| Single Pass Greedy Scan | O(n) | O(1) | Best approach for interviews and production. One linear traversal computes minimal operations. |
LeetCode Premium: 3353 Minimum Total Operations #leetcode #coding #interview #leetcodesolution #code • Super Lazy Coder • 158 views views
Practice Minimum Total Operations with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor