3875. Construct Uniform Parity Array I

LeetCode ↗

Problem Pattern Idea Example Code Complex Pitfalls

Problem Description

You are given an array nums1 of n distinct integers.

Your goal is to build another array nums2 of length n, with one key requirement: every element in nums2 must share the same parity — that is, the elements are either all odd or all even.

To construct nums2, you process each index i and must pick exactly one of the two options below (the order in which you handle the indices does not matter):

Keep the value as is: set nums2[i] = nums1[i].
Subtract another element: set nums2[i] = nums1[i] - nums1[j], where j is any index different from i (j != i).

After filling in every position of nums2, check whether all its elements have the same parity.

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

Quick Interview Experience

Help others by sharing your interview experience

Have you seen this problem before?

How We Pick the Algorithm

Why Math / Bit Manipulation?

This problem maps to Math / Bit Manipulation through a short path in the full flowchart.

The problem reduces to a parity insight where the answer is always true, requiring only mathematical reasoning about odd/even properties of subtraction.

Open in Flowchart

Intuition

The trick to this problem is realizing that we can always succeed, no matter what nums1 looks like. Let's reason through the possible cases.

First, think about what happens if nums1 is already uniform — meaning every element is odd, or every element is even. In that situation, we don't need to do anything clever: we simply choose nums2[i] = nums1[i] for every index. The result is identical to nums1, which already has the same parity throughout. So this case clearly works.

Now consider the harder-looking case, where nums1 contains a mix of odd and even numbers. The key insight comes from how parity behaves under subtraction:

odd - even = odd
even - odd = odd

In other words, subtracting two numbers of different parity always produces an odd result. So if nums1 has at least one odd number and at least one even number, then for every element nums1[i], we can always find some nums1[j] of the opposite parity and compute nums2[i] = nums1[i] - nums1[j]. Every such result is odd, making the entire nums2 array all odd — exactly what we want.

Putting both cases together:

If nums1 is all odd or all even → keep the values as they are.
If nums1 is mixed → subtract opposite-parity pairs to make everything odd.

Since every possible configuration of nums1 falls into one of these two cases, a valid nums2 can always be constructed. That's why the answer is unconditionally true.

Pattern Learn more about Math patterns.

Solution Approach

Solution 1: Brain Teaser

Based on the intuition above, the implementation becomes remarkably simple — there is essentially nothing to compute.

The reasoning breaks down into two cases:

nums1 is already uniform. If all elements are odd, or all elements are even, we just pick nums2[i] = nums1[i] for every index. The resulting nums2 keeps the same parity throughout, so the condition holds.
nums1 is mixed. If nums1 contains both odd and even numbers, then for each index i we choose the second option, nums2[i] = nums1[i] - nums1[j], picking a j whose parity differs from i. Because odd - even and even - odd both yield an odd number, every element of nums2 becomes odd, and the array is uniform.

Since both cases always allow us to build a valid nums2, the answer is always true. There is no input for which construction fails, so we can return true directly without inspecting the array at all.

class Solution:
    def uniformArray(self, nums1: list[int]) -> bool:
        return True

In terms of complexity, the time is O(1) and the space is O(1), since we perform no iteration over the input and simply return a constant result.

Example Walkthrough

Let's trace through the solution approach using two small examples that cover both cases in the reasoning.

Example 1: Already uniform array

Consider nums1 = [3, 7, 1].

Every element here is odd. Since the array is already uniform, we don't need to do anything clever — we simply apply the first option at every index:

Index 0: nums2[0] = nums1[0] = 3 (odd)
Index 1: nums2[1] = nums1[1] = 7 (odd)
Index 2: nums2[2] = nums1[2] = 1 (odd)

This gives nums2 = [3, 7, 1], where every element is odd. The parity is uniform, so construction succeeds. The same logic applies if all elements were even.

Example 2: Mixed array

Now consider nums1 = [2, 5, 8].

Here we have a mix: 2 and 8 are even, while 5 is odd. We use the second option for each index, subtracting an element of the opposite parity:

