Sponsored
Sponsored
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.
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.
1def validPartition(nums):
2 n = len(nums)
3 if n < 2:
4 return False
5
6 dp = [False] * (n + 1)
7 dp[0] = True
8 dp[1] = nums[0] == nums[1]
9
10 for i in range(2, n):
11 if nums[i] == nums[i-1] and dp[i-1]:
12 dp[i+1] = True
13 if nums[i] == nums[i-1] == nums[i-2] and dp[i-2]:
14 dp[i+1] = True
15 if nums[i] - 1 == nums[i-1] == nums[i-2] - 1 and dp[i-2]:
16 dp[i+1] = True
17
18 return dp[n]
19This code uses a dynamic programming approach to iterate through the list, checking and updating the validity of partitions.
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.
Time Complexity: O(n)
Space Complexity: O(1)
1#include <vector>
2using namespace std;
bool validPartition(vector<int>& nums) {
int n = nums.size();
int i = 0;
while (i < n) {
if (i < n - 1 && nums[i] == nums[i + 1]) {
i += 2;
} else if (i < n - 2 && nums[i] == nums[i + 1] && nums[i + 1] == nums[i + 2]) {
i += 3;
} else if (i < n - 2 && nums[i + 1] - nums[i] == 1 && nums[i + 2] - nums[i + 1] == 1) {
i += 3;
} else {
return false;
}
}
return true;
}
The C++ solution uses a greedy methodology to check for valid subarrays iteratively.