Construct Uniform Parity Array I | LeetCode 3875 | Weekly Contest 494 | Java | Developer Coder
Construct Uniform Parity Array I - Video Solution
Watch 9 video solutions for Construct Uniform Parity Array I, a easy level problem involving Array, Math. This walkthrough by Developer Coder has 619 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Problem Statement
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 indexj != i
Return true if it is possible to construct such an array, otherwise, return false.
Example 1:
Input: nums1 = [2,3]
Output: true
Explanation:
- Choose
nums2[0] = nums1[0] - nums1[1] = 2 - 3 = -1. - Choose
nums2[1] = nums1[1] = 3. nums2 = [-1, 3], and both elements are odd. Thus, the answer istrue.
Example 2:
Input: nums1 = [4,6]
Output: true
Explanation:
- Choose
nums2[0] = nums1[0] = 4. - Choose
nums2[1] = nums1[1] = 6. nums2 = [4, 6], and all elements are even. Thus, the answer istrue.
Constraints:
1 <= n == nums1.length <= 1001 <= nums1[i] <= 100nums1consists of distinct integers.
Approach Overview
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.
Complexity Analysis
| 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 |