{x}
blog image

Check if There is a Valid Partition For The Array

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

Solution Explanation for Check if There is a Valid Partition For The Array

This problem asks whether a given integer array can be partitioned into contiguous subarrays, where each subarray meets one of three conditions:

  1. Length 2 with equal elements: e.g., [2, 2]
  2. Length 3 with equal elements: e.g., [4, 4, 4]
  3. Length 3 with consecutive increasing elements: e.g., [3, 4, 5]

Two approaches are presented below: Memoization Search and Dynamic Programming. Both have a time complexity of O(n) and space complexity of O(n), where n is the length of the input array.

This approach uses recursion with memoization to avoid redundant calculations. A recursive function dfs(i) checks if a valid partition is possible starting from index i.

Algorithm:

  1. Base Case: If i is greater than or equal to the array length, it means we've successfully partitioned the entire array, so return true.
  2. Check Conditions:
    • If the next two elements are equal (nums[i] == nums[i+1]), recursively check if a valid partition exists starting from i+2.
    • If the next three elements are equal (nums[i] == nums[i+1] == nums[i+2]), recursively check from i+3.
    • If the next three elements are consecutively increasing (nums[i+1] - nums[i] == 1 and nums[i+2] - nums[i+1] == 1), recursively check from i+3.
  3. Return Value: If any of the above conditions lead to a true result, return true; otherwise, return false.
  4. Memoization: Use a cache (@cache in Python, Boolean[] f in Java/C++/TypeScript) to store results for previously processed indices. This avoids recomputing the same subproblems.

Approach 2: Dynamic Programming

This approach iteratively builds a solution using dynamic programming. An array f stores boolean values indicating whether a valid partition is possible up to index i.

Algorithm:

  1. Initialization: f[0] = true (an empty array can be considered a valid partition).
  2. Iteration: Iterate through the array. For each index i:
    • Check the three conditions (similar to the memoization approach).
    • If any condition is true and the corresponding previous subarray had a valid partition (f[i-2] or f[i-3]), then f[i] = true.
  3. Result: f[n] (where n is the array length) will indicate if a valid partition is possible for the entire array.

Code Implementation (Python3, Java, C++, Go, TypeScript)

The code implementations are provided in the original response. Each implementation follows the algorithm described above, differing only in syntax and specific language features (e.g., @cache decorator in Python, Boolean[] array in Java). The dynamic programming solution is generally slightly more efficient because it avoids the overhead of recursive function calls. Both approaches have the same time and space complexity.

Time and Space Complexity Analysis

Both the Memoization Search and Dynamic Programming approaches have:

  • Time Complexity: O(n) - Each element in the array is processed at most a constant number of times.
  • Space Complexity: O(n) - The space is used to store the memoization cache or the dynamic programming array f.