Construct Uniform Parity Array I
Asked at Meta
Problem
Given an array nums of length n where some values are -1 (placeholders), determine if it is possible to replace all -1s with any integers so that every pair of adjacent elements has an odd sum (different parity). Return true if possible, false otherwise.
Asked At
| Company | Difficulty | |
|---|---|---|
| Meta | Easy | View all Meta questions → |
How to Think About It
Key insight: for adjacent elements to sum to an odd number, they must have different parity (one even, one odd). So the array must alternate parity: even-odd-even-odd... or odd-even-odd-even...
Check all adjacent pairs of known values: if both are known and have the same parity (both even or both odd), their sum is even, so it is impossible -> return false.
If one of the pair is -1 (unknown), we can always fill it with the appropriate parity to satisfy the constraint. No conflict arises.
Visual walkthrough for nums=[2,0,2,-1]: pairs (2,0) both even -> sum even -> impossible. Return false. For nums=[1,-1,1]: (1,1) are not adjacent (separated by -1), so no conflict. Fill -1 with 0 (even). Result: [1,0,1] -> 1+0=1 (odd), 0+1=1 (odd). Valid.
The algorithm is simply: scan adjacent pairs. If both known and same parity, return false. Otherwise return true.
Edge cases: all -1s (always true), single element (always true), two adjacent known with same parity (false).
Optimal Approach
Step 1: For each adjacent pair (i, i+1) in nums:
- If both are known (not -1) and have the same parity (both even or both odd): return false.
Step 2: No conflicts found -> return true.
Walkthrough for nums=[1,-1,1,-1,1]:
- (1,-1): one unknown, skip.
- (-1,1): one unknown, skip.
- (1,-1): one unknown, skip.
- (-1,1): one unknown, skip.
- No conflicts. Return true.
Walkthrough for nums=[2,0,2,-1]:
- (2,0): both even. Conflict! Return false.
Time: O(n) for one scan. Space: O(1).
What Trips People Up in Real Interviews
Overthinking the fill strategy. The problem only asks if it is POSSIBLE, not to construct the array. Just check for conflicts.
Checking non-adjacent pairs. Only consecutive elements matter. nums[0] and nums[2] can have the same parity without issue.
Confusing odd sum with same parity. Odd sum means different parity. Same parity gives even sum.
Missing that -1 elements are wildcards. They can be any integer, so they always adapt to satisfy the constraint with their neighbors.
Trying to actually fill the array. The problem is a feasibility check (boolean return), not a construction task.
Solution Code
def isPossible(nums):
for i in range(len(nums) - 1):
if nums[i] != -1 and nums[i+1] != -1 and (nums[i] + nums[i+1]) % 2 == 0:
return False
return TrueFrequently Asked Questions
What is the Construct Uniform Parity Array I problem?
Given an array nums of length n where some values are -1 (placeholders), determine if it is possible to replace all -1s with any integers so that every pair of adjacent elements has an odd sum (different parity). Return true if possible, false otherwise.
How do you solve Construct Uniform Parity Array I?
The optimal approach is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
What companies ask Construct Uniform Parity Array I?
Construct Uniform Parity Array I is asked at Meta. It is a easy difficulty problem.
What are common mistakes on Construct Uniform Parity Array I?
- Overthinking the fill strategy. The problem only asks if it is POSSIBLE, not to construct the array. Just check for conflicts.
- Checking non-adjacent pairs. Only consecutive elements matter. nums[0] and nums[2] can have the same parity without issue.
- Confusing odd sum with same parity. Odd sum means different parity. Same parity gives even sum.
- Missing that -1 elements are wildcards. They can be any integer, so they always adapt to satisfy the constraint with their neighbors.
- Trying to actually fill the array. The problem is a feasibility check (boolean return), not a construction task.