Index 0: nums1[0] = 2 is even. Pick odd nums1[1] = 5. → nums2[0] = 2 - 5 = -3 (odd)
Index 1: nums1[1] = 5 is odd. Pick even nums1[0] = 2. → nums2[1] = 5 - 2 = 3 (odd)
Index 2: nums1[2] = 8 is even. Pick odd nums1[1] = 5. → nums2[2] = 8 - 5 = 3 (odd)

This gives nums2 = [-3, 3, 3], where every element is odd. The parity is uniform once again.

Conclusion

In Example 1 the array was already uniform, and in Example 2 the mix of parities guaranteed at least one odd and one even number, letting every subtraction produce an odd result. Both configurations lead to a valid nums2. Since every possible input falls into one of these two cases, the function can confidently return True without ever inspecting the array.

Solution Implementation

1from typing import List
2
3
4class Solution:
5    def uniformArray(self, nums1: List[int]) -> bool:
6        # This method currently returns True unconditionally,
7        # indicating the array is considered "uniform" by default.
8        return True
9

1class Solution {
2    /**
3     * Determines whether the given array is uniform.
4     * A uniform array is one where all elements share a common property
5     * (for example, all elements being equal).
6     *
7     * @param nums the input array to be evaluated
8     * @return true if the array satisfies the uniform condition, false otherwise
9     */
10    public boolean uniformArray(int[] nums) {
11        // Current implementation always returns true as a placeholder.
12        // Replace this with the actual uniformity-checking logic when needed.
13        return true;
14    }
15}
16

1class Solution {
2public:
3    // Determines whether the given array is uniform.
4    // Returns true if the condition is satisfied.
5    bool uniformArray(vector<int>& nums1) {
6        // Currently always returns true as a placeholder.
7        return true;
8    }
9};
10

1/**
2 * Determines whether the given array is "uniform".
3 *
4 * @param nums - The input array of numbers to be checked.
5 * @returns A boolean value indicating the result of the uniformity check.
6 */
7function uniformArray(nums: number[]): boolean {
8    // Currently returns true unconditionally as a placeholder implementation.
9    return true;
10}
11

Time and Space Complexity

Time Complexity: O(1). The method uniformArray directly returns True without performing any iteration, computation, or processing of the input list nums1. Since the operation executes in constant time regardless of the size of the input, the time complexity is O(1).
Space Complexity: O(1). The method does not allocate any additional data structures or use auxiliary space that scales with the input size. Only a constant amount of space is used for the return value, so the space complexity is O(1).

Pattern Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall 1: Overthinking the Problem and Writing Unnecessary Logic

The most common pitfall is treating this as a complex construction problem and attempting to actually simulate building nums2. Many solvers write elaborate code that counts odd/even elements, tries different pairings, or even brute-forces all 2^n choices of "keep vs. subtract" for each index.

For example, an over-engineered attempt might look like this:

from typing import List


class Solution:
    def uniformArray(self, nums1: List[int]) -> bool:
        odds = sum(1 for x in nums1 if x % 2 == 1)
        evens = len(nums1) - odds

        # Wrongly assumes we need a "balanced" mix or special counts
        if odds == 0 or evens == 0:
            return True
        # Incorrectly returns False when both parities are present
        return False

Why this is wrong: The logic above returns False when nums1 contains both odd and even numbers. But that case is actually the easiest to satisfy — for every index i we pick nums2[i] = nums1[i] - nums1[j] where j has opposite parity. Since odd - even and even - odd are both odd, the whole array becomes uniformly odd. The mixed case never fails.

Solution: Recognize the key insight before coding. The two cases (all-uniform input, or mixed input) both always produce a valid nums2. Once you see that no input can ever fail, the answer collapses to a constant:

from typing import List


class Solution:
    def uniformArray(self, nums1: List[int]) -> bool:
        return True

Pitfall 2: Missing the `n == 1` Edge Case in Reasoning

When n == 1, the second option (nums2[i] = nums1[i] - nums1[j] with j != i) is impossible because there is no other index to choose. A solver who relies on the "subtract to force odd" trick might worry this edge case breaks the answer.

