What is the time complexity of LeetCode 2170. Minimum Operations to Make the Array Alternating?

The Python solution on this page runs in O(n).

What is the space complexity of LeetCode 2170. Minimum Operations to Make the Array Alternating?

The Python solution on this page uses O(n), where n is the length of the array \textit{nums} auxiliary space.

Minimum Operations to Make the Array Alternating — LeetCode 2170 Python Solution

MediumGreedyArrayHash TableCounting

Problem: #2170
Pattern: Greedy
Reading time: 3 min
Source: leetcode.com

The problem

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.

Example

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].

Python solution

Python

class Solution:
    def minimumOperations(self, nums: List[int]) -> int:
        def f(i: int) -> Tuple[int, int, int, int]:
            k1 = k2 = 0
            cnt = Counter(nums[i::2])
            for k, v in cnt.items():
                if cnt[k1] < v:
                    k2, k1 = k1, k
                elif cnt[k2] < v:
                    k2 = k
            return k1, cnt[k1], k2, cnt[k2]

        a, b = f(0), f(1)
        n = len(nums)
        if a[0] != b[0]:
            return n - (a[1] + b[1])
        return n - max(a[1] + b[3], a[3] + b[1])

Complexity

Measure	Complexity
Time	O(n)
Space	O(n), where n is the length of the array \textit{nums} auxiliary

Pattern: Greedy

Take the locally best option every time — when you can prove that never costs you later. LeetCode 2170. Minimum Operations to Make the Array Alternating is filed here because LeetCode tags it Greedy, which is the vocabulary this hub collects.

The greedy guide has the Python template for the pattern and the 346 LeetCode problems that use it.

Frequently asked questions

How hard is LeetCode 2170. Minimum Operations to Make the Array Alternating?: LeetCode 2170. Minimum Operations to Make the Array Alternating is rated Medium on LeetCode.
What is the time complexity of LeetCode 2170. Minimum Operations to Make the Array Alternating?: The Python solution on this page runs in O(n).
What is the space complexity of LeetCode 2170. Minimum Operations to Make the Array Alternating?: The Python solution on this page uses O(n), where n is the length of the array \textit{nums} auxiliary space.
What topics does LeetCode 2170. Minimum Operations to Make the Array Alternating cover?: LeetCode 2170. Minimum Operations to Make the Array Alternating is tagged Greedy, Array, Hash Table and Counting on LeetCode.