Welcome to Subscribe On Youtube

2170. Minimum Operations to Make the Array Alternating

Description

You are given a 0-indexed array nums consisting of n positive integers.

The array nums is called alternating if:

  • nums[i - 2] == nums[i], where 2 <= i <= n - 1.
  • nums[i - 1] != nums[i], where 1 <= i <= n - 1.

In one operation, you can choose an index i and change nums[i] into any positive integer.

Return the minimum number of operations required to make the array alternating.

 

Example 1:

Input: nums = [3,1,3,2,4,3]
Output: 3
Explanation:
One way to make the array alternating is by converting it to [3,1,3,1,3,1].
The number of operations required in this case is 3.
It can be proven that it is not possible to make the array alternating in less than 3 operations.

Example 2:

Input: nums = [1,2,2,2,2]
Output: 2
Explanation:
One way to make the array alternating is by converting it to [1,2,1,2,1].
The number of operations required in this case is 2.
Note that the array cannot be converted to [2,2,2,2,2] because in this case nums[0] == nums[1] which violates the conditions of an alternating array.

 

Constraints:

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

Solutions

  • class Solution {
    private int[] nums;
    private int n;

    public int minimumOperations(int[] nums) {
        this.nums = nums;
        n = nums.length;
        int ans = Integer.MAX_VALUE;
        for (int[] e1 : get(0)) {
            for (int[] e2 : get(1)) {
                if (e1[0] != e2[0]) {
                    ans = Math.min(ans, n - (e1[1] + e2[1]));
                }
            }
        }
        return ans;
    }

    private int[][] get(int i) {
        Map<Integer, Integer> freq = new HashMap<>();
        for (; i < n; i += 2) {
            freq.put(nums[i], freq.getOrDefault(nums[i], 0) + 1);
        }
        int a = 0;
        int n1 = 0;
        int b = 0;
        int n2 = 0;
        for (Map.Entry<Integer, Integer> e : freq.entrySet()) {
            int k = e.getKey();
            int v = e.getValue();
            if (v > n1) {
                b = a;
                n2 = n1;
                a = k;
                n1 = v;
            } else if (v > n2) {
                b = k;
                n2 = v;
            }
        }
        return new int[][] { {a, n1}, {b, n2} };
    }
}

  • typedef pair<int, int> PII;

class Solution {
public:
    int minimumOperations(vector<int>& nums) {
        int ans = INT_MAX;
        int n = nums.size();
        for (auto& [a, n1] : get(0, nums))
            for (auto& [b, n2] : get(1, nums))
                if (a != b)
                    ans = min(ans, n - (n1 + n2));
        return ans;
    }

    vector<PII> get(int i, vector<int>& nums) {
        unordered_map<int, int> freq;
        for (; i < nums.size(); i += 2) ++freq[nums[i]];
        int a = 0, n1 = 0, b = 0, n2 = 0;
        for (auto& [k, v] : freq) {
            if (v > n1) {
                b = a;
                n2 = n1;
                a = k;
                n1 = v;
            } else if (v > n2) {
                b = k;
                n2 = v;
            }
        }
        return { {a, n1}, {b, n2} };
    }
};

  • class Solution:
    def minimumOperations(self, nums: List[int]) -> int:
        def get(i):
            c = Counter(nums[i::2]).most_common(2)
            if not c:
                return [(0, 0), (0, 0)]
            if len(c) == 1:
                return [c[0], (0, 0)]
            return c

        n = len(nums)
        return min(n - (n1 + n2) for a, n1 in get(0) for b, n2 in get(1) if a != b)


  • func minimumOperations(nums []int) int {
	n := len(nums)
	get := func(i int) [][]int {
		freq := make(map[int]int)
		for ; i < n; i += 2 {
			freq[nums[i]]++
		}
		a, n1, b, n2 := 0, 0, 0, 0
		for k, v := range freq {
			if v > n1 {
				b, n2, a, n1 = a, n1, k, v
			} else if v > n2 {
				b, n2 = k, v
			}
		}
		return [][]int{ {a, n1}, {b, n2} }
	}
	ans := 100000
	for _, e1 := range get(0) {
		for _, e2 := range get(1) {
			if e1[0] != e2[0] && ans > (n-(e1[1]+e2[1])) {
				ans = n - (e1[1] + e2[1])
			}
		}
	}
	return ans
}

  • function minimumOperations(nums: number[]): number {
    const n = nums.length,
        m = 10 ** 5;
    let odd = new Array(m).fill(0);
    let even = new Array(m).fill(0);
    for (let i = 0; i < n; i++) {
        let cur = nums[i];
        if (i & 1) {
            odd[cur] = (odd[cur] || 0) + 1;
        } else {
            even[cur] = (even[cur] || 0) + 1;
        }
    }
    let i1 = odd.indexOf(Math.max(...odd));
    let i2 = even.indexOf(Math.max(...even));
    if (i1 != i2) {
        return n - odd[i1] - even[i2];
    } else {
        let l1 = odd[i1],
            l2 = even[i2];
        (odd[i1] = 0), (even[i2] = 0);
        let j1 = odd.indexOf(Math.max(...odd));
        let j2 = even.indexOf(Math.max(...even));
        return n - Math.max(l1 + even[j2], l2 + odd[j1]);
    }
}

All Problems

All Solutions