Watch 9 video solutions for Minimum Operations to Make the Array Alternating, a medium level problem involving Array, Hash Table, Greedy. This walkthrough by Bro Coders has 2,843 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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 |