Nayan PahujaHey Guys! Nayan here and this is the 24th day of the 100-DAY challenge. If you are reading this for the first time , I learn and solve some questions throughout the day and post them here.
Let's get right to the problem.
Problem: Wiggle Subsequence
A wiggle sequence is a sequence where the differences between successive numbers strictly alternate between positive and negative. The first difference (if one exists) may be either positive or negative. A sequence with one element and a sequence with two non-equal elements are trivially wiggle sequences.
- For example, [1, 7, 4, 9, 2, 5] is a wiggle sequence because the differences (6, -3, 5, -7, 3) alternate between positive and negative.
- In contrast, [1, 4, 7, 2, 5] and [1, 7, 4, 5, 5] are not wiggle sequences. The first is not because its first two differences are positive, and the second is not because its last difference is zero.
- A subsequence is obtained by deleting some elements (possibly zero) from the original sequence, leaving the remaining elements in their original order.
Given an integer array nums, return the length of the longest wiggle subsequence of nums.
Example:
Input: nums = [1,7,4,9,2,5]
Output: 6
Explanation: The entire sequence is a wiggle sequence with differences (6, -3, 5, -7, 3).
Intuition:
The question is pretty straightforward. Although a common mistake one can do is return the length of differences instead of the wiggle subsequence.
Let's start with observations and then optimize the solution further. We have done plenty of subsequence problems and our mind pretty much recognizes the pattern once again of picking the element and notPicking the element.
So we do exactly that using recursion and add memoization DP to it to optimize the exponential time complexity.
Approach:
- We will start from the last index and stop once we go to last index as we can't calculate it's difference. Hence our base case in this case is if(index <= 0). So we return 0.
- If we decide not to pick the element we just simply move forward in our traversion.
- Now observe that we need to maintain two changing parameters. One is the index and second is the lastSign of the previous difference. Hence we must apply our pick exactly those conditions. Since 0 is neither positive nor negative we return false anytime we encounter difference to be 0.
Let's code it up.
Code:
class Solution {
public:
int helper(int idx, vector<int>& nums, int n, int lastSign, vector<vector<int>> &dp){
if(idx <= 0){
return 0;
}
int notPick = 0 + helper(idx-1,nums,n, lastSign,dp);
int pick = 0;
if(dp[idx][lastSign] != -1) return dp[idx][lastSign];
if(nums[idx]- nums[idx-1] < 0 && lastSign == 1 || nums[idx]-nums[idx-1] < 0 && lastSign == 2){
pick = 1 + helper(idx-1,nums,n,0,dp);
}
else if(nums[idx]- nums[idx-1] > 0 && lastSign == 0 || nums[idx]-nums[idx-1] > 0 && lastSign == 2){
pick = 1 + helper(idx-1,nums, n, 1,dp);
}
return dp[idx][lastSign] = max(notPick, pick);
}
int wiggleMaxLength(vector<int>& nums) {
int n = nums.size();
int lastSign;
vector<vector<int>> dp(n, vector<int>(3,-1));
return helper(n-1,nums,n,2,dp)+1;
}
};
Time Complexity: O(3*N)
Space Complexity: O (N*3) + O(N)
We can further optimize this using tabulation approach.
- We will increment our index in the above approach such that we don't go out of bounds for tabulation since we can have only 0 based indexing.
- We also establish the base cases and store them but we don't need to as we have already initialized our array as 0. Rest our code follows the same logic.
Code:
int wiggleMaxLength(vector<int>& nums) {
int n = nums.size();
int lastSign;
vector<vector<int>> dp(n+1, vector<int>(3,0));
for(int sign = 0; sign <=2; sign++){
dp[0][sign] = 0;
dp[1][sign] = 0;
}
for(int idx = 2; idx < n+1; idx++){
for(int sign = 2; sign >= 0; sign--){
int notPick = 0 + dp[idx-1][sign];
int pick = 0;
if(nums[idx-1]- nums[idx-2] < 0 && sign == 1 || nums[idx-1]-nums[idx-2] < 0 && sign == 2){
pick = 1 + dp[idx-1][0];
}
else if(nums[idx-1]- nums[idx-2] > 0 && sign == 0 || nums[idx-1]-nums[idx-2] > 0 && sign == 2){
pick = 1 + dp[idx-1][1];
}
dp[idx][sign] = max(pick,notPick);
}
}
return dp[n][2] + 1;
}
Time Complexity: O(3*N).
Space Complexity: O (N*3). Extra space due to recursion stack removed
We can clearly see here that our array depends on the lastSign row rather than the full array and hence we can space optimize it further even more.
Code:
int wiggleMaxLength(vector<int>& nums) {
int n = nums.size();
int lastSign;
vector<int> prev(3,0);
vector<int> cur(3,0);
for(int idx = 2; idx < n+1; idx++){
for(int sign = 2; sign >= 0; sign--){
int notPick = prev[sign];
int pick = 0;
if(nums[idx-1]- nums[idx-2] < 0 && sign == 1 || nums[idx-1]-nums[idx-2] < 0 && sign == 2){
pick = 1 + prev[0];
}
else if(nums[idx-1]- nums[idx-2] > 0 && sign == 0 || nums[idx-1]-nums[idx-2] > 0 && sign == 2){
pick = 1 + prev[1];
}
cur[sign] = max(pick,notPick);
}
prev = cur;
}
return prev[2] + 1;
}
Time Complexity: O(3*N).
Space Complexity: O (1). Extra space removed.
There is a O(N) approach to this question using greedy approach.
We maintain two pointers.
- Check if the length of the input list nums is less than 2. If yes, return the length of nums. This is because a sequence with one element and a sequence with two non-equal elements are trivially wiggle sequences. If the diff is positive and our lastSign was not positive or the opposite for negative and lastSign was not negative we increment maxLen and update lastSign.
Code:
int wiggleMaxLength(vector<int>& nums) {
int n = nums.size();
if(n < 2) return n;
int maxLen = 1;
int lastSign;
for(int i = 1; i < n; i++){
int diff = nums[i]-nums[i-1];
if(diff > 0 && lastSign != 1 || diff < 0 && lastSign != -1){
maxLen++;
if(diff > 0){
lastSign = 1;
}
else
{
lastSign = -1;
}
}
}
return maxLen;
}
Time Complexity: O(N)
Space Complexity: O(1)
