LeetCode 3854 - Minimum Operations to Make Array Parity Alternating

Difficulty: 🟡 Medium
Topics: Array, Greedy

Solution

Problem Understanding

We are given an integer array nums. An array is called parity alternating when every pair of adjacent elements has different parity. In other words, the parity pattern must alternate between even and odd.

For an array of length n, there are only two possible valid parity patterns:

Even, Odd, Even, Odd, ...
Odd, Even, Odd, Even, ...

In one operation, we may increase or decrease any element by exactly 1.

The output consists of two values:

answer[0] is the minimum number of operations required to transform the array into a parity alternating array.
answer[1] is the minimum possible value of max(nums) - min(nums) among all parity alternating arrays that can be obtained using exactly answer[0] operations.

The constraints are large:

n can be as large as 100000.
Values can be as small as -10^9 and as large as 10^9.

These constraints immediately rule out any approach that tries to enumerate all possible transformed arrays.

An important observation is that changing a number's parity requires exactly one operation. If a number already has the desired parity, changing it would waste operations and prevent us from achieving the minimum operation count.

Some important edge cases are:

Arrays of length 1, which are automatically parity alternating.
Arrays that are already parity alternating, where the minimum operation count is 0.
Arrays where both alternating parity patterns require the same number of parity fixes.
Large positive and negative values, where arithmetic must remain within 64 bit integer limits.

Approaches

Brute Force

A brute force solution would first determine which elements need parity changes and then try every possible way of applying +1 or -1 to those elements.

Suppose k elements need their parity flipped. Each such element has two possible resulting values:

x - 1
x + 1

The brute force method would examine all 2^k combinations, compute the resulting range for each combination, and choose the best one.

This is correct because it explicitly checks every feasible minimum-operation transformation.

Unfortunately, k can be as large as 100000, making 2^k completely infeasible.

Key Insight

The minimum number of operations is easy to compute.

For a fixed alternating pattern:

If an element already has the required parity, it costs 0.
If it has the wrong parity, it costs 1.

Therefore, the minimum operation count for a pattern is simply the number of parity mismatches.

After fixing the minimum operation count, every mismatched element has exactly two possible final values:

x - 1
x + 1

Every matched element is fixed at x.

Now the problem becomes:

Choose one allowed value from each position so that the range (max - min) is minimized.

This can be reformulated as:

Find the smallest interval [L, R] that contains at least one allowed value from every position.

Each position contributes either:

one allowed value, or
two allowed values.

We create all allowed values, sort them, and use a sliding window to find the smallest value interval containing at least one candidate from every index.

This turns the problem into a classic "smallest range covering all colors" problem.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(2^k)	O(k)	Tries every ±1 choice for mismatched elements
Optimal	O(n log n)	O(n)	Sliding window on sorted candidate values

Algorithm Walkthrough

Step 1: Evaluate one alternating parity pattern

Fix a target pattern, for example:

index 0 even
index 1 odd
index 2 even
...

For every element:

If its parity already matches the target parity, it contributes one allowed value {x}.
Otherwise, it must be changed exactly once, so it contributes two allowed values {x - 1, x + 1} and increases the operation count by one.

Step 2: Compute the minimum operation count

Count how many elements have the wrong parity relative to the chosen pattern.

This count is the minimum number of operations required for that pattern.

Step 3: Build candidate points

For every allowed value, create a pair:

(value, index)

Each index contributes either one or two points.

Step 4: Sort all candidate points

Sort the pairs by value.

After sorting, every possible interval in value space becomes a contiguous segment of this sorted list.

Step 5: Use a sliding window

Maintain a window over the sorted points.

Track how many different indices are represented inside the current window.

Expand the right boundary until every index appears at least once.

When all indices are represented:

The current window defines a valid interval.
Update the best range.
Move the left boundary forward while preserving validity.

Step 6: Obtain the minimum range for this parity pattern

The smallest valid window width gives the minimum achievable value of:

max(nums) - min(nums)

among all minimum-operation transformations for this parity pattern.

Step 7: Evaluate both alternating patterns

Compute:

even-odd-even-odd...
odd-even-odd-even...

Let:

