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