NeetCode #679LC-2369Medium1-D Dynamic Programming
← Back to All Problems#679 · #2369 · Check if There is a Valid Partition For The Array(检查数组是否存在有效划分)
📌 Problem Statement & Constraints
Given a 0-indexed integer array
nums, a partition into contiguous subarrays is valid when every subarray is one of: length 2 with equal elements, length 3 with all elements equal, or length 3 with three consecutive increasing integers. Return whether such a partition exists. Constraints: 2 <= nums.length <= 10^5, 1 <= nums[i] <= 10^6.💡 Core Algorithmic Approaches
- Let
dp[i]indicate whether the prefixnums[:i]admits a valid partition, withdp[0] = true. - For each
i, test the three possible final blocks ending at indexi - 1. - A length-2 block requires the last two elements to be equal; a length-3 equal block requires three equal elements; a length-3 consecutive block requires the three to increase by one each step.
dp[i]is true if any valid block is preceded by a true prefix state.
💻 Benchmark Python3 Implementation
class Solution:
def validPartition(self, nums: List[int]) -> bool:
n = len(nums)
dp = [False] * (n + 1)
dp[0] = True
for i in range(1, n + 1):
if i >= 2 and nums[i - 1] == nums[i - 2] and dp[i - 2]:
dp[i] = True
if i >= 3 and dp[i - 3]:
a, b, c = nums[i - 3], nums[i - 2], nums[i - 1]
if a == b == c or (a + 1 == b and b + 1 == c):
dp[i] = True
return dp[n]⚡ Complexity Deep Dive
⏱️ Time Complexity
O(n): a constant number of checks per index.
💾 Space Complexity
O(n) for the DP array; three rolling booleans suffice.
⚠️ Interview Pitfalls & Follow-ups
- Mixing up the block shapes: the length-3 block has two variants, all equal or three consecutive increasing values.
- Off-by-one on the block boundaries: a length-3 block ending at
i - 1starts ati - 3. - Assuming only one block type may be used: any mix of the three shapes is allowed.
- Forgetting
dp[0] = True: the empty prefix must be considered valid for the first block to attach.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.