LeetCode 3876 - Construct Uniform Parity Array II

The problem asks us to determine whether we can construct a new array nums2 from a given array nums1 of distinct integers such that all elements in nums2 have the same parity (all even or all odd).

leetcodemediumarraymath

LeetCode Problem 3876

Difficulty: 🟡 Medium
Topics: Array, Math

Solution

Problem Understanding

The problem asks us to determine whether we can construct a new array nums2 from a given array nums1 of distinct integers such that all elements in nums2 have the same parity (all even or all odd). For each index i, we have two options: we can either take nums1[i] directly, or subtract any other element nums1[j] (with j != i) from nums1[i] as long as the result is at least 1. The output is a boolean indicating whether this construction is possible.

The input nums1 is a list of distinct integers with length n up to 10^5 and values up to 10^9. The constraints imply that a brute-force approach checking all combinations is infeasible due to exponential growth in possibilities. Important edge cases include arrays of length 1, arrays where all numbers are consecutive integers, and arrays where some numbers are very large compared to others. The guarantee that nums1 has distinct elements ensures that nums1[i] - nums1[j] is always at least 1 for some valid choice if nums1[i] is not the smallest element.

Approaches

The brute-force approach is to try every possible combination of choices for nums2[i]. For each index, we could choose nums1[i] or subtract any other element, checking if the resulting array has uniform parity. This approach is correct because it exhaustively explores all valid constructions, but it is too slow due to the combinatorial explosion for large n.

The key observation for an optimal solution is that parity is preserved under subtraction. Subtracting two numbers of the same parity results in an even number, while subtracting two numbers of different parity results in an odd number. Therefore, it is enough to examine the parities of the numbers in nums1. If nums1 contains both odd and even numbers, we can always subtract an appropriate number to achieve a uniform parity for the resulting array, except in trivial two-element arrays where both parities are different. The optimal solution only needs to count how many numbers are odd and even and check the feasibility.

Approach Time Complexity Space Complexity Notes
Brute Force O(2^n * n) O(n) Tries all possible combinations of assignments
Optimal O(n) O(1) Uses parity properties to decide feasibility in linear time

Algorithm Walkthrough

  1. Count the number of odd and even elements in nums1.
  2. If nums1 contains only one element, return true because a single element is trivially uniform in parity.
  3. If nums1 contains more than one element and all numbers are either all odd or all even, return true.
  4. If there are exactly two elements with different parity, return false because subtracting the only other element would produce a number less than 1 in some cases or cannot make parity uniform.
  5. Otherwise, return true because with at least three numbers, we can always subtract an appropriate element to adjust parity as needed.

Why it works: By analyzing parities and their interactions under subtraction, we know that the only impossible case occurs when we have exactly two numbers with different parity. In all other cases, the flexibility of subtracting a different element allows construction of a uniform parity array.

Python Solution

class Solution:
    def uniformArray(self, nums1: list[int]) -> bool:
        n = len(nums1)
        if n == 1:
            return True
        
        odd_count = sum(num % 2 for num in nums1)
        even_count = n - odd_count
        
        if odd_count == 0 or even_count == 0:
            return True
        
        if n == 2:
            return False
        
        return True

In this Python implementation, we first check for the single-element case. We then count odd and even numbers. If all numbers share the same parity, the result is true. For arrays of length two with mixed parity, the result is false. In all other cases, we can construct a uniform parity array.

Go Solution

func uniformArray(nums1 []int) bool {
    n := len(nums1)
    if n == 1 {
        return true
    }
    
    oddCount := 0
    for _, num := range nums1 {
        if num%2 != 0 {
            oddCount++
        }
    }
    evenCount := n - oddCount
    
    if oddCount == 0 || evenCount == 0 {
        return true
    }
    
    if n == 2 {
        return false
    }
    
    return true
}

The Go version follows the same logic. We count odd numbers with a loop and derive the number of even numbers. We handle single-element arrays, arrays with uniform parity, and two-element mixed-parity arrays explicitly. The rest are guaranteed to be possible.

Worked Examples

Example 1: nums1 = [1, 4, 7]

Index nums1[i] Choice nums2[i]
0 1 nums1[i] 1
1 4 nums1[i] - nums1[0] 3
2 7 nums1[i] 7

All elements in nums2 are odd, return true.

Example 2: nums1 = [2, 3]

Two elements with different parity, return false.

Example 3: nums1 = [4, 6]

All elements are even, return true.

Complexity Analysis

Measure Complexity Explanation
Time O(n) Single pass to count odd and even numbers
Space O(1) Only a few counters are used

Counting parities is linear in the array size, and no extra storage proportional to n is needed.

Test Cases

assert Solution().uniformArray([1, 4, 7]) == True  # mixed numbers, length 3
assert Solution().uniformArray([2, 3]) == False    # two numbers, different parity
assert Solution().uniformArray([4, 6]) == True     # all even
assert Solution().uniformArray([1]) == True        # single element
assert Solution().uniformArray([1, 3, 5, 7]) == True  # all odd
assert Solution().uniformArray([2, 4, 6, 8]) == True  # all even
assert Solution().uniformArray([1, 2, 3]) == True      # mixed numbers, length > 2
Test Why
[1,4,7] Demonstrates creating uniform parity from mixed elements
[2,3] Edge case with two elements of different parity
[4,6] Uniform parity array already even
[1] Single-element trivial case
[1,3,5,7] All odd elements
[2,4,6,8] All even elements
[1,2,3] Mixed elements with more than two numbers

Edge Cases

A single-element array is always valid because the parity is trivially uniform. Arrays with exactly two elements of different parity are impossible to convert because subtraction cannot create a uniform parity without violating the >=1 constraint. Arrays with more than two elements, even if mixed, can always adjust parity using subtraction to achieve a uniform array because at least one number can act as a reference for subtraction, ensuring the resulting numbers all share the same parity.