Construct Uniform Parity Array I solution and explanation
Google
8 more videos on this problem
Construct Uniform Parity Array I | LeetCode 3875 | Weekly Contest 494 | Java | Developer CoderDeveloper Coder · 3:39 · 619 views
LeetCode 3875 & 3876 | Construct Uniform Parity Array I & II | JavaCode Kage · 9:43 · 174 views
LeetCode Weekly Contest 494 | Construct Uniform Parity Array I & II (3875, 3876) | Full ExplanationProof2Code · 10:51 · 56 views
Leetcode 3875 | Construct Uniform Parity Array I | Weekly Contest 494Code Like Him · 2:17 · 56 views
Leetcode Contest 494: Construct Uniform Parity Array IShailviStart · 4:09 · 45 views
Leetcode Weekly Contest 494 Q1. Construct Uniform Parity Array I #python #dsaADevOpsEngineer · 1:08 · 42 views
Leetcode 3875. Construct Uniform Parity Array I || Weekly Contest 494ExpertFunda · 27:31 · 40 views
LC 3875 | Construct Uniform Parity Array I | Contest 494CodingHelp · 8:29 · 16 views
Construct Uniform Parity Array I | Leetcode 3875 | Explanation With Code | Javacodewithsitaram · 8:57 · 15 views
The problem
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.
Solution
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).
class Solution:
def uniformArray(self, nums1: list[int]) -> bool:
return Trueclass Solution {
public boolean uniformArray(int[] nums1) {
return true;
}
}class Solution {
public:
bool uniformArray(vector<int>& nums1) {
return true;
}
};function uniformArray(nums1: number[]): boolean {
return true;
}func uniformArray(nums1 []int) bool {
return true
}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 |
Frequently asked questions
Is Construct Uniform Parity Array I easy or hard?
Construct Uniform Parity Array I is classified as an Easy problem. The challenge mainly involves recognizing the parity constraint and constructing the array accordingly. Once you apply simple modulo logic and iteration, the implementation becomes straightforward.
Construct Uniform Parity Array I Python/Java solution
The implementation is straightforward in Python, Java, C++, Go, or TypeScript. Iterate through the array length and assign values that maintain consistent parity, typically by starting with a valid number and increasing by 2 each step. This preserves the parity constraint and keeps the algorithm O(n).
How to solve Construct Uniform Parity Array I in O(n)?
Determine the parity you want all elements to share. Then iterate from index 0 to n-1 and assign values that maintain that parity, such as increasing by 2 or adjusting numbers so value % 2 remains consistent. Since each position is processed once, the algorithm runs in linear time.
What is the best approach for Construct Uniform Parity Array I?
The best approach is a direct parity construction. Choose a target parity (even or odd) and generate elements that maintain that parity while filling the array. This requires a single pass over the array and simple arithmetic checks like value % 2. The complexity is O(n) time and O(1) extra space.
Is Construct Uniform Parity Array I asked at Google/Amazon/Meta?
Parity and array construction problems frequently appear in screening rounds at large companies because they test logical reasoning and edge-case handling. While this exact problem may vary by platform, similar parity-based array construction tasks are common in coding interviews.
What data structure is used in Construct Uniform Parity Array I?
The problem primarily uses a basic array for output construction. No complex data structures such as hash maps or trees are required. The logic focuses on arithmetic parity checks and sequential iteration.
What is the time complexity of Construct Uniform Parity Array I?
The optimal solution runs in O(n) time because you iterate through the array once to assign values with the required parity. Each step performs constant-time operations such as arithmetic and parity checks. Space complexity is O(1) beyond the output array.