Why it still works: With a single element, the only valid choice is nums2[0] = nums1[0]. A one-element array is trivially uniform — there is nothing to disagree in parity with. So the answer remains true, and no special handling is needed.

Solution: Confirm that the "keep as is" option alone already covers any input where the subtract trick is unavailable or unnecessary (single element, or already-uniform arrays). The constant return True correctly absorbs this edge case.

Pitfall 3: Misreading the Parity Rule for Subtraction

A subtle reasoning error is assuming subtraction can be used to force even uniformity in the mixed case. Some may try to pair odd - odd or even - even to get even results, then get confused when the parities don't line up across all indices.

Why this misleads: In a mixed array, the clean guarantee comes from pairing opposite parities to always yield odd. Trying to engineer all-even results requires every index to find a same-parity partner, which is fragile and unnecessary.

Solution: Anchor on the simplest invariant — odd ± even = odd — which uniformly works for every index in a mixed array. This keeps the proof clean and reinforces why the answer is unconditionally true.

Ready to land your dream job?

Unlock your dream job with a 5-minute quiz for a personalized study roadmap!

Get My Roadmap

Discover Your Strengths and Weaknesses: Take Our 5-Minute Quiz to Get a Personalized Study Roadmap:

What's the output of running the following function using input [30, 20, 10, 100, 33, 12]?

1def fun(arr: List[int]) -> List[int]:
2    import heapq
3    heapq.heapify(arr)
4    res = []
5    for i in range(3):
6        res.append(heapq.heappop(arr))
7    return res
8

1public static int[] fun(int[] arr) {
2    int[] res = new int[3];
3    PriorityQueue<Integer> heap = new PriorityQueue<>();
4    for (int i = 0; i < arr.length; i++) {
5        heap.add(arr[i]);
6    }
7    for (int i = 0; i < 3; i++) {
8        res[i] = heap.poll();
9    }
10    return res;
11}
12

1class HeapItem {
2    constructor(item, priority = item) {
3        this.item = item;
4        this.priority = priority;
5    }
6}
7
8class MinHeap {
9    constructor() {
10        this.heap = [];
11    }
12
13    push(node) {
14        // insert the new node at the end of the heap array
15        this.heap.push(node);
16        // find the correct position for the new node
17        this.bubble_up();
18    }
19
20    bubble_up() {
21        let index = this.heap.length - 1;
22
23        while (index > 0) {
24            const element = this.heap[index];
25            const parentIndex = Math.floor((index - 1) / 2);
26            const parent = this.heap[parentIndex];
27
28            if (parent.priority <= element.priority) break;
29            // if the parent is bigger than the child then swap the parent and child
30            this.heap[index] = parent;
31            this.heap[parentIndex] = element;
32            index = parentIndex;
33        }
34    }
35
36    pop() {
37        const min = this.heap[0];
38        this.heap[0] = this.heap[this.size() - 1];
39        this.heap.pop();
40        this.bubble_down();
41        return min;
42    }
43
44    bubble_down() {
45        let index = 0;
46        let min = index;
47        const n = this.heap.length;
48
49        while (index < n) {
50            const left = 2 * index + 1;
51            const right = left + 1;
52
53            if (left < n && this.heap[left].priority < this.heap[min].priority) {
54                min = left;
55            }
56            if (right < n && this.heap[right].priority < this.heap[min].priority) {
57                min = right;
58            }
59            if (min === index) break;
60            [this.heap[min], this.heap[index]] = [this.heap[index], this.heap[min]];
61            index = min;
62        }
63    }
64
65    peek() {
66        return this.heap[0];
67    }
68
69    size() {
70        return this.heap.length;
71    }
72}
73
74function fun(arr) {
75    const heap = new MinHeap();
76    for (const x of arr) {
77        heap.push(new HeapItem(x));
78    }
79    const res = [];
80    for (let i = 0; i < 3; i++) {
81        res.push(heap.pop().item);
82    }
83    return res;
84}
85

[30, 20, 10]

[100, 33, 30]

[10, 12, 20]

I don't know