Skip to main content
Talentd

Construct Uniform Parity Array I - Solution & Explanation

EasyArrayMath6 min readAsked at: Google, Amdocs
Practice this problem

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 index j != 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 is true​​​​​​​.

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 is true.

 

Constraints:

  • 1 <= n == nums1.length <= 100
  • 1 <= nums1[i] <= 100
  • nums1 consists 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).

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force Parity ConstructionO(n)O(n)When validating both parity possibilities explicitly for clarity or debugging
Brain Teaser / Direct ConstructionO(n)O(1)Best general solution. Construct values with fixed parity in a single pass

Video Solution

Construct Uniform Parity Array I | LeetCode 3875 | Weekly Contest 494 | Java | Developer Coder • Developer Coder • 619 views views

Watch 8 more video solutions →

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.

Ready to solve this problem?

Practice Construct Uniform Parity Array I with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays