LeetCode 3875 - Construct Uniform Parity Array I

Difficulty: 🟢 Easy
Topics: Array, Math

Solution

Problem Understanding

The problem asks us to determine if it is possible to construct a new array nums2 of the same length as nums1 where all elements are either all odd or all even. For each element nums2[i], we can either copy the corresponding element from nums1[i] directly, or we can set it as the difference between nums1[i] and another element nums1[j] with j != i.

The input array nums1 contains distinct positive integers and can be of length from 1 to 100. The output is a boolean: true if we can construct a uniform parity array, and false otherwise.

The key insight is that any difference between two integers preserves the parity pattern: subtracting an odd from an odd gives an even, subtracting an even from an even gives an even, and subtracting odd and even yields odd. This means that the parity of the differences between elements and the original numbers determines whether we can achieve uniform parity.

Important edge cases include arrays with a single element, arrays where all numbers are already even or odd, and arrays with a mixture of even and odd numbers where differences must be used to adjust parity.

Approaches

A brute-force approach would attempt every possible combination of choices for each element: either keeping it or subtracting any other element. This would guarantee the correct answer because it explores all possibilities. However, the complexity is factorial in the worst case (O(n!)), making it infeasible for n = 100.

The optimal approach comes from observing that we only need to consider the parities. If there exists at least one even and one odd number, we can use their differences to generate either parity. Specifically, subtracting an odd from an even (or vice versa) gives an odd, while subtracting numbers with the same parity gives an even. Therefore, it is always possible to construct a uniform parity array if the array has both parities. If all numbers are already the same parity, we can just copy them directly.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n!)	O(n)	Try all possible selections of nums2[i] for all i
Optimal	O(n)	O(1)	Check if nums1 contains both even and odd, then return true; otherwise return true if already uniform parity

Algorithm Walkthrough

Initialize two flags has_even and has_odd to False. These will track whether nums1 contains at least one even and one odd number.
Iterate over each element num in nums1. For each element, check if it is even or odd.
If the number is even, set has_even = True. If it is odd, set has_odd = True.
After scanning all elements, check the flags:

If both has_even and has_odd are True, then return True because differences between even and odd elements can generate any parity, allowing construction of a uniform parity array.
Otherwise, return True anyway because all numbers are already of the same parity.

The function returns the final boolean result.

Why it works: The property of integer parity ensures that differences between numbers of opposite parity produce odd numbers, and differences between numbers of the same parity produce even numbers. Therefore, if there is at least one even and one odd, we can always construct a uniform array using differences. If all numbers already share the same parity, copying them suffices.

Python Solution

class Solution:
    def uniformArray(self, nums1: list[int]) -> bool:
        has_even = False
        has_odd = False
        
        for num in nums1:
            if num % 2 == 0:
                has_even = True
            else:
                has_odd = True
        
        return True  # It's always possible to construct a uniform parity array

Explanation: We iterate through the array to determine parity presence, but the final return is always True. This is because for any array of distinct integers, using either the original numbers or their differences, it is always possible to construct an array where all numbers have the same parity. The initial check helps understand why this property holds, but it does not change the result.

Go Solution

func uniformArray(nums1 []int) bool {
    // In Go, we don't need to track separately; any array can form uniform parity
    return true
}

Explanation: The Go implementation is simpler because the same reasoning applies: for any array of distinct integers, we can construct a uniform parity array. Edge handling is trivial due to the guaranteed properties of integer subtraction and parity.

Worked Examples

Example 1: nums1 = [2,3]

Step	nums2 Choice	nums2 State
1	nums2[0] = nums1[0] - nums1[1] = -1	[-1]
2	nums2[1] = nums1[1] = 3	[-1, 3]

Both elements are odd → return True.

Example 2: nums1 = [4,6]

Step	nums2 Choice	nums2 State
1	nums2[0] = nums1[0] = 4	[4]
2	nums2[1] = nums1[1] = 6	[4, 6]

Both elements are even → return True.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	We scan the array once to check parities
Space	O(1)	Only two flags are used, independent of input size

The algorithm only requires a single pass through the array, and no extra data structures are needed.

Test Cases

# Provided examples
assert Solution().uniformArray([2,3]) == True  # Mix of even and odd
assert Solution().uniformArray([4,6]) == True  # All even

# Single element arrays
assert Solution().uniformArray([1]) == True  # Single odd
assert Solution().uniformArray([2]) == True  # Single even

# All odd
assert Solution().uniformArray([1,3,5,7]) == True

# All even
assert Solution().uniformArray([2,4,8,10]) == True

# Mix of even and odd
assert Solution().uniformArray([1,2,3,4]) == True

Test	Why
[2,3]	Mix of parity, ensures differences can create uniform parity
[4,6]	All even, already uniform
[1]	Single element edge case
[2]	Single element edge case
[1,3,5,7]	All odd numbers
[2,4,8,10]	All even numbers
[1,2,3,4]	Mixed array with multiple elements

Edge Cases

Single-element array: An array with only one number trivially forms a uniform parity array since there is only one element. The implementation returns True directly.

All numbers of same parity: If all numbers are either even or odd, no difference operation is needed; simply copying the numbers forms a uniform parity array. Our solution handles this naturally by returning True.

Mixed parity with more than two elements: Even with multiple elements of mixed parity, it is always possible to construct a uniform parity array using differences between elements. Our solution's reasoning generalizes, ensuring correctness regardless of array size.