You are given a 0-indexed integer array nums. You have to partition the array into one or more contiguous subarrays.

We call a partition of the array valid if each of the obtained subarrays satisfies one of the following conditions:


	The subarray consists of exactly 2 equal elements. For example, the subarray [2,2] is good.
	The subarray consists of exactly 3 equal elements. For example, the subarray [4,4,4] is good.
	The subarray consists of exactly 3 consecutive increasing elements, that is, the difference between adjacent elements is 1. For example, the subarray [3,4,5] is good, but the subarray [1,3,5] is not.


Return true if the array has at least one valid partition. Otherwise, return false.

&nbsp;
Example 1:

Input: nums = [4,4,4,5,6]
Output: true
Explanation: The array can be partitioned into the subarrays [4,4] and [4,5,6].
This partition is valid, so we return true.


Example 2:

Input: nums = [1,1,1,2]
Output: false
Explanation: There is no valid partition for this array.


&nbsp;
Constraints:


	2 &lt;= nums.length &lt;= 105
	1 &lt;= nums[i] &lt;= 106


class Solution:
    def validPartition(self, nums: List[int]) -> bool:
        n = len(nums)
        
        dp = [False] * 3
        dp[0] = True  # An empty partition is always valid

        for i in range(2, n + 1):
            ans = False

            if nums[i - 1] == nums[i - 2]:
                ans = ans or dp[(i - 2) % 3]
            if i >= 3 and nums[i - 1] == nums[i - 2] == nums[i - 3]:
                ans = ans or dp[(i - 3) % 3]
            if i >= 3 and nums[i - 1] == nums[i - 2] + 1 == nums[i - 3] + 2:
                ans = ans or dp[(i - 3) % 3]

            dp[i % 3] = ans

        return dp[n % 3]
// Time O(n)
// Space O(n)
class Solution {
    public boolean validPartition(int[] nums) {
        boolean[] dp = new boolean[nums.length+1];
        dp[0]=true; // base case
        for (int i = 2; i <= nums.length; i++){
            dp[i]|= nums[i-1]==nums[i-2] && dp[i-2]; // cond 1
            dp[i]|= i>2 && nums[i-1] == nums[i-2] && nums[i-2] == nums[i-3] && dp[i-3]; // cond 2
            dp[i]|= i>2 && nums[i-1]-nums[i-2]==1 && nums[i-2]-nums[i-3]==1 && dp[i-3]; // cond 3
        }
        return dp[nums.length];
    }
}
class Solution {
    
public:
    int solve(int i, vector<int> &nums, vector<int> &dp)
    {
        if (i == nums.size()) return 1;
        if (dp[i] != -1) return dp[i];
        
        int ans = 0;
        if (i+1 < nums.size() and nums[i] == nums[i+1])
            ans = max(ans, solve(i+2, nums, dp));
        if (i+2 < nums.size())
        {
            if (nums[i] == nums[i+1] && nums[i+1] == nums[i+2])
                ans = max(ans, solve(i+3, nums, dp));
            else if (abs(nums[i]-nums[i+1]) == 1 and abs(nums[i+1]-nums[i+2]) == 1)
                ans = max(ans, solve(i+3, nums, dp));
            
        }
        
        return dp[i] = ans;
    }
    bool validPartition(vector<int>& nums) {
        vector<int> dp(nums.size()+1, -1);
        return solve(0, nums, dp);
    }
};
var validPartition = function(nums) {
  let n = nums.length, memo = Array(n).fill(-1);
  return dp(0);

  function dp(i) {
    if (i === n) return true;
    if (i === n - 1) return false;
    if (memo[i] !== -1) return memo[i];

    if (nums[i] === nums[i + 1] && dp(i + 2)) return memo[i] = true;
    if (i < n - 2) {
      if (!dp(i + 3)) return memo[i] = false;
      let hasThreeEqual = nums[i] === nums[i + 1] && nums[i + 1] === nums[i + 2];
      let hasThreeConsecutive = nums[i] + 1 === nums[i + 1] && nums[i + 1] + 1 === nums[i + 2];
      if (hasThreeEqual || hasThreeConsecutive) return memo[i] = true;
    }
    return memo[i] = false;
  }
};
Check if There is a Valid Partition For The Array