Check if There is a Valid Partition For The Array

Problem Statement

In this task, you're provided with an array nums, which is indexed from 0. The goal is to divide this array into one or more contiguous subarrays that meet certain criteria. A subarray is considered valid if it:

1. Contains exactly two identical elements ([2,2]).
2. Has precisely three identical elements ([4,4,4]).
3. Consists of three consecutive and incrementally increasing numbers ([3,4,5]), where the difference between adjacent numbers is 1. Subarrays like [1,3,5], despite being numerically ordered, do not meet this condition due to the non-consecutive nature of the increments.

The function should return true if there is at least one way to partition the array such that all resulting subarrays are valid based on the above conditions. If no valid partitioning is possible, the function should return false.

Examples

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

Approach and Intuition

When determining if the array can be validly partitioned, consider the following key insights and approaches drawn from the given examples and constraints:

1. Identify Pairs and Triplets:

   • Start by looking for simple conditions such as pairs (two identical elements) and triplets (three identical elements).
   • When these conditions are met, they clearly define a segment of the array making them easy to extract and evaluate.

2. Sequential Analysis:

   • Attempt to check for sequences of three consecutive increasing numbers.
   • This step involves comparing each element with the next and seeing if they form a sequence like x, x+1, x+2.

3. Greedy Partitioning:

   • As you traverse through the array, use a greedy approach to partition the array wherever a valid condition is met.
   • If a triplet or a valid sequence is recognized, mark that portion of the array and move to the next segment continuing the search without reconsidering the partitioned segment.

4. Edge Cases:

   • Arrays that have fewer than the minimum numbers needed for any partition (less than 2 elements) will automatically not satisfy the conditions although the constraints guarantee a minimum length of 2.
   • If you reach the end of the array and parts of it remain unpartitioned without satisfying any of the valid conditions, the function should return false.

5. Iterative Checking:

   • Iteratively explore combinations starting from index 0, using conditional checks for doubles and triples.
   • If neither condition can be satisfied at a given point, consider potential sequences.

Through orderly and stepwise examination of nums, employing the above strategies will efficiently determine if valid partitions exist, fulfilling the criteria set forth.

Solutions

class Solution {
    public boolean isValidPartition(int[] elements) {
        int length = elements.length;
        boolean[] memo = new boolean[3];
        memo[0] = true;
    
        for (int i = 0; i < length; i++) {
            int memoIdx = i + 1;
            boolean currentValid = false;
    
            if (i > 0 && elements[i] == elements[i - 1]) {
                currentValid |= memo[(memoIdx - 2) % 3];
            }
            if (i > 1 && elements[i] == elements[i - 1] && elements[i] == elements[i - 2]) {
                currentValid |= memo[(memoIdx - 3) % 3];
            }
            if (i > 1 && elements[i] == elements[i - 1] + 1 && elements[i] == elements[i - 2] + 2) {
                currentValid |= memo[(memoIdx - 3) % 3];
            }
    
            memo[memoIdx % 3] = currentValid;
        }
    
        return memo[length % 3];
    }
}