ops1, range1
ops2, range2

If one pattern uses fewer operations, choose it.

If both patterns use the same minimum number of operations, choose the smaller range.

Why it works

For a fixed parity pattern, every minimum-operation solution corresponds to choosing exactly one allowed value from each position. A range is feasible if and only if it contains at least one allowed value from every position. Therefore, finding the smallest feasible range is equivalent to finding the smallest interval covering all positions. The sliding window over sorted candidate values enumerates exactly these intervals and returns the minimum width. Evaluating both alternating parity patterns guarantees that the globally optimal answer is found.

Python Solution

from typing import List
from collections import defaultdict

class Solution:
    def makeParityAlternating(self, nums: List[int]) -> List[int]:
        n = len(nums)

        def solve(start_even: bool):
            operations = 0
            points = []

            for i, x in enumerate(nums):
                target_even = ((i % 2) == 0) == start_even
                current_even = (x & 1) == 0

                if current_even == target_even:
                    points.append((x, i))
                else:
                    operations += 1
                    points.append((x - 1, i))
                    points.append((x + 1, i))

            points.sort()

            count = defaultdict(int)
            covered = 0
            left = 0
            best_range = float("inf")

            for right in range(len(points)):
                value_r, idx_r = points[right]

                if count[idx_r] == 0:
                    covered += 1
                count[idx_r] += 1

                while covered == n:
                    value_l, idx_l = points[left]
                    best_range = min(best_range, value_r - value_l)

                    count[idx_l] -= 1
                    if count[idx_l] == 0:
                        covered -= 1

                    left += 1

            return operations, best_range

        ops1, range1 = solve(True)
        ops2, range2 = solve(False)

        if ops1 < ops2:
            return [ops1, range1]

        if ops2 < ops1:
            return [ops2, range2]

        return [ops1, min(range1, range2)]

The implementation follows the algorithm directly. The helper function evaluates one parity pattern. It first determines which elements already satisfy the target parity and which require exactly one parity-changing operation. This simultaneously computes the minimum operation count and builds the set of allowed values for each index.

All allowed values are converted into (value, index) pairs and sorted. The sliding window then searches for the smallest value interval that contains at least one candidate from every index. The width of the best interval is the minimum achievable range for that parity pattern.

Finally, both alternating patterns are evaluated, and the result with the smaller operation count is selected. If both require the same number of operations, the smaller range is chosen.

Go Solution

package main

import (
	"math"
	"sort"
)

func makeParityAlternating(nums []int) []int {
	n := len(nums)

	type Point struct {
		value int
		idx   int
	}

	solve := func(startEven bool) (int, int) {
		operations := 0
		points := make([]Point, 0, 2*n)

		for i, x := range nums {
			targetEven := ((i%2) == 0) == startEven
			currentEven := (x & 1) == 0

			if currentEven == targetEven {
				points = append(points, Point{x, i})
			} else {
				operations++
				points = append(points, Point{x - 1, i})
				points = append(points, Point{x + 1, i})
			}
		}

		sort.Slice(points, func(i, j int) bool {
			return points[i].value < points[j].value
		})

		count := make([]int, n)
		covered := 0
		left := 0
		bestRange := math.MaxInt64

		for right := 0; right < len(points); right++ {
			idxR := points[right].idx

			if count[idxR] == 0 {
				covered++
			}
			count[idxR]++

			for covered == n {
				width := points[right].value - points[left].value
				if width < bestRange {
					bestRange = width
				}

				idxL := points[left].idx
				count[idxL]--

				if count[idxL] == 0 {
					covered--
				}

				left++
			}
		}

		return operations, bestRange
	}

	ops1, range1 := solve(true)
	ops2, range2 := solve(false)

	if ops1 < ops2 {
		return []int{ops1, range1}
	}

	if ops2 < ops1 {
		return []int{ops2, range2}
	}

	if range2 < range1 {
		range1 = range2
	}

	return []int{ops1, range1}
}

The Go version uses a slice of structures instead of Python tuples and a fixed-size integer slice instead of a hash map for coverage counts. Since indices range from 0 to n-1, an array-based counter is more efficient. All arithmetic safely fits within 64 bit signed integer limits because values differ by at most one from the original input values.

