Minimum Operations to Make the Array Alternating
Medium
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], where2 <= i <= n - 1.nums[i - 1] != nums[i], where1 <= 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**].
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 <= 10^51 <= nums[i] <= 10^5
Solution
Naive Approach
A brute force solution would involve trying all possible combinations of numbers for each index and checking if the resulting array is alternating. Since each number can be any positive integer, and the array can be large, this quickly becomes infeasible. Specifically, for each element, we would need to iterate over every other number, making this approach $O(k^n)$ where k is the range of integers allowed and n is the number of elements.
Optimal Approach
The key idea is to count the frequencies of numbers at even and odd indices separately. Then, we try to minimize the number of operations by keeping the most frequent number at even indices and the most frequent number at odd indices, but we have to handle the case when the most frequent numbers are the same.
Here's a breakdown:
- Count Frequencies: Create two dictionaries (or HashMaps), one for even indices and one for odd indices. Iterate through the input array and count the occurrences of each number at even and odd positions.
- Find Most Frequent Numbers: For each dictionary, find the number with the highest frequency (the "most frequent number"). Also, find the number with the second-highest frequency.
- Calculate Operations:
- If the most frequent number in the even indices dictionary is different from the most frequent number in the odd indices dictionary, the number of operations is
n - (frequency of most frequent even number + frequency of most frequent odd number). We keep the most frequent numbers and change the rest. - If the most frequent numbers are the same, then there will be some overlap. We consider two possibilities:
- Keep the most frequent number in even indices and the second most frequent number in odd indices.
- Keep the second most frequent number in even indices and the most frequent number in odd indices. Take the minimum of these two options.
- If the most frequent number in the even indices dictionary is different from the most frequent number in the odd indices dictionary, the number of operations is
Edge Cases
- Empty array: Should not happen, based on constraints.
- Single element array: The array is trivially alternating, so 0 operations.
- Two element array: If the two elements are different, the array is alternating, so 0 operations. Otherwise, 1 operation.
Example
nums = [3, 1, 3, 2, 4, 3]
- Even indices:
{3: 2, 4: 1}. Most frequent:3(frequency 2), Second most frequent:4(frequency 1). - Odd indices:
{1: 1, 2: 1, 3: 1}. Most frequent:1(frequency 1), Second most frequent:2(frequency 1).
Since the most frequent numbers (3 and 1) are different, the number of operations is 6 - (2 + 1) = 3.
nums = [1, 2, 2, 2, 2]
- Even indices:
{1: 1, 2: 1}. Most frequent:1(frequency 1), Second most frequent:2(frequency 1). - Odd indices:
{2: 3}. Most frequent:2(frequency 3), Second most frequent: N/A (frequency 0).
Since the most frequent numbers (1 and 2) are different, the number of operations is 5 - (1 + 3) = 1. There is a mistake in the sample testcase
Code
from collections import defaultdict
def min_operations(nums):
n = len(nums)
even_counts = defaultdict(int)
odd_counts = defaultdict(int)
for i in range(0, n, 2):
even_counts[nums[i]] += 1
for i in range(1, n, 2):
odd_counts[nums[i]] += 1
def get_most_frequent(counts):
if not counts:
return None, 0, None, 0
most_frequent = None
most_frequent_count = 0
second_most_frequent = None
second_most_frequent_count = 0
for num, count in counts.items():
if count > most_frequent_count:
second_most_frequent = most_frequent
second_most_frequent_count = most_frequent_count
most_frequent = num
most_frequent_count = count
elif count > second_most_frequent_count:
second_most_frequent = num
second_most_frequent_count = count
return most_frequent, most_frequent_count, second_most_frequent, second_most_frequent_count
even_most_frequent, even_most_frequent_count, even_second_most_frequent, even_second_most_frequent_count = get_most_frequent(even_counts)
odd_most_frequent, odd_most_frequent_count, odd_second_most_frequent, odd_second_most_frequent_count = get_most_frequent(odd_counts)
if even_most_frequent != odd_most_frequent:
return n - (even_most_frequent_count + odd_most_frequent_count)
else:
return n - max(even_most_frequent_count + odd_second_most_frequent_count,
even_second_most_frequent_count + odd_most_frequent_count)
Time and Space Complexity
- Time Complexity: O(n), where n is the length of the input array. We iterate through the array a fixed number of times (to build the frequency maps and to find the most frequent elements).
- Space Complexity: O(n), where n is the length of the input array in the worst case. In the worst case, the maps could contain n/2 unique elements each, if every number is distinct.
