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:
2, equal elements. For example, the subarray [2,2] is good.3, equal elements. For example, the subarray [4,4,4] is good.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 <= 1051 <= nums[i] <= 106Problem 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.
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.
Python
C++
Java
C#
JavaScript
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.
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.
Python
C++
Java
C#
JavaScript
Time Complexity: O(n)
Space Complexity: O(1)
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:
i \ge n, return true.i and i+1 are equal, we can choose to make i and i+1 a subarray, and recursively call dfs(i+2).i, i+1 and i+2 are equal, we can choose to make i, i+1 and i+2 a subarray, and recursively call dfs(i+3).i, i+1 and i+2 increase by 1 in turn, we can choose to make i, i+1 and i+2 a subarray, and recursively call dfs(i+3).false, otherwise return true.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.
Python
Java
C++
Go
TypeScript
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.
Python
Java
C++
Go
TypeScript
| 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 | — |
| 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 |
Check if There is a Valid Partition For The Array - Leetcode 2369 - Python • NeetCodeIO • 10,881 views views
Watch 9 more video solutions →Practice Check if There is a Valid Partition For The Array with our built-in code editor and test cases.
Practice on FleetCode