2369. Check if There is a Valid Partition For The Array - Explanation

Problem Link

1. Recursion

Intuition

We need to partition the array into subarrays where each subarray is either two equal elements, three equal elements, or three consecutive increasing elements. At each position, we can try taking 2 or 3 elements if they form a valid pattern, then recursively check if the remainder can also be validly partitioned.

Algorithm

1. Define a recursive function starting at index 0.
2. Base case: if we reach the end of the array, return true (valid partition found).
3. At each position, try two options:
   • If the next two elements are equal, recursively check from index i+2.
   • If the next three elements are either all equal or form consecutive increasing values, recursively check from index i+3.
4. Return true if any recursive path leads to a valid partition.
5. Return false if no valid partition is possible from the current position.

class Solution:
    def validPartition(self, nums: List[int]) -> bool:
        def dfs(i):
            if i == len(nums):
                return True

            res = False
            if i < len(nums) - 1 and nums[i] == nums[i + 1]:
                res = dfs(i + 2)
            if i < len(nums) - 2:
                if ((nums[i] == nums[i + 1] == nums[i + 2]) or
                    (nums[i] + 1 == nums[i + 1] and nums[i + 1] + 1 == nums[i + 2])
                ):
                    res = res or dfs(i + 3)
            return res

        return dfs(0)

Time & Space Complexity

• Time complexity: $O(2 ^ n)$
• Space complexity: $O(n)$

---

2. Dynamic Programming (Top-Down)

Intuition

The recursive solution has overlapping subproblems because we might reach the same index through different partition choices. By memoizing results for each starting index, we avoid redundant computations. Once we compute whether a valid partition exists from index i, we store it and reuse it.

Algorithm

1. Create a memoization map to store results for each starting index.
2. Define a recursive function that first checks if the result for the current index is already computed.
3. Base case: if we reach the end of the array, return true.
4. Try forming a valid subarray of length 2 (two equal elements) and recurse.
5. Try forming a valid subarray of length 3 (three equal or three consecutive) and recurse.
6. Store the result in the memo before returning.
7. Return the result for index 0.

class Solution:
    def validPartition(self, nums: List[int]) -> bool:
        dp = { len(nums) : True }
        def dfs(i):
            if i in dp:
                return dp[i]

            res = False
            if i < len(nums) - 1 and nums[i] == nums[i + 1]:
                res = dfs(i + 2)
            if i < len(nums) - 2:
                if ((nums[i] == nums[i + 1] == nums[i + 2]) or
                    (nums[i] + 1 == nums[i + 1] and nums[i + 1] + 1 == nums[i + 2])
                ):
                    res = res or dfs(i + 3)

            dp[i] = res
            return res

        return dfs(0)

Time & Space Complexity

• Time complexity: $O(n)$
• Space complexity: $O(n)$

---

3. Dynamic Programming (Bottom-Up)

Intuition

Instead of starting from the beginning and recursing forward, we can build our solution from the ground up. We define dp[i] as whether the first i elements can be validly partitioned. We iterate through the array and for each position, check if we can extend a valid partition by adding a valid 2-element or 3-element subarray.

Algorithm

1. Create a DP array of size n+1, initialized to false.
2. Set dp[0] = true (empty prefix is valid).
3. Iterate from index 2 to n:
   • If elements at positions i-1 and i-2 are equal, and dp[i-2] is true, set dp[i] = true.
   • If i > 2 and the last three elements form a valid pattern (all equal or consecutive), and dp[i-3] is true, set dp[i] = true.
4. Return dp[n].

class Solution:
    def validPartition(self, nums: List[int]) -> bool:
        dp = [False] * (len(nums) + 1)
        dp[0] = True

        for i in range(2, len(nums) + 1):
            if nums[i - 1] == nums[i - 2]:
                dp[i] = dp[i] or dp[i - 2]
            if i > 2 and ((nums[i - 1] == nums[i - 2] == nums[i - 3]) or
                          (nums[i - 3] + 1 == nums[i - 2] and nums[i - 2] + 1 == nums[i - 1])):
                dp[i] = dp[i] or dp[i - 3]

        return dp[len(nums)]

Time & Space Complexity

• Time complexity: $O(n)$
• Space complexity: $O(n)$

---

4. Dynamic Programming (Space Optimized)

Intuition

Since each DP state only depends on the previous three states (dp[i-1], dp[i-2], dp[i-3]), we do not need to store the entire DP array. We can use just three variables and rotate them as we iterate through the array from right to left.

Algorithm

1. Use three variables to represent the DP states for positions i, i+1, and i+2.
2. Initialize them to represent the base cases (true for positions at or beyond the array end).
3. Iterate from the second-to-last index down to 0.
4. At each position, compute the new DP value based on:
   • Whether taking 2 elements forms a valid subarray and the state two positions ahead is true.
   • Whether taking 3 elements forms a valid subarray and the state three positions ahead is true.
5. Shift the variables to prepare for the next iteration.
6. Return the final value which represents whether the entire array can be partitioned.

class Solution:
    def validPartition(self, nums: List[int]) -> bool:
        dp = [False, True, True]

        for i in range(len(nums) - 2, -1, -1):
            dp1 = dp[0]
            if nums[i] == nums[i + 1] and dp[1]:
                dp[0] = True
            elif i < len(nums) - 2 and dp[2] and (
                (nums[i] == nums[i + 1] == nums[i + 2]) or
                (nums[i] + 1 == nums[i + 1] and nums[i + 1] == nums[i + 2] - 1)
            ):
                dp[0] = True
            else:
                dp[0] = False
            dp[2] = dp[1]
            dp[1] = dp1

        return dp[0]

Time & Space Complexity

• Time complexity: $O(n)$
• Space complexity: $O(1)$ extra space.

---

Common Pitfalls

Confusing Consecutive with Equal Elements

The three-element partition allows either three equal elements OR three consecutive increasing elements, but not both conditions mixed. Writing nums[i] == nums[i+1] + 1 instead of nums[i] + 1 == nums[i+1] reverses the direction and checks for decreasing sequences.

# Wrong: nums[i] == nums[i+1] + 1 (checks decreasing)
# Correct:
nums[i] + 1 == nums[i + 1] and nums[i + 1] + 1 == nums[i + 2]

Forgetting to Check Both 2-Element and 3-Element Options

At each position, you must consider both taking 2 elements (if they're equal) AND taking 3 elements (if they form a valid pattern). Only checking one option or using else if when both could be valid may miss the correct partition path.

# Must use OR logic to try both options:
res = dfs(i + 2) if valid_pair else False
res = res or dfs(i + 3) if valid_triple else res

Off-by-One Errors in DP Array Indexing

In the bottom-up DP approach, dp[i] represents whether the first i elements can be partitioned. When checking if elements form a valid pattern, you must use nums[i-1], nums[i-2], nums[i-3] (0-indexed array access) rather than nums[i], which would be out of bounds or reference the wrong elements.