420. Construct Uniform Parity Array II

Only parity matters, and a value can flip parity only by subtracting a strictly smaller odd element. The smallest element is the bottleneck: nothing can flip it, so the whole array must be able to converge on that element's parity.

Key insight

The concrete values of nums2 never matter — only whether each entry is odd or even. Track parity as 0 (even) or 1 (odd).

For an index i there are two moves:

• Keep: nums2[i] = nums1[i] → parity stays p_i.
• Subtract: nums2[i] = nums1[i] - nums1[j] where j != i and nums1[i] - nums1[j] >= 1. Because the elements are distinct and the difference must be positive, nums1[j] must be strictly smaller than nums1[i]. The new parity is (p_i + p_j) mod 2, since a - b shares the parity of a + b. So subtracting a smaller odd element flips the parity; subtracting a smaller even one leaves it unchanged.

The crucial restriction (versus part I) is the >= 1 rule: you may only borrow a flip from an element that is smaller than the current one.

Why the minimum decides it

Let m be the smallest element of nums1. It has no strictly smaller element to subtract, so it can only ever be kept — nums2 for that index is stuck at parity p_m. Therefore the common target parity is forced to be p_m.

Now check the two targets:

• Target even (p_m even): every odd element must flip to even, which needs a strictly smaller odd element. But the smallest odd element (if any exists) has no smaller odd to borrow from → it can never become even. So target even is reachable only when there are no odd elements at all, i.e. the array is already all even.
• Target odd (p_m odd, i.e. the global minimum is odd): every even element must flip to odd, which needs a strictly smaller odd element. Since the global minimum is odd, every even element has that odd minimum sitting below it → all evens can flip, and odds are simply kept.

Putting it together, the answer is true exactly when:

• the array is all even (target even, no changes needed), or
• the minimum element is odd (target odd is reachable for everyone).

return all_even(nums1) or (min(nums1) is odd)

Worked example

nums1 = [1, 4, 7] → parities [1, 0, 1]. The minimum is 1, which is odd, so aim for all odd. Keep 1 and 7. Flip the even 4 by subtracting the smaller odd 1: 4 - 1 = 3 (odd). Result nums2 = [1, 3, 7] — all odd → true.

Contrast nums1 = [2, 3]: not all even, and the minimum 2 is even. The odd 3 cannot flip (no smaller odd), and the even 2 cannot flip (no smaller odd below it) → false.

Complexity

• Time: O(n) — one pass to find the minimum and confirm whether every element is even.
• Space: O(1).

class Solution {
    public boolean uniformArray(int[] nums1) {
        // Only parity matters, and a value can flip its parity only by subtracting
        // a STRICTLY SMALLER odd element (the difference must be >= 1, elements
        // distinct). The minimum element can only be kept, so the common target
        // parity is forced to be the minimum's parity:
        //   - Target EVEN works only when the array is already all even.
        //   - Target ODD works when the global minimum is odd (it sits below every
        //     even element, letting each even flip to odd).
        int min = Integer.MAX_VALUE;
        boolean allEven = true;
        for (int x : nums1) {
            if ((x & 1) == 1) allEven = false;
            if (x < min) min = x;
        }
        return allEven || (min & 1) == 1;
    }
}