# Check if There is a Valid Partition For The Array
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/check-if-there-is-a-valid-partition-for-the-array)
Canonical: https://scaleengineer.com/dsa/problems/check-if-there-is-a-valid-partition-for-the-array
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming)
**Data structures:** Array
**Companies:** [Coinbase](https://scaleengineer.com/companies/coinbase)
---
## Problem
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:

1. The subarray consists of **exactly** `2,` equal elements. For example, the subarray `[2,2]` is good.
2. The subarray consists of **exactly** `3,` equal elements. For example, the subarray `[4,4,4]` is good.
3. 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`.

**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.

**Constraints:**

* `2 <= nums.length <= 105`
* `1 <= nums[i] <= 106`

# Approaches
## Brute-Force Recursion
This approach uses a straightforward recursive method to explore every possible way the array can be partitioned. It checks from the beginning of the array, trying to form valid subarrays of size 2 or 3, and then recursively checks the remainder of the array.
**Time:** O(2^n), where n is the length of the array. The number of recursive calls can grow exponentially, similar to a Fibonacci sequence, as `T(n) ≈ T(n-2) + T(n-3)`. · **Space:** O(n), where n is the length of the array. This is for the recursion stack depth in the worst case.
**Pros:** Simple to conceptualize and implement.; Follows the problem definition closely.
**Cons:** Extremely inefficient due to a large number of redundant computations for the same subproblems.; Will likely result in a 'Time Limit Exceeded' error on platforms like LeetCode for the given constraints.
### Explanation
The brute-force recursive approach directly translates the problem statement into a recursive structure. We define a function that attempts to partition the array starting from a given index. This function tries to match the first 2 or 3 elements against the valid partition rules. If a match is found, it recursively calls itself on the rest of the array. This process continues until the entire array is partitioned or all possibilities are exhausted.

The core idea is to check every path. For example, from index `i`, we can potentially move to `i+2` or `i+3`. This branching leads to an exponential number of paths to explore.

Here is the Java implementation:
```java
class Solution {
    public boolean validPartition(int[] nums) {
        return solve(0, nums);
    }

    private boolean solve(int index, int[] nums) {
        int n = nums.length;
        if (index == n) {
            return true;
        }

        // Condition 1: Subarray of size 2
        if (index + 1 < n && nums[index] == nums[index + 1]) {
            if (solve(index + 2, nums)) {
                return true;
            }
        }

        // Condition 2 & 3: Subarray of size 3
        if (index + 2 < n) {
            // 3 equal elements
            if (nums[index] == nums[index + 1] && nums[index + 1] == nums[index + 2]) {
                if (solve(index + 3, nums)) {
                    return true;
                }
            }
            // 3 consecutive increasing elements
            if (nums[index] + 1 == nums[index + 1] && nums[index + 1] + 1 == nums[index + 2]) {
                if (solve(index + 3, nums)) {
                    return true;
                }
            }
        }

        return false;
    }
}
```
### Algorithm
- Define a recursive function, say `solve(index)`, which returns `true` if the subarray `nums[index...]` can be validly partitioned, and `false` otherwise.
- The base case for the recursion is when `index` reaches the end of the array (`index == nums.length`). This signifies that the entire array has been successfully partitioned, so we return `true`.
- If `index` exceeds the array bounds, it's an invalid state, so we return `false`.
- In the recursive step, we explore all valid partitioning choices from the current `index`:
  - **Check for a 2-element partition:** If `index + 1 < n` and `nums[index] == nums[index + 1]`, we can form a valid 2-element subarray. We then recursively call `solve(index + 2)` to check if the rest of the array can be partitioned. If it can, we've found a valid partition for the whole array.
  - **Check for a 3-element partition:** If `index + 2 < n`, we check if `nums[index...index+2]` forms a valid 3-element subarray (either all equal or consecutive increasing). If it does, we recursively call `solve(index + 3)`. If the recursive call returns `true`, we've found a solution.
- If any of the recursive calls return `true`, the function returns `true`. Otherwise, after trying all possibilities, it returns `false`.

## Bottom-Up Dynamic Programming
This approach improves upon the brute-force method by using dynamic programming to avoid recomputing results for overlapping subproblems. We use a DP array (or table) to store the results for subproblems, building the solution from the ground up (bottom-up).
**Time:** O(n), as we iterate through the array once to fill the DP table. · **Space:** O(n), for the DP array `dp` of size `n+1`.
**Pros:** Efficient with a linear time complexity.; Guaranteed to pass within the time limits.; Avoids deep recursion and potential stack overflow issues that can arise in the pure recursive approach.
**Cons:** Requires O(n) extra space for the DP array, which might be a concern for very large inputs, although it's acceptable for the given constraints.
### Explanation
The key observation for optimizing the recursive solution is that we repeatedly solve the same subproblems. Dynamic programming is the perfect tool for this. We can solve this iteratively using a technique called tabulation.

We define `dp[i]` as a boolean value indicating whether the prefix of the array of length `i` (i.e., `nums[0...i-1]`) can be validly partitioned. Our goal is to find `dp[n]`. The state `dp[i]` depends on the results of smaller prefixes, specifically `dp[i-2]` and `dp[i-3]`.

Here is the Java implementation:
```java
class Solution {
    public boolean validPartition(int[] nums) {
        int n = nums.length;
        if (n < 2) {
            return false;
        }
        boolean[] dp = new boolean[n + 1];
        dp[0] = true;

        for (int i = 2; i <= n; i++) {
            // Condition 1: Subarray of size 2
            if (nums[i - 2] == nums[i - 1]) {
                dp[i] = dp[i] || dp[i - 2];
            }

            // Condition 2 & 3: Subarray of size 3
            if (i >= 3) {
                boolean threeEqual = nums[i - 3] == nums[i - 2] && nums[i - 2] == nums[i - 1];
                boolean threeConsecutive = nums[i - 3] + 1 == nums[i - 2] && nums[i - 2] + 1 == nums[i - 1];
                if (threeEqual || threeConsecutive) {
                    dp[i] = dp[i] || dp[i - 3];
                }
            }
        }
        return dp[n];
    }
}
```
A top-down DP approach with memoization would also achieve the same time and space complexity.
### Algorithm
- Create a boolean DP array, `dp`, of size `n + 1`, where `dp[i]` will be `true` if the prefix `nums[0...i-1]` can be validly partitioned.
- Initialize `dp[0] = true`. This is the base case, representing a valid partition for an empty prefix.
- Iterate from `i = 2` to `n` (since the smallest partition is of size 2).
- Inside the loop, calculate `dp[i]` based on the three rules:
  - **Rule 1 (2 equal elements):** If `nums[i-2] == nums[i-1]`, it means the last two elements form a valid partition. If the prefix before that, `nums[0...i-3]`, was also validly partitionable (i.e., `dp[i-2]` is true), then `dp[i]` can be set to `true`.
  - **Rule 2 & 3 (3-element subarray):** If `i >= 3`, check if the last three elements `nums[i-3...i-1]` form a valid partition (either 3 equal or 3 consecutive increasing). If they do, and the prefix `nums[0...i-4]` was valid (`dp[i-3]` is true), then `dp[i]` can also be set to `true`.
- The final answer is the value of `dp[n]`.

## Space-Optimized Bottom-Up Dynamic Programming
This is the most efficient approach, optimizing the space complexity of the standard DP solution. By observing the dependencies in the DP recurrence relation, we can see that we only need to store the last three results to compute the next one. This allows us to reduce the space from O(n) to O(1).
**Time:** O(n), as we still need to iterate through the array once. · **Space:** O(1), as we only use a few variables to store the previous DP states, regardless of the input size.
**Pros:** Most optimal solution with linear time and constant space complexity.; Highly efficient for very large inputs.
**Cons:** The logic can be slightly more complex to reason about due to the rolling variables instead of a direct-access array.
### Explanation
We can further optimize the bottom-up DP approach in terms of space. The value of `dp[i]` depends only on `dp[i-2]` and `dp[i-3]`. This means that at any point in our iteration, we only need to know the results for the last three indices. We can achieve this by using a few variables to store these previous states, effectively reducing the space complexity to constant.

We'll use three variables to keep track of the necessary previous DP values as we iterate through the array. This avoids allocating an array of size `n+1` and is the most optimal solution for this problem.

Here is the space-optimized Java implementation:
```java
class Solution {
    public boolean validPartition(int[] nums) {
        int n = nums.length;

        // We only need to store the last 3 dp values.
        // Let three_back, two_back, one_back be dp[i-3], dp[i-2], dp[i-1]
        boolean three_back = true;  // Base case for dp[0]
        boolean two_back = false;   // dp[1] is always false
        boolean one_back = (n >= 2 && nums[0] == nums[1]); // Base case for dp[2]

        if (n == 2) {
            return one_back;
        }

        for (int i = 3; i <= n; i++) {
            boolean current_dp = false;
            // Case 1: Last two elements form a valid partition (e.g., [x,x])
            if (nums[i - 2] == nums[i - 1]) {
                current_dp = current_dp || two_back; // check dp[i-2]
            }
            // Case 2: Last three elements form a valid partition
            boolean threeEqual = nums[i - 3] == nums[i - 2] && nums[i - 2] == nums[i - 1];
            boolean threeConsecutive = nums[i - 3] + 1 == nums[i - 2] && nums[i - 2] + 1 == nums[i - 1];
            if (threeEqual || threeConsecutive) {
                current_dp = current_dp || three_back; // check dp[i-3]
            }
            
            // Update states for the next iteration
            three_back = two_back;
            two_back = one_back;
            one_back = current_dp;
        }
        return one_back; // This holds the final result, dp[n]
    }
}
```
### Algorithm
- The calculation of `dp[i]` only depends on `dp[i-2]` and `dp[i-3]`. This allows us to optimize the space.
- Instead of a full DP array, we only need to maintain the last three DP states. Let's use three boolean variables: `three_back`, `two_back`, and `one_back` to represent `dp[i-3]`, `dp[i-2]`, and `dp[i-1]` respectively.
- Initialize the variables based on the base cases:
  - `three_back = true` (representing `dp[0]`)
  - `two_back = false` (representing `dp[1]`, which is not reachable by a valid partition)
  - `one_back = (nums[0] == nums[1])` (representing `dp[2]`)
- Handle the `n=2` case separately.
- Iterate from `i = 3` to `n`. In each iteration, calculate `current_dp` based on `two_back` and `three_back`.
  - `current_dp` is true if `(nums[i-2] == nums[i-1] && two_back)` is true, or if `(valid 3-element partition ending at i-1 && three_back)` is true.
- After computing `current_dp`, update the state variables for the next iteration: `three_back` becomes `two_back`, `two_back` becomes `one_back`, and `one_back` becomes `current_dp`.
- The final result is the value of `one_back` after the loop finishes.

# Solutions
### Java

```java
class Solution {
private
  int n;
private
  int[] f;
private
  int[] nums;
public
  boolean validPartition(int[] nums) {
    this.nums = nums;
    n = nums.length;
    f = new int[n];
    Arrays.fill(f, -1);
    return dfs(0);
  }
private
  boolean dfs(int i) {
    if (i == n) {
      return true;
    }
    if (f[i] != -1) {
      return f[i] == 1;
    }
    boolean res = false;
    if (i < n - 1 && nums[i] == nums[i + 1]) {
      res = res || dfs(i + 2);
    }
    if (i < n - 2 && nums[i] == nums[i + 1] && nums[i + 1] == nums[i + 2]) {
      res = res || dfs(i + 3);
    }
    if (i < n - 2 && nums[i + 1] - nums[i] == 1 &&
        nums[i + 2] - nums[i + 1] == 1) {
      res = res || dfs(i + 3);
    }
    f[i] = res ? 1 : 0;
    return res;
  }
}

```

### CPP

```cpp
class Solution {
public:
  vector<int> f;
  vector<int> nums;
  int n;
  bool validPartition(vector<int> &nums) {
    n = nums.size();
    this->nums = nums;
    f.assign(n, -1);
    return dfs(0);
  }
  bool dfs(int i) {
    if (i == n)
      return true;
    if (f[i] != -1)
      return f[i] == 1;
    bool res = false;
    if (i < n - 1 && nums[i] == nums[i + 1])
      res = res || dfs(i + 2);
    if (i < n - 2 && nums[i] == nums[i + 1] && nums[i + 1] == nums[i + 2])
      res = res || dfs(i + 3);
    if (i < n - 2 && nums[i + 1] - nums[i] == 1 &&
        nums[i + 2] - nums[i + 1] == 1)
      res = res || dfs(i + 3);
    f[i] = res ? 1 : 0;
    return res;
  }
};

```

### Python

```python
class Solution:
    def validPartition(self, nums: List[int]) -> bool: @ cache def dfs(i): if i == n: return True res = False if i < n - 1 and nums[i] == nums[i + 1]: res = res or dfs(i + 2) if i < n - 2 and nums[i] == nums[i + 1] and nums[i + 1] == nums[i + 2]: res = res or dfs(i + 3) if (i < n - 2 and nums[i + 1] - nums[i] == 1 and nums[i + 2] - nums[i + 1] == 1): res = res or dfs(i + 3) return res n = len(nums) return dfs(0)

```