Watch 10 video solutions for Check if There is a Valid Partition For The Array, a medium level problem involving Array, Dynamic Programming. This walkthrough by NeetCodeIO has 10,881 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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 |