Worked Examples

Example 1

Input:

[-2, -3, 1, 4]

Target pattern:

Even, Odd, Even, Odd

Index	Value	Current Parity	Target Parity	Allowed Values
0	-2	Even	Even	{-2}
1	-3	Odd	Odd	{-3}
2	1	Odd	Even	{0, 2}
3	4	Even	Odd	{3, 5}

Operations:

Sorted candidate values:

(-3,1)
(-2,0)
(0,2)
(2,2)
(3,3)
(5,3)

The smallest window covering all four indices is:

[-3, 3]

Range:

3 - (-3) = 6

Answer:

[2, 6]

Example 2

Input:

[0, 2, -2]

Target pattern:

Even, Odd, Even

Index	Value	Allowed Values
0	0	{0}
1	2	{1, 3}
2	-2	{-2}

Operations:

Sorted values:

-2, 0, 1, 3

Smallest covering interval:

[-2, 1]

Range:

Answer:

[1, 3]

Example 3

Input:

[7]

Only one element exists.

Allowed values:

{7}

Operations:

Range:

7 - 7 = 0

Answer:

[0, 0]

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n log n)	Sorting at most `2n` candidate values dominates
Space	O(n)	Stores candidate points and coverage counts

The number of candidate values is at most 2n because each index contributes either one value or two values. Sorting these values costs O(n log n), and the sliding window processes each point at most twice, giving linear time after sorting.

Test Cases

s = Solution()

assert s.makeParityAlternating([-2, -3, 1, 4]) == [2, 6]      # example 1
assert s.makeParityAlternating([0, 2, -2]) == [1, 3]          # example 2
assert s.makeParityAlternating([7]) == [0, 0]                 # length 1

assert s.makeParityAlternating([2, 3, 4, 5]) == [0, 3]        # already alternating
assert s.makeParityAlternating([2, 4, 6, 8]) == [2, 5]        # all even
assert s.makeParityAlternating([1, 3, 5, 7]) == [2, 5]        # all odd

assert s.makeParityAlternating([0, 1]) == [0, 1]              # smallest alternating pair
assert s.makeParityAlternating([0, 0]) == [1, 1]              # two equal evens

assert s.makeParityAlternating([-1000000000]) == [0, 0]       # large negative
assert s.makeParityAlternating([1000000000]) == [0, 0]        # large positive

assert s.makeParityAlternating([1, 1, 1, 1, 1]) == [2, 2]     # repeated values
assert s.makeParityAlternating([-1, -1, -1, -1]) == [2, 2]    # repeated negatives

Test Summary

Test	Why
`[-2,-3,1,4]`	Official example 1
`[0,2,-2]`	Official example 2
`[7]`	Length one array
`[2,3,4,5]`	Already alternating
`[2,4,6,8]`	All even values
`[1,3,5,7]`	All odd values
`[0,1]`	Smallest valid alternating array
`[0,0]`	Single parity correction needed
`[-1000000000]`	Large negative boundary
`[1000000000]`	Large positive boundary
`[1,1,1,1,1]`	Many duplicate odd values
`[-1,-1,-1,-1]`	Duplicate negative values

Edge Cases

Array Length One

An array with a single element is automatically parity alternating because there are no adjacent pairs to violate the condition. The algorithm handles this naturally because the candidate set contains exactly one value, the operation count is zero, and the sliding window immediately finds a range of zero.

Already Alternating Arrays

When every element already matches the target parity pattern, no operations are needed. Each index contributes only one candidate value, namely its original value. The algorithm therefore computes the range of the original array and correctly returns zero operations.

Multiple Optimal Parity Patterns

Sometimes both alternating parity patterns require the same minimum number of operations. In that situation, the first objective does not distinguish between them. The implementation explicitly evaluates both patterns and returns the smaller achievable range among those tied minimum-operation solutions.

Large Positive and Negative Values

Values may be as small as -10^9 or as large as 10^9. Since every modified value differs from the original by only one, all intermediate values remain safely within 64 bit integer limits. The algorithm performs only comparisons, additions, and subtractions, so no overflow issues arise.