Check if There is a Valid Partition For The Array - Solution & Explanation
Problem Statement
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
Approach Overview
Problem Overview: You receive an integer array and must determine whether it can be partitioned into contiguous groups that follow strict rules: two equal numbers [x, x], three equal numbers [x, x, x], or three consecutive increasing numbers [x, x+1, x+2]. The entire array must be covered without overlap.
Approach 1: Dynamic Programming (O(n) time, O(n) space)
The most reliable strategy uses dynamic programming. Define dp[i] as whether the first i elements can form a valid partition. Iterate through the array and check whether the current position can extend a valid partition using one of the allowed patterns. For each index, verify the last two elements for the [x, x] pattern or the last three elements for [x, x, x] and [x, x+1, x+2]. If a rule matches and the previous state dp[i-k] was valid, mark dp[i] as true. This builds the solution incrementally with a single pass through the array. Time complexity is O(n) because each index performs constant checks, while space complexity is O(n) for the DP table.
Approach 2: Greedy State Compression (O(n) time, O(1) space)
The DP solution only depends on the previous two or three states, so storing the entire table is unnecessary. You can compress the state and track only a few booleans representing dp[i-1], dp[i-2], and dp[i-3]. During iteration, compute the current validity using the same partition rules and shift the state variables forward. This behaves like a greedy rolling decision process while still respecting the dynamic programming transitions. The algorithm still scans the array once, so time complexity remains O(n), but the space complexity drops to O(1). This version is ideal when optimizing memory or writing concise interview code.
Recommended for interviews: Interviewers expect the dynamic programming reasoning because it clearly models the partition validity at each prefix of the array. After presenting the DP idea, compressing it to constant space demonstrates deeper understanding and optimization skills. Both approaches rely on recognizing valid local patterns and validating them against previously solved subproblems.
Approach 1: Dynamic Programming Approach
The dynamic programming approach uses a dp array where dp[i] is true if there is a valid partition for the subarray nums[0..i]. We initialize dp[0] as false because there cannot be a valid partition for a single element. Then, for each i, we check for all valid configurations of subarrays ending at i, i.e., [i-1,i], [i-2,i], and [i-2,i-1,i], updating the dp array accordingly.
This code uses a dynamic programming approach to iterate through the list, checking and updating the validity of partitions.
Code
Python
C++
Java
C#
JavaScript
Complexity
Time Complexity: O(n), where n is the length of the array since we iterate through the array once.
Space Complexity: O(n) for the dp array.
Approach 2: Greedy Approach
The greedy approach attempts to form valid subarrays by traversing the array and greedily picking the largest valid partition at each position. While processing the elements, if a valid subarray is found, the elements involved are ignored in subsequent iterations. Note, this provides a simple but possibly non-optimal solution for certain edge cases.
This solution greedily attempts to find and skip valid subarrays during a single pass through the array, which can be efficient but is less robust than dynamic programming.
Code
Python
C++
Java
C#
JavaScript
Complexity
Time Complexity: O(n)
Space Complexity: O(1)
Approach 3: Memoization Search
We design a function dfs(i), which represents whether there is a valid partition starting from index i. So the answer is dfs(0).
The execution process of the function dfs(i) is as follows:
- If
i \ge n, returntrue. - If the elements at index
iandi+1are equal, we can choose to makeiandi+1a subarray, and recursively calldfs(i+2). - If the elements at index
i,i+1andi+2are equal, we can choose to makei,i+1andi+2a subarray, and recursively calldfs(i+3). - If the elements at index
i,i+1andi+2increase by1in turn, we can choose to makei,i+1andi+2a subarray, and recursively calldfs(i+3). - If none of the above conditions are met, return
false, otherwise returntrue.
That is:
$
dfs(i) = OR
\begin{cases}
true,&i \ge n\
dfs(i+2),&i+1 < n\ and\ nums[i] = nums[i+1]\
dfs(i+3),&i+2 < n\ and\ nums[i] = nums[i+1] = nums[i+2]\
dfs(i+3),&i+2 < n\ and\ nums[i+1] - nums[i] = 1\ and\ nums[i+2] - nums[i+1] = 1
\end{cases}
To avoid repeated calculations, we use the method of memoization search.
The time complexity is O(n), and the space complexity is O(n). Where n$ is the length of the array.
Code
Python
Java
C++
Go
TypeScript
Approach 4: Dynamic Programming
We can convert the memoization search in Solution 1 into dynamic programming.
Let f[i] represent whether there is a valid partition for the first i elements of the array. Initially, f[0] = true, and the answer is f[n].
The state transition equation is as follows:
$
f[i] = OR
\begin{cases}
true,&i = 0\
f[i-2],&i-2 \ge 0\ and\ nums[i-1] = nums[i-2]\
f[i-3],&i-3 \ge 0\ and\ nums[i-1] = nums[i-2] = nums[i-3]\
f[i-3],&i-3 \ge 0\ and\ nums[i-1] - nums[i-2] = 1\ and\ nums[i-2] - nums[i-3] = 1
\end{cases}
The time complexity is O(n), and the space complexity is O(n). Where n$ is the length of the array.
Code
Python
Java
C++
Go
TypeScript
Complexity Comparison
| Approach | Complexity |
|---|---|
| Dynamic Programming Approach | Time Complexity: O(n), where n is the length of the array since we iterate through the array once. |
| Greedy Approach | Time Complexity: O(n) |
| Memoization Search | — |
| Dynamic Programming | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Dynamic Programming (DP Table) | O(n) | O(n) | Best for explaining the logic clearly and deriving the recurrence during interviews |
| Greedy / State Compressed DP | O(n) | O(1) | Use when optimizing memory since only the last few DP states are required |
Video Solution
Check if There is a Valid Partition For The Array - Leetcode 2369 - Python • NeetCodeIO • 11,006 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Check if There is a Valid Partition For The Array easy or hard?
Check if There is a Valid Partition For The Array Python/Java solution
How to solve Check if There is a Valid Partition For The Array in O(n)?
What is the best approach for Check if There is a Valid Partition For The Array?
Is Check if There is a Valid Partition For The Array asked at Google/Amazon/Meta?
What data structure is used in Check if There is a Valid Partition For The Array?
What is the time complexity of Check if There is a Valid Partition For The Array?
Ready to solve this problem?
Practice Check if There is a Valid Partition For The Array with our built-in code editor and test cases.
Practice on FleetCode