1class Solution {
2    // The input array we operate on
3    private int[] nums;
4    // The minimum value found in the array
5    private int min;
6    // The maximum value found in the array
7    private int max;
8    // A "large" sentinel value used to avoid integer overflow during min/max tracking
9    private static final int INF = Integer.MAX_VALUE / 2;
10
11    public int[] makeParityAlternating(int[] nums) {
12        // A single-element array is already valid: zero changes, range treated as 0
13        if (nums.length == 1) {
14            return new int[] {0, 0};
15        }
16        this.nums = nums;
17
18        // Compute the global minimum and maximum of the array
19        min = INF;
20        max = -INF;
21        for (int value : nums) {
22            min = Math.min(min, value);
23            max = Math.max(max, value);
24        }
25
26        // Evaluate both possible parity patterns:
27        // k = 0 -> positions where (value - index) is even
28        // k = 1 -> positions where (value - index) is odd
29        int[] result0 = f(0);
30        int[] result1 = f(1);
31
32        // Prefer the pattern requiring fewer changes;
33        // if equal, prefer the one with the smaller resulting range
34        if (result0[0] != result1[0]) {
35            return result0[0] < result1[0] ? result0 : result1;
36        }
37        return result0[1] <= result1[1] ? result0 : result1;
38    }
39
40    /**
41     * Evaluates the cost and resulting range for a target parity pattern.
42     *
43     * @param k the target parity of (value - index): 0 for even, 1 for odd
44     * @return an array {changeCount, range}, where changeCount is the number of
45     *         elements that must be adjusted and range is the max-min spread
46     *         (at least 1) of the values after adjustment
47     */
48    private int[] f(int k) {
49        // Number of elements that violate the target parity and must be changed
50        int count = 0;
51        // Track the minimum value after potential adjustments
52        int low = INF;
53        // Track the maximum value after potential adjustments
54        int high = -INF;
55
56        for (int i = 0; i < nums.length; i++) {
57            int x = nums[i];
58            // Check whether (x - i) matches the desired parity k
59            if (((x - i) & 1) != k) {
60                count++;
61                // Adjust the value by 1 to fix the parity,
62                // nudging boundary values inward to keep the range tight
63                if (x == min) {
64                    x += 1;
65                } else if (x == max) {
66                    x -= 1;
67                }
68            }
69            low = Math.min(low, x);
70            high = Math.max(high, x);
71        }
72
73        // Ensure the reported range is at least 1
74        return new int[] {count, Math.max(1, high - low)};
75    }
76}
77

1class Solution {
2public:
3    vector<int> makeParityAlternating(vector<int>& nums) {
4        // Edge case: a single element requires no changes,
5        // and the spread is defined as 0 here.
6        if (nums.size() == 1) {
7            return {0, 0};
8        }
9
10        // Find the global minimum and maximum values in one pass.
11        auto [minIter, maxIter] = minmax_element(nums.begin(), nums.end());
12        int globalMin = *minIter;
13        int globalMax = *maxIter;
14
15        // Lambda that evaluates a target parity pattern.
16        // 'parity' is the expected value of (x - i) & 1 for every index i.
17        // It returns: { number_of_changes, resulting_spread }.
18        auto evaluate = [&](int parity) {
19            int changeCount = 0;        // How many elements violate the pattern.
20            int spreadMin = INT_MAX;    // Minimum value after adjustments.
21            int spreadMax = INT_MIN;    // Maximum value after adjustments.
22
23            for (int i = 0; i < static_cast<int>(nums.size()); i++) {
24                int value = nums[i];
25
26                // If the current element's parity does not match the target,
27                // it must be adjusted (toggled) to fix the alternating pattern.
28                if (((value - i) & 1) != parity) {
29                    changeCount++;
30
31                    // Adjust the value inward so the spread is minimized:
32                    // bump the global minimum up, or pull the global maximum down.
33                    if (value == globalMin) {
34                        ++value;
35                    } else if (value == globalMax) {
36                        --value;
37                    }
38                }
39
40                // Track the running min/max of the (possibly adjusted) values.
41                spreadMin = min(spreadMin, value);
42                spreadMax = max(spreadMax, value);
43            }
44
45            // The spread is at least 1 to avoid a degenerate zero result.
46            return vector<int>{changeCount, max(1, spreadMax - spreadMin)};
47        };
48
49        // Try both possible target parities and pick the lexicographically
50        // smaller result (fewer changes first, then smaller spread).
51        vector<int> resultEven = evaluate(0);
52        vector<int> resultOdd = evaluate(1);
53
54        return resultEven < resultOdd ? resultEven : resultOdd;
55    }
56};
57

1/**
2 * Determines the optimal parity-alternating configuration for the given array.
3 *
4 * For each index i, the "target parity" is derived from (nums[i] - i). We try two
5 * possible alternating patterns (k = 0 and k = 1), counting how many elements break
6 * the pattern and tracking the resulting spread (max - min) after adjusting the
7 * boundary values (the current global min/max) by one step.
8 *
9 * The result with the smaller mismatch count wins; ties are broken by the smaller spread.
10 *
11 * @param nums - The input array of numbers.
12 * @returns A tuple [count, spread] describing the best configuration.
13 */
14function makeParityAlternating(nums: number[]): number[] {
15    // A single-element array trivially needs no changes and has zero spread.
16    if (nums.length === 1) {
17        return [0, 0];
18    }
19
20    // Precompute the global minimum and maximum of the array.
21    const minValue = Math.min(...nums);
22    const maxValue = Math.max(...nums);
23
24    /**
25     * Evaluates a single alternating pattern.
26     *
27     * @param targetParity - The desired parity (0 or 1) of (nums[i] - i).
28     * @returns A tuple [mismatchCount, spread] where:
29     *          - mismatchCount is the number of elements violating the pattern,
30     *          - spread is the value range (max - min), at least 1.
31     */
32    const evaluatePattern = (targetParity: number): number[] => {
33        let mismatchCount = 0;
34        let localMin = Number.MAX_SAFE_INTEGER;
35        let localMax = Number.MIN_SAFE_INTEGER;
36
37        for (let i = 0; i < nums.length; i++) {
38            let value = nums[i];
39
40            // Check whether this element violates the desired parity pattern.
41            if (((value - i) & 1) !== targetParity) {
42                mismatchCount++;
43
44                // Adjust boundary values by one step to reduce the spread when possible.
45                if (value === minValue) {
46                    ++value;
47                } else if (value === maxValue) {
48                    --value;
49                }
50            }
51
52            // Update the local minimum and maximum after any adjustment.
53            localMin = Math.min(localMin, value);
54            localMax = Math.max(localMax, value);
55        }
56
57        // The spread is at least 1 to avoid a degenerate zero range.
58        return [mismatchCount, Math.max(1, localMax - localMin)];
59    };
60
61    // Evaluate both possible alternating patterns.
62    const resultEven = evaluatePattern(0);
63    const resultOdd = evaluatePattern(1);
64
65    // Prefer the pattern with fewer mismatches.
66    if (resultEven[0] !== resultOdd[0]) {
67        return resultEven[0] < resultOdd[0] ? resultEven : resultOdd;
68    }
69
70    // On a tie in mismatch count, prefer the pattern with the smaller spread.
71    return resultEven[1] <= resultOdd[1] ? resultEven : resultOdd;
72}
73