Skip to main content
Talentd

Minimum Operations to Make Array Parity Alternating - Solution & Explanation

MediumArrayGreedy14 min read
Practice this problem

Problem Statement

You are given an integer array nums.

An array is called parity alternating if for every index i where 0 <= i < n - 1, nums[i] and nums[i + 1] have different parity (one is even and the other is odd).

In one operation, you may choose any index i and either increase nums[i] by 1 or decrease nums[i] by 1.

Return an integer array answer of length 2 where:

  • answer[0] is the minimum number of operations required to make the array parity alternating.
  • answer[1] is the minimum possible value of max(nums) - min(nums) taken over all arrays that are parity alternating and can be obtained by performing exactly answer[0] operations.

An array of length 1 is considered parity alternating.

 

Example 1:

Input: nums = [-2,-3,1,4]

Output: [2,6]

Explanation:

Applying the following operations:

  • Increase nums[2] by 1, resulting in nums = [-2, -3, 2, 4].
  • Decrease nums[3] by 1, resulting in nums = [-2, -3, 2, 3].

The resulting array is parity alternating, and the value of max(nums) - min(nums) = 3 - (-3) = 6 is the minimum possible among all parity alternating arrays obtainable using exactly 2 operations.

Example 2:

Input: nums = [0,2,-2]

Output: [1,3]

Explanation:

Applying the following operation:

  • Decrease nums[1] by 1, resulting in nums = [0, 1, -2].

The resulting array is parity alternating, and the value of max(nums) - min(nums) = 1 - (-2) = 3 is the minimum possible among all parity alternating arrays obtainable using exactly 1 operation.

Example 3:

Input: nums = [7]

Output: [0,0]

Explanation:

No operations are required. The array is already parity alternating, and the value of max(nums) - min(nums) = 7 - 7 = 0, which is the minimum possible.

 

Constraints:

  • 1 <= nums.length <= 105
  • -109 <= nums[i] <= 109

Approach Overview

Problem Overview: You are given an integer array and need the minimum number of operations to make the parity of elements alternate (even, odd, even, odd or odd, even, odd, even). Each operation changes the parity of a single element. The task is to determine the smallest number of changes required.

Approach 1: Pattern Enumeration (O(n) time, O(1) space)

Only two valid parity patterns exist for any alternating array: starting with even (even, odd, even...) or starting with odd (odd, even, odd...). Iterate through the array and compare each element’s parity with the expected parity for both patterns. If the current value does not match the required parity, count it as one operation. After scanning the array, you get two operation counts—one for each pattern—and the minimum of the two is the answer.

Approach 2: Greedy Single Pass (O(n) time, O(1) space)

The greedy observation: the optimal result depends only on whether each index matches its required parity. During one traversal, track mismatches for both possible starting patterns simultaneously. For index i, the expected parity is determined by i % 2. If the array starts with even, indices 0,2,4... must be even; if it starts with odd, those positions must be odd. Increment mismatch counters accordingly while iterating once. Return the smaller mismatch count. This avoids extra passes and works because each position can be fixed independently.

This problem is fundamentally about recognizing a fixed set of valid configurations and computing the cost to convert the array into each one. No reordering or complex state tracking is required—just parity checks and counters.

Recommended for interviews: The greedy single-pass solution is what interviewers expect. It demonstrates that you recognize the two valid parity patterns and compute mismatch counts efficiently in O(n) time with constant space. A naive approach might try to simulate conversions or rebuild arrays, but the optimal solution simply counts parity violations while iterating the array. This pattern appears frequently in array problems and parity-based greedy decision problems.

Solution

We can try to transform the array into two different parity-alternating forms: one where even numbers are at even indices and odd numbers are at odd indices, and another where odd numbers are at even indices and even numbers are at odd indices.

For each form, we calculate the number of operations needed and the maximum and minimum values of the resulting array. Finally, we choose the plan with fewer operations; if the operation counts are equal, we choose the plan with the smaller difference between the maximum and minimum values.

We define a function f(k), where k represents the desired parity of the numbers placed at even indices (where k=0 means even and k=1 means odd). The function f(k) computes the number of operations needed to transform the array into the corresponding parity-alternating form, as well as the maximum and minimum values of the resulting array.

In the function f(k), we iterate over each element in the array. If the parity of the current element does not match the expected parity, we perform one operation to adjust it. To minimize the difference between the maximum and minimum values, we adjust the current element to the nearest number, which is either the current element plus 1 or minus 1, depending on whether the current element equals the minimum or maximum value in the array. If the current element equals the minimum value, we increase it by 1; if it equals the maximum value, we decrease it by 1; otherwise, we can choose to either increase or decrease by 1. We then update the current maximum and minimum values. Finally, the function f(k) returns the operation count and the difference between the maximum and minimum values of the resulting array.

The time complexity is O(n), where n is the length of the array nums. The space complexity is O(1), as we only use a constant amount of extra space.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Pattern EnumerationO(n)O(1)Clear baseline approach when evaluating both possible parity patterns separately.
Greedy Single PassO(n)O(1)Preferred solution for interviews and production code. Counts mismatches for both patterns during one traversal.

Video Solution

Leetcode 3854 | Minimum Operations to Make Array Parity Alternating | Beginner friendly • CodeWithMeGuys • 688 views views

Watch 3 more video solutions →

Frequently Asked Questions

Is Minimum Operations to Make Array Parity Alternating easy or hard?
The problem is typically classified as Medium because the trick is recognizing that only two valid parity patterns exist. Once that insight is clear, the implementation becomes a straightforward O(n) greedy scan.
Minimum Operations to Make Array Parity Alternating Python/Java solution
Most implementations follow the same logic: iterate through the array, compare each element's parity with the expected parity for two patterns, and track mismatches. The same O(n) greedy approach translates directly to Python, Java, C++, Go, and TypeScript.
How to solve Minimum Operations to Make Array Parity Alternating in O(n)?
Traverse the array once while tracking mismatches for two patterns: starting with even and starting with odd. For each index i, compute the expected parity using i % 2 and compare it with the element's parity. Increment the mismatch counters accordingly and return the smaller value after the scan.
What is the best approach for Minimum Operations to Make Array Parity Alternating?
The best approach is a greedy mismatch-counting strategy. Evaluate the two possible parity patterns (even-odd-even and odd-even-odd) and count how many indices violate each pattern. The minimum mismatch count gives the required operations. This runs in O(n) time and O(1) space.
Is Minimum Operations to Make Array Parity Alternating asked at Google/Amazon/Meta?
Parity pattern and greedy mismatch-count problems appear frequently in interviews at companies like Amazon, Google, and Meta. While the exact problem number may vary, the technique of evaluating fixed patterns and minimizing changes is a common interview theme.
What data structure is used in Minimum Operations to Make Array Parity Alternating?
The solution primarily uses a simple array traversal with integer counters. No additional data structures such as hash maps or heaps are needed, making it a lightweight greedy algorithm over the input array.
What is the time complexity of Minimum Operations to Make Array Parity Alternating?
The optimal solution runs in O(n) time because the array is scanned once to count parity mismatches. Space complexity is O(1) since only a few counters are maintained and no additional data structures are required.

Ready to solve this problem?

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

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays