Skip to content

3353. Minimum Total Operations πŸ”’

Description

Given an array of integers nums, you can perform any number of operations on this array.

In each operation, you can:

  • Choose a prefix of the array.
  • Choose an integer 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:

  • Operation 1: Choose the prefix [1, 4] of length 2 and add -2 to each element of the prefix. The array becomes [-1, 2, 2].
  • Operation 2: Choose the prefix [-1] of length 1 and add 3 to it. The array becomes [2, 2, 2].
  • Thus, the minimum number of required operations is 2.

Example 2:

Input: nums = [10,10,10]

Output: 0

Explanation:

  • All elements are already equal, so no operations are needed.

 

Constraints:

  • 1 <= nums.length <= 105
  • -109 <= nums[i] <= 109

Solutions

Solution 1: Single Pass

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)$.

1
2
3
class Solution:
    def minOperations(self, nums: List[int]) -> int:
        return sum(x != y for x, y in pairwise(nums))

1
2
3
4
5
6
7
8
9
class Solution {
    public int minOperations(int[] nums) {
        int ans = 0;
        for (int i = 1; i < nums.length; ++i) {
            ans += nums[i] != nums[i - 1] ? 1 : 0;
        }
        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
class Solution {
public:
    int minOperations(vector<int>& nums) {
        int ans = 0;
        for (int i = 1; i < nums.size(); ++i) {
            ans += nums[i] != nums[i - 1];
        }
        return ans;
    }
};

1
2
3
4
5
6
7
8
func minOperations(nums []int) (ans int) {
    for i, x := range nums[1:] {
        if x != nums[i] {
            ans++
        }
    }
    return
}

1
2
3
4
5
6
7
function minOperations(nums: number[]): number {
    let ans = 0;
    for (let i = 1; i < nums.length; ++i) {
        ans += nums[i] !== nums[i - 1] ? 1 : 0;
    }
    return ans;
}

Comments