2369. Check if There is a Valid Partition For The Array
Description
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
3
consecutive 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 <= 105
1 <= nums[i] <= 106
Solutions
Solution 1: 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$, return $true$.
- If the elements at index $i$ and $i+1$ are equal, we can choose to make $i$ and $i+1$ a subarray, and recursively call $dfs(i+2)$.
- If the elements at index $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)$.
- If the elements at index $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)$.
- If none of the above conditions are met, return $false$, otherwise return $true$.
That is:
$$ dfs(i) = \textit{OR} \begin{cases} true,&i \ge n\ dfs(i+2),&i+1 < n \textit{and} \textit{nums}[i] = \textit{nums}[i+1]\ dfs(i+3),&i+2 < n \textit{and} \textit{nums}[i] = \textit{nums}[i+1] = \textit{nums}[i+2]\ dfs(i+3),&i+2 < n \textit{and} \textit{nums}[i+1] - \textit{nums}[i] = 1 \textit{and} \textit{nums}[i+2] - \textit{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.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
|
Solution 2: 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] = \textit{OR} \begin{cases} true,&i = 0\ f[i-2],&i-2 \ge 0 \textit{and} \textit{nums}[i-1] = \textit{nums}[i-2]\ f[i-3],&i-3 \ge 0 \textit{and} \textit{nums}[i-1] = \textit{nums}[i-2] = \textit{nums}[i-3]\ f[i-3],&i-3 \ge 0 \textit{and} \textit{nums}[i-1] - \textit{nums}[i-2] = 1 \textit{and} \textit{nums}[i-2] - \textit{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.
1 2 3 4 5 6 7 8 9 10 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
|
1 2 3 4 5 6 7 8 9 10 11 12 |
|