Check if There is a Valid Partition For The Array — Solution
Check if There is a Valid Partition For The Array solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.
Check if There is a Valid Partition For The Array is a medium coding problem on arrays and dynamic programming, asked in Amazon and Google interviews.
- Difficulty: Medium
- Topics: Arrays, Dynamic Programming
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Cut the integer array nums into one or more contiguous pieces. The partition is valid when every piece is one of:
- exactly 2 equal elements, e.g.
[4,4]; - exactly 3 equal elements, e.g.
[4,4,4]; - exactly 3 consecutive increasing elements, each one more than the previous, e.g.
[3,4,5](but not[1,3,5]).
Return true if nums has at least one valid partition, and false otherwise.
Example 1
Input: nums = [3,3,5,6,7]
Output: true
Explanation: `[3,3]` and `[5,6,7]`.
Example 2
Input: nums = [7,8,9,9]
Output: false
Explanation: `[7,8,9]` would leave a lone `9`, and `[7,8]` is not a valid piece.
Example 3
Input: nums = [1,1,1,1]
Output: true
Explanation: `[1,1]` and `[1,1]`.
Constraints
2 <= nums.length <= 10^51 <= nums[i] <= 10^6
Hints for Check if There is a Valid Partition For The Array
Hint 1
Greedily taking the first piece that fits can paint you into a corner —
[1,1,1,2,3]needs[1,1]first.Hint 2
Let
dp[i]say whether the firstielements can be partitioned validly.Hint 3
dp[i]is true if the last piece is a valid 2-piece anddp[i-2]holds, or a valid 3-piece anddp[i-3]holds.
How to solve Check if There is a Valid Partition For The Array
Every valid partition ends in a piece of length 2 or 3, so whether a prefix can be partitioned depends only on the two or three prefixes just before it — a linear DP.
Approach
- Set
dp[0] = true(the empty prefix) and computedp[i]fori = 1..n. dp[i]is true ifi >= 2,nums[i-1] == nums[i-2]anddp[i-2]is true.- It is also true if
i >= 3,dp[i-3]is true and the last three are all equal or formx, x+1, x+2. - Return
dp[n].
Why it works
Removing the last piece of any valid partition of the first i elements leaves a valid partition of the first i - 2 or i - 3 elements, and conversely appending a valid last piece to a valid partition is valid. So the recurrence captures exactly the partitionable prefixes.
Complexity
- Time —
O(n) - Space —
O(n), or O(1) keeping only the last three values
Pitfalls
- A first-fit greedy fails; both piece lengths must be tried.
- 'Consecutive increasing' means steps of exactly +1 —
[1,2,4]or[3,2,1]do not qualify. - Four equal elements are two pairs, not one piece.
Reference solution
Python
from typing import List
def validPartition(nums: List[int]) -> bool:
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
elif 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]Java
public static 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;
} else 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];
}C++
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;
} else 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];
}JavaScript
var validPartition = function(nums) {
var n = nums.length;
var dp = new Array(n + 1).fill(false);
dp[0] = true;
for (var i = 2; i <= n; i++) {
if (dp[i - 2] && nums[i - 1] === nums[i - 2]) {
dp[i] = true;
} else if (i >= 3 && dp[i - 3]) {
var 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];
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Dynamic Programming