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 <= 1051 <= nums[i] <= 105Problem Overview: You are given an integer array and must make it alternating with the minimum number of operations. An array is alternating when all elements at even indices share the same value, all elements at odd indices share the same value, and the two values are different. Each operation replaces any element with another value.
The core challenge is selecting the best value for even positions and the best value for odd positions so that the number of replacements is minimized.
Approach 1: Frequency Counting with Top Candidates (O(n) time, O(k) space)
Split the array conceptually into two groups: values at even indices and values at odd indices. Use a hash table or frequency map to count how often each number appears in both groups. Track the top two most frequent values in the even positions and the top two in the odd positions.
The best case occurs when the most frequent value for even indices differs from the most frequent value for odd indices. The number of unchanged elements is the sum of those frequencies, and the remaining elements must be replaced. If both groups share the same most frequent value, choose the second-best candidate for one side. This approach scans the array once and computes the optimal pair directly.
Approach 2: Separate Array Counting and Greedy Adjustment (O(n + m log m) time, O(m) space)
Create two separate frequency containers for even and odd positions. After counting, sort or rank the frequency entries to identify the most frequent candidates. This converts the problem into selecting two different values that maximize the number of preserved elements.
A greedy choice works because keeping the most frequent values minimizes replacements globally. If the top candidate for even and odd positions is the same, compare combinations using the second-best candidate from either side and pick the configuration with the highest total frequency. Counting is linear, while ranking candidates adds a small overhead depending on the number of distinct values.
The main insight across both approaches is that the array can be treated as two independent frequency problems: even indices and odd indices. Using counting techniques lets you quickly identify which values preserve the maximum elements.
Recommended for interviews: The frequency counting approach with top-two tracking is the expected solution. It runs in O(n) time with minimal extra space and demonstrates a clear understanding of array traversal, frequency analysis, and greedy decision making. A brute-force or full sorting approach shows the idea but is less efficient.
To solve this problem efficiently, we can use frequency counting on even and odd indexed positions separately. The core idea is to maximize usage of the most frequent numbers in even and odd indexed positions to minimize the number of operations. Compute the frequency of numbers in even-indexed slots and odd-indexed slots. Then, attempt to alternate the array by using the most frequent elements from these counts. Choose the numbers for even and odd indexed positions to minimize the overlap, and calculate the minimum operations required from this distribution.
The implementation uses the `Counter` class to find the most common elements of the nums array at even and odd indices, respectively. It then determines if the most common elements at these indices are different. If they are, the total number of operations is minimized by taking their sum. If not, the code takes the second most common element from one, ensuring a minimum number of total operations by replacing it.
Python
C++
Java
JavaScript
Time Complexity: O(n), due to iterating over the array twice and the max common calculation.
Space Complexity: O(n), needed for storing the counts.
An alternative approach involves first separating the logic for even and odd indices. Then, apply a greedy algorithm to adjust numbers with potential constraints by swapping or modifying excess element types. Minimize adjustment by using a combination of additional structures where necessary to speed up modifications preserving the alternating property effectiveness.
This is a placeholder solution for approach evaluation logic in Python. The core idea is measuring by structure to identify index-based information with parallel balancing checks between even and odd sequences where necessary.
Python
C++
Java
JavaScript
Time Complexity: O(n), balancing loops.
Space Complexity: O(1), constant space requirements excluding input.
According to the problem description, if an array nums is an alternating array, then the elements at odd positions and even positions must be different, and the elements at odd positions are the same, as well as the elements at even positions.
To minimize the number of operations required to transform the array nums into an alternating array, we can count the occurrence of elements at odd and even positions. We find the two elements with the highest occurrence at even positions, a_0 and a_2, and their corresponding counts a_1 and a_3; similarly, we find the two elements with the highest occurrence at odd positions, b_0 and b_2, and their corresponding counts b_1 and b_3.
If a_0 neq b_0, then we can change all elements at even positions in the array nums to a_0 and all elements at odd positions to b_0, making the number of operations n - (a_1 + b_1); if a_0 = b_0, then we can change all elements at even positions in the array nums to a_0 and all elements at odd positions to b_2, or change all elements at even positions to a_2 and all elements at odd positions to b_0, making the number of operations n - max(a_1 + b_3, a_3 + b_1).
The time complexity is O(n), and the space complexity is O(n), where n is the length of the array nums.
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Using Frequency Counting | Time Complexity: O(n), due to iterating over the array twice and the max common calculation. |
| Separate array manipulation and Greedy Adjustment | Time Complexity: O(n), balancing loops. |
| Maintain Count of Odd and Even Positions | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Frequency Counting with Top Candidates | O(n) | O(k) | Best general solution; linear scan with frequency maps |
| Separate Counting + Greedy Adjustment | O(n + m log m) | O(m) | When using sorted frequency lists or explicit ranking of candidates |
2170 Minimum Operations to Make the Array Alternating | LeetCode 2170 || LeetCode Weekly Contest 280 • Bro Coders • 2,843 views views
Watch 8 more video solutions →Practice Minimum Operations to Make the Array Alternating with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor