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:
nums[2] by 1, resulting in nums = [-2, -3, 2, 4].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:
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] <= 109Problem 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.
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.
Python
Java
C++
Go
TypeScript
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Pattern Enumeration | O(n) | O(1) | Clear baseline approach when evaluating both possible parity patterns separately. |
| Greedy Single Pass | O(n) | O(1) | Preferred solution for interviews and production code. Counts mismatches for both patterns during one traversal. |
Leetcode 3854 | Minimum Operations to Make Array Parity Alternating | Beginner friendly • CodeWithMeGuys • 578 views views
Watch 3 more video solutions →Practice Minimum Operations to Make Array Parity Alternating with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor