⚡Flashcard Drill➔
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

  1. Let dp[i] indicate whether the prefix nums[:i] admits a valid partition, with dp[0] = true.
  2. For each i, test the three possible final blocks ending at index i - 1.
  3. 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.
  4. 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 - 1 starts at i - 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.
🎯 Drill This Card Now➔

🧩 Related 1-D Dynamic Programming Problems