Skip to main content
Talentd

Minimum Operations to Make the Array Alternating - Solution & Explanation

MediumArrayHash TableGreedyCounting18 min readAsked at: Amazon, Bloomberg
Practice this problem

Problem Statement

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

Approach Overview

Problem 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 1: Using Frequency Counting

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.

Code

PythonC++JavaJavaScript

Python

C++

Java

JavaScript

Complexity

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.

Try this approach in the editor →

Approach 2: Separate array manipulation and Greedy Adjustment

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.

Code

PythonC++JavaJavaScript

Python

C++

Java

JavaScript

Complexity

Time Complexity: O(n), balancing loops.
Space Complexity: O(1), constant space requirements excluding input.

Try this approach in the editor →

Approach 3: Maintain Count of Odd and Even Positions

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.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Using Frequency Counting

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.

Separate array manipulation and Greedy Adjustment

Time Complexity: O(n), balancing loops.
Space Complexity: O(1), constant space requirements excluding input.

Maintain Count of Odd and Even Positions—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Frequency Counting with Top CandidatesO(n)O(k)Best general solution; linear scan with frequency maps
Separate Counting + Greedy AdjustmentO(n + m log m)O(m)When using sorted frequency lists or explicit ranking of candidates

Video Solution

2170 Minimum Operations to Make the Array Alternating | LeetCode 2170 || LeetCode Weekly Contest 280 • Bro Coders • 3,017 views views

Watch 7 more video solutions →

Frequently Asked Questions

Is Minimum Operations to Make the Array Alternating easy or hard?
Minimum Operations to Make the Array Alternating is rated Medium on LeetCode. The implementation is straightforward once you recognize the frequency counting pattern, but identifying the need to track the top two candidates for each index group requires careful reasoning.
Minimum Operations to Make the Array Alternating Python/Java solution
The solution in Python or Java typically uses two hash maps to count frequencies at even and odd indices. After counting, determine the top two candidates in each map and compute the maximum preserved elements. The final answer is n minus that value.
How to solve Minimum Operations to Make the Array Alternating in O(n)?
Iterate through the array and maintain two frequency maps: one for even indices and one for odd indices. Track the top two most frequent values in each map. If the most frequent values differ, use them directly; otherwise combine the best candidate from one side with the second-best from the other to minimize operations.
What is the best approach for Minimum Operations to Make the Array Alternating?
The best approach uses frequency counting for values at even and odd indices separately. Track the two most frequent values in each group, then choose a pair with different values that maximizes preserved elements. This minimizes replacements and runs in O(n) time with O(k) extra space.
Is Minimum Operations to Make the Array Alternating asked at Google/Amazon/Meta?
Problems involving frequency counting, greedy selection, and array restructuring are common in interviews at companies like Google, Amazon, and Meta. Variants that require selecting optimal values for positions based on frequency appear frequently in coding interviews.
What data structure is used in Minimum Operations to Make the Array Alternating?
The main data structure is a hash table (or dictionary) to count frequencies of numbers at even and odd positions. These counts allow quick identification of the most frequent candidates needed for the greedy selection step.
What is the time complexity of Minimum Operations to Make the Array Alternating?
The optimal solution runs in O(n) time because the array is scanned once to compute frequency counts for even and odd indices. Additional work only involves comparing the top candidates from each group. Space complexity is O(k), where k is the number of distinct values.

Ready to solve this problem?

Practice Minimum Operations to Make the Array Alternating with our built-in code editor and test cases.

Practice on FleetCode
Previous

Minimum Deletions to Make Array Beautiful

Next

Minimum Number of Flips to Make the Binary String Alternating