Greedy Approach I

On a first glance, a greedy approach for this problem might seem intractable, but it isn't. The fact that the numbers are all unique really help here. Bucket them up into two sorted sets, one for even and one for odd numbers. Then greedily try even first, then odd. When trying even, you can quickly calculate for each number whether there is a possibility to use the second rule. The same for the odd case. When doing that, despite being a greedy approach (trying all possibilities), it runs very quickly in nlogn (a linear approach should be feasible too). Code is down below, cheers, ACC.

Construct Uniform Parity Array II - LeetCode

ou are given an array nums1 of n distinct integers.

You want to construct another array nums2 of length n such that the elements in nums2 are either all odd or all even.

For each index i, you must choose exactly one of the following (in any order):

• nums2[i] = nums1[i]​​​​​​​
• nums2[i] = nums1[i] - nums1[j], for an index j != i, such that nums1[i] - nums1[j] >= 1

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

 

Example 1:

Input: nums1 = [1,4,7]

Output: true

Explanation:​​​​​​​​​​​​​​

• Set nums2[0] = nums1[0] = 1.
• Set nums2[1] = nums1[1] - nums1[0] = 4 - 1 = 3.
• Set nums2[2] = nums1[2] = 7.
• nums2 = [1, 3, 7], and all elements are odd. Thus, the answer is true.

Example 2:

Input: nums1 = [2,3]

Output: false

Explanation:

It is not possible to construct nums2 such that all elements have the same parity. Thus, the answer is false.

Example 3:

Input: nums1 = [4,6]

Output: true

Explanation:

• Set nums2[0] = nums1[0] = 4.
• Set nums2[1] = nums1[1] = 6.
• nums2 = [4, 6], and all elements are even. Thus, the answer is true.

 

Constraints:

• 1 <= n == nums1.length <= 105
• 1 <= nums1[i] <= 109
• nums1 consists of distinct integers.

public class Solution {
    public bool UniformArray(int[] nums1)
    {
        SortedSet<int> evenNums = new SortedSet<int>();
        SortedSet<int> oddNums = new SortedSet<int>();

        foreach (int n in nums1)
        {
            if(n%2==0) evenNums.Add(n);
            else oddNums.Add(n);
        }

        //Try even
        bool found = true;
        for(int i=0;i<nums1.Length;i++)
        {
            if (nums1[i] % 2 == 1 && !CheckPossibleVal(true, nums1[i], evenNums, oddNums))
            {
                found = false;
                break;
            }
        }
        if (found) return true;

        //Try odd
        found = true;
        for (int i = 0; i < nums1.Length; i++)
        {
            if (nums1[i] % 2 == 0 && !CheckPossibleVal(false, nums1[i], evenNums, oddNums))
            {
                found = false;
                break;
            }
        }
        if (found) return true;

        return false;
    }

    private bool CheckPossibleVal(bool even, int number, SortedSet<int> evenNums, SortedSet<int> oddNums)
    {
        if (even)
        {
            foreach (int n in evenNums)
            {
                if (n == number) continue;
                if (number - n < 1) return false;
                if ((number - n) % 2 == 0) return true;
            }
        }
        else
        {
            foreach (int n in oddNums)
            {
                if (n == number) continue;
                if (number - n < 1) return false;
                if ((number - n) % 2 == 1) return true;
            }
        }
        return false;
    }
}