3876. Construct Uniform Parity Array II

Array
Math
Counting
Greedy

TIME

O(n)

SPACE

O(1)

Intuition

As in part I, only parities matter, but the extra condition nums1[i] - nums1[j] >= 1 restricts j to elements strictly smaller than nums1[i], and that changes the answer substantially.

Subtracting an even leaves the parity alone; subtracting an odd flips it. So:

index i can flip its parity iff some odd element is strictly smaller than nums1[i].

Let minOdd be the smallest odd value and minEven the smallest even value.

All even. Every odd element has to flip. But the smallest odd element has no odd below it, so it can never flip, it is stuck being odd. Therefore all-even is possible only when there are no odd elements at all.

All odd. Every even element has to flip, which needs an odd strictly below it. The binding case is the smallest even, so the condition is minOdd < minEven (or there are no evens, in which case it holds trivially).

Compare with part I, where subtraction had no ordering restriction: there, all-even merely required cntOdd != 1. Here the "smallest odd is stranded" argument kills it entirely whenever any odd exists.

Approach

Count odds and evens, and track minOdd and minEven in the same pass.
allEven = (cntOdd == 0).
allOdd = (cntEven == 0) or (cntOdd >= 1 and minOdd < minEven).
Return allEven or allOdd.

Complexity

Time: O(n), one pass
Space: O(1)

Edge Cases

n == 1 → no valid j; a single even satisfies all-even, a single odd satisfies all-odd
Any odd present → all-even is impossible, no matter how many odds there are
Smallest element is even with odds above it (Example 2: [2,3]) → the even 2 cannot flip → false
All even → all-even trivially true (Example 3)
All odd → all-odd trivially true
Only minOdd versus minEven matters; larger evens are automatically covered once the smallest one is

Code

from typing import List


class Solution:
    def canConstruct(self, nums1: List[int]) -> bool:
        """
        3876. Construct Uniform Parity Array II
        Time: O(n)
        Space: O(1)
        """
        INF = float("inf")
        min_odd = INF
        min_even = INF
        odd_count = 0

        for x in nums1:
            if x % 2:
                odd_count += 1
                if x < min_odd:
                    min_odd = x
            elif x < min_even:
                min_even = x

        even_count = len(nums1) - odd_count

        # The smallest odd can never flip (nothing odd is below it),
        # so any odd element blocks an all-even result.
        all_even = odd_count == 0
        # Every even must flip, which needs an odd strictly below it.
        all_odd = even_count == 0 or (odd_count >= 1 and min_odd < min_even)

        return all_even or all_odd

/**
 * 3876. Construct Uniform Parity Array II
 * Time: O(n)
 * Space: O(1)
 */
class Solution {
    public boolean canConstruct(int[] nums1) {
        long minOdd = Long.MAX_VALUE;
        long minEven = Long.MAX_VALUE;
        int oddCount = 0;

        for (int x : nums1) {
            if (x % 2 != 0) {
                oddCount++;
                if (x < minOdd) {
                    minOdd = x;
                }
            } else if (x < minEven) {
                minEven = x;
            }
        }

        int evenCount = nums1.length - oddCount;

        // The smallest odd can never flip (nothing odd is below it),
        // so any odd element blocks an all-even result.
        boolean allEven = oddCount == 0;
        // Every even must flip, which needs an odd strictly below it.
        boolean allOdd = evenCount == 0 || (oddCount >= 1 && minOdd < minEven);

        return allEven || allOdd;
    }
}