3876. Construct Uniform Parity Array II
Difficulty: Medium | Published on 2026-09-04
This is Part II of the problem you just solved — same setup, but with one extra rule bolted onto the subtract option, and that one rule completely changes the answer from "always true" to something you actually have to check. Let's build it up.
1. Problem in Very Simple Language
Same setup as Part I: you have INLINECODE0, all distinct integers, and you want to build INLINECODE1 (same length) where every element is odd, or every element is even — no mixing.
For each position INLINECODE2, you choose one of:
INLINECODE3 (copy), or INLINECODE4 for some other index INLINECODE5, but only if INLINECODE6.
That last condition is brand new compared to Part I, and it's the whole story here: since every value is a positive integer, INLINECODE7 simply means INLINECODE8 must be strictly smaller than INLINECODE9. In Part I, you could subtract any other element, even a bigger one (giving a negative result, which was fine). Now, you can only subtract a smaller number from a bigger one.
What's given: INLINECODE10. What to find: is there a way to fill INLINECODE11, respecting this new "can only subtract something smaller" rule, so everything ends up the same parity? What to return: INLINECODE12 or INLINECODE13.
2. Real-Life Analogy
Back to our lockers: each locker can either keep its own tag, or swap it for "my number minus a smaller number from some other locker." You're no longer allowed to subtract a bigger locker's number from yours (that trick, which let you sometimes go negative in Part I, is now off the table). This sounds like a small change, but it has a big consequence: the locker holding the smallest number in the entire row has nobody smaller to borrow from — it is physically forced to just keep its own tag.
3. Important Programming Concepts I Need First
Everything from Part I still applies (parity, the "subtracting odd flips parity, subtracting even doesn't" rule) — quick recap:
Parity-flip rule (from Part I, still true here)
INLINECODE14, INLINECODE15, INLINECODE16, INLINECODE17. In short: subtracting an odd number always flips parity; subtracting an even number never does, regardless of which number is bigger.New concept: "Forced move"
Concept: Sometimes a rule leaves you with zero legal choices except one — that one choice is "forced." Recognizing forced moves early often unlocks the whole problem, because they pin down facts you can build the rest of your reasoning on. Why we need it: The new INLINECODE18 restriction means the smallest element in INLINECODE19 has no valid INLINECODE20 to subtract at all (there's nothing smaller than the minimum!) — so it's forced to just copy itself. That one forced move turns out to decide almost everything.Minimum of an array
Concept: The single smallest value among all elements. Example: INLINECODE21. Why we need it: As just discussed, the minimum element is the one with no subtraction option available — it's the anchor of our whole argument.Sorted order (as a thinking tool, not necessarily code we write)
Concept: Imagining the array's values lined up from smallest to largest helps reason about "does a smaller helper number exist?" questions. Why we need it: We'll repeatedly ask "is there a smaller odd number available?" — thinking in sorted order makes this easy to reason about, even though our final code won't need to actually sort anything.4. Understand the Input
Take Example 2 (the interesting one — it's INLINECODE22 this time!): CODEBLOCK0
INLINECODE23 is even, INLINECODE24 is odd. The minimum value in the array is INLINECODE25. Since INLINECODE26 is the minimum, there's no index INLINECODE27 with INLINECODE28 — so index 0 (value INLINECODE29) has no valid subtraction option at all. It's forced to copy: INLINECODE30. This immediately locks in the target parity: since INLINECODE31 must be INLINECODE32 (even), the entire INLINECODE33 array must be even. Now can INLINECODE34 (at index 1) become even? It would need INLINECODE35 for some INLINECODE36 with INLINECODE37 — the only candidate is INLINECODE38, value INLINECODE39. Is INLINECODE40 even? No, it's odd! Subtracting INLINECODE41 (even) from INLINECODE42 (odd) gives odd (per our parity rule: subtracting an even number never flips parity) — so this doesn't help. There's no other smaller number to try. INLINECODE43 is stuck at odd, but the target is forced to be even. Impossible.
5. Understand the Output
Output: INLINECODE44
As shown above: the minimum element (INLINECODE45) is forced to stay even (no subtraction possible), which locks the whole array's target to "all even." But INLINECODE46 can never be turned into an even number using only smaller numbers to subtract (its only smaller option, INLINECODE47, is even, and subtracting an even number can't flip INLINECODE48's parity). So no valid INLINECODE49 exists.
Compare this to Example 1: INLINECODE50. Minimum is INLINECODE51 (odd) — this forces target = odd. Then INLINECODE52 (even) needs to flip to odd using a smaller number; INLINECODE53 is available and it's odd, so INLINECODE54 works. INLINECODE55 is already odd, just copy. Everything works out → INLINECODE56.
6. Solve the Example Manually
Let's manually work through a slightly bigger example to really nail the pattern: INLINECODE57.
Step 1: Find the minimum. INLINECODE58.
Step 2: Since 3 is the minimum, it has no valid INLINECODE59 to subtract from — it's forced to copy itself. INLINECODE60 for that position = INLINECODE61, which is odd. This locks the target: the whole array must end up odd.
Step 3: Check every other element against target = odd.
| Value | Already odd? | If not, need to flip using SOME smaller ODD number | Available smaller odd number? | Result |
|---|---|---|---|---|
| 3 (the min) | Yes (odd) | — (forced copy anyway) | — | OK (copy) |
| 4 | No (even) | Need smaller odd number INLINECODE62 | Yes! INLINECODE63 is odd and INLINECODE64 | INLINECODE65 (odd) ✔️ |
| 9 | Yes (odd) | — | — | OK (copy, or could subtract too) |
Now let's contrast with INLINECODE67:
Step 1: Minimum is INLINECODE68. It's even → forced target = even.
Step 2: Check every other element against target = even.
| Value | Already even? | If not, need smaller ODD number to flip | Smaller odd number available? | Result |
|---|---|---|---|---|
| 2 (min) | Yes | — | — | OK (forced copy) |
| 4 | Yes | — | — | OK (copy) |
| 9 | No (odd) | Need smaller ODD number INLINECODE69 | Candidates smaller than 9: INLINECODE70 (even), INLINECODE71 (even) — no odd ones available! | ❌ Stuck |
This reveals the real danger zone: when the minimum is even, the smallest odd number in the whole array (if one exists) can never find a smaller odd helper — because by definition, nothing smaller than it is odd.
7. Think Like a Programmer
What do I know? The minimum element is always forced to "copy," which locks in the target parity as INLINECODE74. What do I need to find? Whether every other element can actually reach that forced target. What can I try? Split into two cases based on whether the minimum is odd or even, and figure out exactly when each case can (or can't) succeed. Case: minimum is odd. The target is odd. Any element that's already odd just copies. Any element that's even needs to flip — and it needs some smaller odd number to subtract. Here's the beautiful part: the minimum itself is odd, and by definition it's smaller than every other element in the array! So every even element can always use the minimum as its "flip helper." This case can never fail. Case: minimum is even. The target is even. Any already-even element copies fine. Any odd element needs to flip using a smaller odd number. But now the minimum (even) can't help with that — we need some other, odd, smaller number. The most fragile case is: the smallest odd number in the whole array. By definition, nothing smaller than it is odd (if something smaller and odd existed, it would BE the smallest odd number instead). So if any odd number exists at all, the smallest one among them is permanently stuck. This case only succeeds if there are zero odd numbers in the entire array. What information should I remember? Just two things, found in a single pass: the array's minimum value (specifically, its parity), and whether any odd number exists at all. What pattern do I notice? This collapses to a two-line check — no need to actually simulate constructing INLINECODE75.
8. Start With the Brute Force Solution
Brute force idea: For each of the 2 possible targets (all-even, all-odd), check every element: if it matches, fine. If not, search through all other elements smaller than it to see if any has the opposite (odd) parity needed to flip it.
Why it works: Directly checks feasibility for both targets, respecting the "must subtract something smaller" rule.
Time complexity: For each of 2 targets, and for each element needing a flip, scanning all smaller elements could take O(n) — giving O(n²) overall in the worst case. With INLINECODE76 up to INLINECODE77, that's up to INLINECODE78 operations — way too slow.
CODEBLOCK1
9. Explain the Brute Force Code Line by Line
INLINECODE79 — try both possible targets (even=0, odd=1); if either is achievable, return true. Inside INLINECODE80: for each element, INLINECODE81 — if it already matches the target, no work needed, "copy" handles it. Otherwise, we need to flip it. We scan every other index INLINECODE82, looking for one that is (a) smaller in value (INLINECODE83, satisfying the new INLINECODE84 rule) and (b) odd (since only subtracting odd numbers flips parity). If we find such a INLINECODE85, this element can be fixed; if we scan everything and find nothing, this target is impossible, so we return INLINECODE86 immediately.
10. Why Is the Brute Force Solution Not Ideal?
With INLINECODE87 up to INLINECODE88, checking "does a smaller odd number exist" by re-scanning the whole array for every single element that needs a flip could mean up to INLINECODE89 billion comparisons in the worst case. That's far too slow to run in time. We need to answer "is there a smaller odd number available?" instantly, not by rescanning.
11. Find the Better Approach
CODEBLOCK2
⭐ Key Insight
Before the insight
It looks like we need to check every element against every possible smaller helper, for both possible targets — an expensive search.The problem
That's way too much repeated work, and it obscures a much simpler truth hiding in the problem's structure.The insight
The new INLINECODE90 restriction removes all freedom from exactly one element: the minimum. It can never subtract anything (nothing is smaller), so it must copy itself — which single-handedly decides the target parity for the entire array; there's no longer a choice between "try both targets," there's only ever one target to check: INLINECODE91.Once the target is pinned down, everything else follows from one more fact: the minimum element, if odd, is a universal helper (it's smaller than everything else, so every even element can always borrow it to flip to odd). But if the minimum is even, it can't help anyone flip — and the next smallest odd number (if one exists) has the exact same problem the minimum had: nothing smaller than it is odd, so it's permanently stuck if the target is even.
After the insight
The whole problem reduces to two quick checks computed in a single pass: what's the parity of the minimum, and does any odd number exist in the array at all?13. Dry Run the Optimized Solution
Let's dry-run Example 2: INLINECODE92.
Step 1: Scan once, tracking minimum value and whether any odd number exists.
| Index | Value | Running min | Is this value odd? | hasOdd so far |
|---|---|---|---|---|
| 0 | 2 | 2 | No | false |
| 1 | 3 | 2 (unchanged, 3 > 2) | Yes | true |
Step 2: Check INLINECODE95's parity. INLINECODE96 → minimum is even.
Step 3: Since minimum is even, the answer is INLINECODE97. INLINECODE98, so INLINECODE99.
Final answer: INLINECODE100 ✔️ matches!
14. Optimized Code
CODEBLOCK3
CODEBLOCK4
15. Explain Optimized Code Line by Line
INLINECODE101 — start with an impossibly large placeholder, so the very first real value we see will correctly become the new minimum. INLINECODE102 — tracks whether we've seen any odd number anywhere in the array. The INLINECODE103 loop — a single pass through the array. INLINECODE104 — standard running-minimum tracking. INLINECODE105 — flags that at least one odd number exists, the moment we see one. INLINECODE106 — checks whether the minimum element is odd. If yes: this case always succeeds, because the minimum is both the smallest value in the array and odd, making it a universal "flip helper" for every even element. We INLINECODE107 immediately. INLINECODE108 — if the minimum is even, the target is forced to even, and this only works if there's no odd number anywhere. So we return INLINECODE109 only when INLINECODE110 is INLINECODE111.
16. Test With Multiple Examples
Example 1 — Normal Case
INLINECODE112 → min = 1 (odd) → Output: INLINECODE113 ✔️Example 2 — Different Case
INLINECODE114 → min = 2 (even), hasOdd = true → Output: INLINECODE115 ✔️Example 3 — Edge Case
INLINECODE116 → min = 4 (even), hasOdd = false (both even) → Output: INLINECODE117 ✔️17. Edge Cases
Single-element array (INLINECODE118) → the lone element is forced to copy itself (no INLINECODE119 exists at all), which trivially matches its own parity → INLINECODE120 = that element; if odd, INLINECODE121 directly; if even, INLINECODE122 will be INLINECODE123 (since the only number is even) → INLINECODE124 either way. Always INLINECODE125 for INLINECODE126. All elements even → INLINECODE127 is even, INLINECODE128 → INLINECODE129 (nothing ever needs to flip). All elements odd → INLINECODE130 is odd → INLINECODE131 immediately (every element already matches, or can trivially copy). Minimum is odd, but there are many even numbers to flip → still always INLINECODE132, since the minimum alone is sufficient to flip every even number, no matter how many there are. Minimum is even, exactly one odd number exists → INLINECODE133 → INLINECODE134 (that lone odd number, being both the only and therefore the smallest odd number, can never find a smaller odd helper). Large arrays (INLINECODE135 up to INLINECODE136) with mixed parities → handled efficiently in one O(n) pass, no risk of timeout.
18. Time Complexity
CODEBLOCK5
Why: We only need to look at each element exactly once to know both its value (for tracking the minimum) and its parity (for tracking INLINECODE137). No nested loops, no rescanning — everything the final answer depends on can be computed while walking through the array a single time.
19. Space Complexity
We only use a couple of simple variables (INLINECODE138, INLINECODE139) — no arrays, lists, or structures that grow with input size.
Extra space: INLINECODE140 — constant.
20. Common Mistakes Beginners Make
❌ "This is just like Part I, so the answer should always be INLINECODE141." ✅ Part I allowed subtracting any other element (even a bigger one, going negative). Part II's INLINECODE142 restriction removes that freedom specifically from the minimum element, which breaks the "always true" guarantee from Part I entirely.
❌ "I should check both possible targets (all-even, all-odd), like in Part I." ✅ There's no longer a free choice of target — the minimum element is forced to copy itself (no valid INLINECODE143 exists for it), which locks the target to INLINECODE144 automatically. Only one target is ever worth checking.
❌ "If the minimum is even, I just need to check if there's a smaller odd number for each odd element individually." ✅ You don't need to check element-by-element — the key realization is that it's specifically the smallest odd number (if any exists) that's the bottleneck; if it fails, nothing built around checking "is target even achievable" needs anything more granular than "does any odd number exist at all?"
❌ "Subtracting works the same regardless of which number is bigger." ✅ In this version, INLINECODE145 requires INLINECODE146 — you can only subtract something smaller. This one-directional restriction is the entire crux of the problem.
21. How to Recognize This Pattern in Other Problems
Watch for these signal phrases:
CODEBLOCK6
22. Interview Thinking
CODEBLOCK7
23. Mini Challenge
Try these before checking the answers:
1. Why is the minimum element in INLINECODE147 the only one guaranteed to have zero valid subtraction options? 2. If the minimum element is odd, why can it always help every even element flip to odd, no matter how large the array is? 3. If the minimum is even and there are 3 odd numbers in the array — say INLINECODE148 — which one specifically causes the problem, and why don't the other two matter?
Answer to Mini Challenge
1. The rule requires INLINECODE149 for a valid subtraction at index INLINECODE150. The minimum element, by definition, has no other element smaller than it anywhere in the array — so no valid INLINECODE151 can ever exist for it, forcing it to copy itself. 2. Because the minimum is, by definition, smaller than every other element in the array — so for any even element INLINECODE152, INLINECODE153 is always a legal move (satisfies the INLINECODE154 rule since INLINECODE155), and since the minimum is odd, subtracting it always flips INLINECODE156's parity to odd. 3. The smallest of the three, INLINECODE157, is the one that causes the problem — it has no smaller odd number to use as its own flip-helper (since it's the smallest odd number overall), so it can never become even. INLINECODE158 and INLINECODE159 are both larger and could technically use INLINECODE160 as their odd helper if needed, so they're not the bottleneck — but since INLINECODE161 itself already fails, the whole target is impossible regardless.
24. Final Revision
🧠 Problem in One Sentence
Determine whether INLINECODE162 can be made uniformly odd or even, where the "subtract" option now only allows subtracting a smaller element.🔑 Main Idea
The minimum element can never subtract anything (nothing is smaller), forcing it to copy itself and locking the target parity to INLINECODE163. If the minimum is odd, it can always flip every other element (always succeeds). If the minimum is even, it only works when there are zero odd numbers anywhere (otherwise the smallest odd number gets permanently stuck).⚙️ Algorithm
1. Scan the array once, tracking the minimum value and whether any odd number exists. 2. If the minimum is odd, return INLINECODE164. 3. Otherwise, return INLINECODE165 only if no odd numbers exist at all; otherwise INLINECODE166.⏱️ Complexity
Time: INLINECODE167 Space: INLINECODE168🎯 Pattern to Remember
A restriction like "can only combine with something smaller/bigger" often locks a specific extreme element (min or max) into a forced move — chase that forced move to see if it determines the whole answer.25. Beginner Quiz
1. (Understanding) Why does adding the INLINECODE169 restriction change the answer from "always true" (Part I) to "sometimes false" (Part II)? 2. (Basic concept) For INLINECODE170, what is the forced target parity, and why? 3. (Logic) Why does it matter specifically whether the smallest odd number (not just any odd number) has a smaller odd helper available? 4. (Dry run) For INLINECODE171, find the minimum, determine the forced target, and decide whether the answer is INLINECODE172 or INLINECODE173. 5. (Complexity/pattern) Why does the brute-force approach risk INLINECODE174 here, and what specific single fact (about the minimum element) collapses the whole problem down to an INLINECODE175 check?