Problem

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.

Examples

Example 1:

1
2
3
4
5
6

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:

1
2
3
4

Input: nums = [10,10,10]
Output: 0
Explanation:
* All elements are already equal, so no operations are needed.

Constraints:

  • 1 <= nums.length <= 10^5
  • -109 <= nums[i] <= 10^9

Solution

Method 1 – Count Prefix Changes

Intuition

To make all elements equal, we need to eliminate every change in value as we scan from left to right. Each time the value changes, we need an operation to adjust the prefix so the next value matches the previous ones.

Approach

  1. Initialize a counter for operations.
  2. Iterate through the array from left to right.
  3. Each time nums[i] is different from nums[i-1], increment the counter.
  4. Return the total count.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

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

func MinimumOperations(nums []int) int {
    ops := 0
    for i := 1; i < len(nums); i++ {
        if nums[i] != nums[i-1] {
            ops++
        }
    }
    return ops
}
1
2
3
4
5
6
7
8
9

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

class Solution {
    fun minimumOperations(nums: IntArray): Int {
        var ops = 0
        for (i in 1 until nums.size) {
            if (nums[i] != nums[i-1]) ops++
        }
        return ops
    }
}
1
2
3
4
5
6
7
8

from typing import List
class Solution:
    def minimumOperations(self, nums: List[int]) -> int:
        ops = 0
        for i in range(1, len(nums)):
            if nums[i] != nums[i-1]:
                ops += 1
        return ops
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

impl Solution {
    pub fn minimum_operations(nums: Vec<i32>) -> i32 {
        let mut ops = 0;
        for i in 1..nums.len() {
            if nums[i] != nums[i-1] {
                ops += 1;
            }
        }
        ops
    }
}
1
2
3
4
5
6
7
8
9

class Solution {
    minimumOperations(nums: number[]): number {
        let ops = 0;
        for (let i = 1; i < nums.length; i++) {
            if (nums[i] !== nums[i-1]) ops++;
        }
        return ops;
    }
}

Complexity

  • ⏰ Time complexity: O(n) — We scan the array once.
  • 🧺 Space complexity: O(1) — Only a few variables are used for computation.