Check if There is a Valid Partition For The Array

How it works

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.

Steps

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.

Complexity

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

Things to watch for

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.

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.

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.

from typing import List

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]

class Solution {
public:
    bool validPartition(vector<int>& nums) {
        bool dp[3] = {false, true, true};

        for (int i = nums.size() - 2; i >= 0; --i) {
            bool dp1 = dp[0];
            if (nums[i] == nums[i + 1] && dp[1]) {
                dp[0] = true;
            } else if (i < nums.size() - 2 && dp[2] &&
                      ((nums[i] == nums[i + 1] && nums[i] == nums[i + 2]) ||
                      (nums[i] + 1 == nums[i + 1] && nums[i + 1] == nums[i + 2] - 1))) {
                dp[0] = true;
            } else {
                dp[0] = false;
            }
            dp[2] = dp[1];
            dp[1] = dp1;
        }

        return dp[0];
    }
};