You 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 != iReturn true if it is possible to construct such an array, otherwise, return false.
Example 1:
Input: nums1 = [2,3]
Output: true
Explanation:
nums2[0] = nums1[0] - nums1[1] = 2 - 3 = -1.nums2[1] = nums1[1] = 3.nums2 = [-1, 3], and both elements are odd. Thus, the answer is true.Example 2:
Input: nums1 = [4,6]
Output: true
Explanation:
nums2[0] = nums1[0] = 4.nums2[1] = nums1[1] = 6.nums2 = [4, 6], and all elements are even. Thus, the answer is true.
Constraints:
1 <= n == nums1.length <= 1001 <= nums1[i] <= 100nums1 consists of distinct integers.Problem Overview: You need to construct an array where every element has the same parity (all even or all odd) while satisfying the constraints defined in the problem. The task mainly tests whether you correctly reason about parity and construct a valid array efficiently.
Approach 1: Brute Force Construction (O(n) time, O(n) space)
Start by attempting both possible parity configurations: build an array of size n using only even numbers, and then try the same using only odd numbers. Iterate through the required positions and generate candidate values that match the chosen parity. If the constructed array satisfies all constraints, return it. This approach works because there are only two parity states to test, but it performs redundant checks and construction.
Approach 2: Brain Teaser / Direct Parity Construction (O(n) time, O(1) extra space)
The key observation is that parity is determined by value % 2. Instead of trying both possibilities, decide the target parity up front and construct the array directly. Iterate from 0 to n-1, generating numbers that maintain the same parity by adding 2 each step or by ensuring every value satisfies either x % 2 == 0 or x % 2 == 1. This guarantees a uniform parity array while keeping the construction simple and predictable.
This solution relies on basic reasoning about math and arrays. No advanced data structures are required—just iteration and parity checks. The algorithm walks through the array once and assigns values that preserve the chosen parity.
Recommended for interviews: The direct brain teaser construction is what interviewers expect. Brute force shows you understand the parity constraint, but the optimized approach demonstrates that you recognize there are only two parity states and can construct the answer in a single pass using simple greedy reasoning.
If all elements in nums1 are either all odd or all even, we can directly set nums2 equal to nums1, which satisfies the condition.
If nums1 contains both odd and even numbers, we can set each element of nums2 to the current element of nums1 minus some element in nums1 with different parity. Since odd minus even and even minus odd both yield an odd number, all elements of nums2 will be odd, satisfying the condition.
Therefore, regardless of whether the elements in nums1 are all odd, all even, or a mix of both, we can always construct a valid nums2. Thus the answer is always true.
The time complexity is O(1), and the space complexity is O(1).
Python
Java
C++
Go
TypeScript
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Parity Construction | O(n) | O(n) | When validating both parity possibilities explicitly for clarity or debugging |
| Brain Teaser / Direct Construction | O(n) | O(1) | Best general solution. Construct values with fixed parity in a single pass |
Construct Uniform Parity Array I | LeetCode 3875 | Weekly Contest 494 | Java | Developer Coder • Developer Coder • 572 views views
Watch 7 more video solutions →Practice Construct Uniform Parity Array I with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor