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.
1#include <vector>
2using namespace std;
3
4bool validPartition(vector<int>& nums) {
5 int n = nums.size();
6 vector<bool> dp(n + 1, false);
7 dp[0] = true;
8 dp[1] = nums[0] == nums[1];
9
10 for (int i = 2; i < n; ++i) {
11 if (nums[i] == nums[i-1] && dp[i-1]) dp[i+1] = true;
12 if (nums[i] == nums[i-1] && nums[i-1] == nums[i-2] && dp[i-2]) dp[i+1] = true;
13 if (nums[i] - 1 == nums[i-1] && nums[i-1] - 1 == nums[i-2] && dp[i-2]) dp[i+1] = true;
14 }
15 return dp[n];
16}
17The solution uses similar logic to the Python solution, employing a vector to track 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)
1defThis solution greedily attempts to find and skip valid subarrays during a single pass through the array, which can be efficient but is less robust than dynamic programming.