3876. Construct Uniform Parity Array II

Problem Overview

You may keep nums1[i] or replace it with a positive difference nums1[i] - nums1[j].

Intuition

You may keep nums1[i] or replace it with a positive difference nums1[i] - nums1[j]. All-even nums2 is only possible when nums1 is already all even, because subtracting an odd from an even yields an odd. When both parities appear, the only hope is an all-odd array. Every even must subtract the smallest odd so the result stays positive and odd, which means the smallest even must be strictly larger than the smallest odd.

Algorithm

1Scan once and track the minimum odd and the minimum even.
2If either is missing, nums1 is already uniform. Return true.
3Otherwise return whether minEven is greater than minOdd.

Example Walkthrough

Input: nums1 = [1, 4, 7]

1.minOdd = 1, minEven = 4, and 4 > 1.
2.Keep 1 and 7. Set 4 - 1 = 3.
3.nums2 = [1, 3, 7] is all odd.

Output: true

Common Pitfalls

•Unlike part I, mixed parity is not always possible. An even smaller than every odd cannot become a positive odd difference.
•Use a single pass for both minima. Two scans work but are unnecessary.
•Strict inequality matters: minEven must be greater than minOdd, not equal.
•All-even and all-odd inputs succeed by copying nums1.

3876.cs

// Approach: With difference >= 1, all-even is only possible if nums1 is already
// all even. All-odd works when every even can subtract the smallest odd (so
// min even must be > min odd), or when there is no even. One pass tracks both.
// Complexity: O(n) time and O(1) extra space.
public class Solution
{
    public bool UniformArray(int[] nums1)
    {
        int minOdd = int.MaxValue;
        int minEven = int.MaxValue;

        foreach (int x in nums1)
        {
            if ((x & 1) == 0)
            {
                if (x < minEven)
                    minEven = x;
            }
            else if (x < minOdd)
            {
                minOdd = x;
            }
        }

        return minOdd == int.MaxValue || minEven == int.MaxValue || minEven > minOdd;
    }
}

Was this solution helpful?