You are given an array nums1 of n distinct integers.

Your goal is to construct another array nums2, also of length n, where every element in nums2 is either all odd or all even. In other words, the entire nums2 array must consist of only odd numbers, or only even numbers.

To build nums2, you process each index i independently. For each index i, you must choose exactly one of the following two options (you may decide the order freely):

• Keep the value as is: nums2[i] = nums1[i]
• Subtract another element: nums2[i] = nums1[i] - nums1[j], where j != i, and the result must satisfy nums1[i] - nums1[j] >= 1

For each position, you make one of these choices, and the final nums2 array must end up being entirely odd or entirely even.

Return true if it is possible to construct such an array nums2, and false otherwise.

The key observation is to think about parity. We want every element in nums2 to have the same parity (all odd or all even). Let's reason about when this is achievable.

First, consider the simplest case. If all elements in nums1 already share the same parity (either all odd or all even), then we can simply keep every element unchanged by choosing nums2[i] = nums1[i]. This trivially satisfies the requirement.

The interesting case is when nums1 contains a mix of odd and even numbers. Since we can subtract one element from another, notice what happens to parity:

• odd - odd = even
• even - even = even
• odd - even = odd
• even - odd = odd

This means subtraction gives us flexibility to flip or preserve parity, depending on what we subtract. Because the numbers are distinct, the difference is never zero, so the constraint nums1[i] - nums1[j] >= 1 just requires that we subtract a strictly smaller element.

Now, ask: can we make everything even? An element is even either if it is already even, or if we subtract another value of the same parity from it (odd - odd or even - even). For any element x, we can make it even as long as there exists a strictly smaller element with the same parity to subtract. The only element that can ever fail is the globally smallest element of each parity, since there may be nothing smaller of the same parity to subtract from it.

The actual blocker comes down to the smallest values. Let mn be the minimum odd number in the array. If there is some even number x that is smaller than mn, that even number cannot be turned into the needed parity, because there is no valid smaller element to subtract and produce the consistent result. In every other situation, we can carefully pick subtractions to align all elements to a common parity.

So the solution reduces to a simple check: find the minimum odd number, and verify that no even number is smaller than it. If such a smaller even number exists, return false; otherwise, return true.

Pattern Learn more about Math patterns.

We solve this with a straightforward two-pass scan over the array, applying the parity reasoning described above.

Step 1: Find the minimum odd number.

We initialize a variable mn to infinity (inf). Then we iterate through every element x in nums1. Whenever x is odd (checked with x % 2), we update mn to be the smaller of the current mn and x:

mn = inf
for x in nums1:
    if x % 2:
        mn = min(mn, x)

After this loop, mn holds the smallest odd value in the array. If the array contains no odd numbers at all, mn stays at inf.

Step 2: Check the even numbers against mn.

We iterate through the array a second time. For each even element x (checked with x % 2 == 0), we test whether mn is a real odd value (mn != inf) and whether x is smaller than mn:

for x in nums1:
    if x % 2 == 0 and mn != inf and x < mn:
        return False
return True

• The condition mn != inf ensures that the array actually contains at least one odd number. If everything is even, no conflict can arise, so we never fail here.
• The condition x < mn detects the blocking case: an even number that is strictly smaller than the minimum odd number. If we find one, the construction is impossible, so we return False.

If we get through the entire second pass without finding any such even number, the construction is always possible, and we return True.

Complexity Analysis:

• Time complexity: O(n), since we make two linear passes over the array of n elements.
• Space complexity: O(1), since we only use a single extra variable mn regardless of input size.

This approach relies on the brain-teaser insight that the only obstruction is an even number smaller than the smallest odd number, reducing what looks like a complex construction problem into a simple comparison.