Check if There is a Valid Partition of the Array
Problem
You are given an integer array nums (2 ≤ nums.length ≤ 10⁵, 1 ≤ nums[i] ≤ 10⁶). Split it into contiguous blocks so that every block has one of exactly three shapes: two equal values like [7, 7], three equal values like [7, 7, 7], or three values that each step up by exactly 1 like [3, 4, 5]. Return true if at least one such split covers the whole array.
Every element must belong to exactly one block — no other block length or shape is allowed.
nums = [4, 4, 4, 5, 6]truedef valid_partition(nums):
n = len(nums)
dp = [False] * (n + 1)
dp[0] = True
for i in range(2, n + 1):
if dp[i - 2] and nums[i - 1] == nums[i - 2]:
dp[i] = True
if i >= 3 and dp[i - 3]:
a, b, c = nums[i - 3], nums[i - 2], nums[i - 1]
if a == b == c or (b == a + 1 and c == b + 1):
dp[i] = True
return dp[n]function validPartition(nums) {
const n = nums.length;
const dp = new Array(n + 1).fill(false);
dp[0] = true;
for (let i = 2; i <= n; i++) {
if (dp[i - 2] && nums[i - 1] === nums[i - 2]) dp[i] = true;
if (i >= 3 && dp[i - 3]) {
const a = nums[i - 3], b = nums[i - 2], c = nums[i - 1];
if ((a === b && b === c) || (b === a + 1 && c === b + 1)) dp[i] = true;
}
}
return dp[n];
}boolean validPartition(int[] nums) {
int n = nums.length;
boolean[] dp = new boolean[n + 1];
dp[0] = true;
for (int i = 2; i <= n; i++) {
if (dp[i - 2] && nums[i - 1] == nums[i - 2]) dp[i] = true;
if (i >= 3 && dp[i - 3]) {
int a = nums[i - 3], b = nums[i - 2], c = nums[i - 1];
if ((a == b && b == c) || (b == a + 1 && c == b + 1)) dp[i] = true;
}
}
return dp[n];
}bool validPartition(vector<int>& nums) {
int n = nums.size();
vector<bool> dp(n + 1, false);
dp[0] = true;
for (int i = 2; i <= n; i++) {
if (dp[i - 2] && nums[i - 1] == nums[i - 2]) dp[i] = true;
if (i >= 3 && dp[i - 3]) {
int a = nums[i - 3], b = nums[i - 2], c = nums[i - 1];
if ((a == b && b == c) || (b == a + 1 && c == b + 1)) dp[i] = true;
}
}
return dp[n];
}Explanation
The key observation is that every legal block is short: it covers exactly 2 or 3 elements. So whether a prefix of the array can be partitioned only depends on slightly shorter prefixes. That is a textbook setup for dynamic programming over prefixes: let dp[i] mean "the first i numbers can be split into valid blocks", with dp[0] = true because the empty prefix needs no blocks at all.
To decide dp[i], look only at the block that ends at index i - 1. If the last two values are equal and dp[i - 2] is true, a pair block finishes the prefix. If the last three values are all equal, or they increase by exactly 1 each step, and dp[i - 3] is true, a triple block finishes it. If neither rule fires, dp[i] stays false. The final answer is simply dp[n].
Walk through the default example [4, 4, 4, 5, 6]. dp[1] is false since no block has length 1. dp[2] is true via the pair [4, 4] on top of dp[0]. dp[3] is true via the equal triple [4, 4, 4]. dp[4] is false: [4, 5] is not a pair and [4, 4, 5] is neither triple shape. Finally dp[5] is true because [4, 5, 6] is a consecutive triple sitting on dp[2] — so the answer is true, realized by the split [4, 4] + [4, 5, 6].
Why does this beat trying partitions directly? A greedy choice (say, always taking a pair when you can) fails on inputs like [1, 1, 1, 1, 1]: grabbing pairs greedily leaves a stranded final [1], yet the split [1, 1] + [1, 1, 1] is perfectly valid. The DP avoids that trap by remembering every achievable prefix, so all combinations of block choices are implicitly explored without ever enumerating them.
Each prefix length does a constant amount of work — two array comparisons for the pair rule and a handful for the triple rules — so the running time is O(n). The boolean table costs O(n) space, and since transitions only read dp[i - 2] and dp[i - 3], you could even shrink it to three rolling booleans for O(1) space.