Check if There is a Valid Partition For The Array
MedPrompt
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
3consecutive increasing elements, that is, the difference between adjacent elements is1. 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 <= 1051 <= nums[i] <= 106
Approaches
3 approaches with complexity analysis and trade-offs.
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.
Algorithm
- Define a recursive function, say
solve(index), which returnstrueif the subarraynums[index...]can be validly partitioned, andfalseotherwise. - The base case for the recursion is when
indexreaches the end of the array (index == nums.length). This signifies that the entire array has been successfully partitioned, so we returntrue. - If
indexexceeds the array bounds, it's an invalid state, so we returnfalse. - In the recursive step, we explore all valid partitioning choices from the current
index:- Check for a 2-element partition: If
index + 1 < nandnums[index] == nums[index + 1], we can form a valid 2-element subarray. We then recursively callsolve(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 ifnums[index...index+2]forms a valid 3-element subarray (either all equal or consecutive increasing). If it does, we recursively callsolve(index + 3). If the recursive call returnstrue, we've found a solution.
- Check for a 2-element partition: If
- If any of the recursive calls return
true, the function returnstrue. Otherwise, after trying all possibilities, it returnsfalse.
Walkthrough
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:
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; }}Complexity
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.
Trade-offs
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.
Solutions
Solution
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; }}Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.