[Dynamic Programming] Wiggle Subsequence - Medium

A wiggle subsequence is a sequence of numbers. In this sequence, the differences between the numbers change signs. Our goal with the Wiggle Subsequence problem is to find the longest wiggle subsequence in a list of integers. We can solve this problem well using dynamic programming. This method helps us break the problem into smaller parts. Then, we store the results so we can use them again.

In this article, we will look at how to use dynamic programming to solve the Wiggle Subsequence problem. We will explain the problem clearly. We will also talk about what wiggle subsequences are. We will show code examples in Java, Python, and C++. We will also discuss how to save space while solving this problem. We will compare different methods. We will point out common mistakes. And we will share best practices for writing solutions. Here are the topics we will cover:

Explanation of Dynamic Programming Wiggle Subsequence Problem
Understanding Wiggle Subsequence Concept
Dynamic Programming Approach in Java for Wiggle Subsequence
Dynamic Programming Approach in Python for Wiggle Subsequence
Dynamic Programming Approach in C++ for Wiggle Subsequence
Optimizing Space Complexity for Wiggle Subsequence
Comparing Different Approaches for Wiggle Subsequence
Common Mistakes in Solving Wiggle Subsequence Problem
Best Practices for Implementing Wiggle Subsequence Solutions
Frequently Asked Questions

Understanding the Concept of Wiggle Subsequence

A Wiggle Subsequence is a list of numbers. In this list, the differences between the numbers go up and down. For example, if we have a list ( a_1, a_2, a_3, , a_n ), it is a wiggle sequence if:

( (a_2 - a_1) (a_3 - a_2) < 0 )
( (a_3 - a_2) (a_4 - a_3) < 0 )
And this goes on…

Our goal is to find the longest wiggle subsequence from a given list.

Properties

A wiggle sequence has at least one number if the input list is not empty.
We can find the longest wiggle subsequence using dynamic programming. This means we will keep track of the peaks and valleys in the list.

Example

Let’s look at the list: [1, 7, 4, 9, 2, 5].

The differences are: [6, -3, 5, -7, 3]
The longest wiggle subsequence in this case is [1, 7, 4, 9] and its length is 4.

Approach

Start: First, check if the list has at least two numbers.
Track Differences: We will keep counters for the current length of the wiggle sequence and the previous difference.
Loop: Go through the list and update the counters based on the difference between the numbers.
Update Length: If we find a valid wiggle (a positive or negative difference), we increase the length counter.

This way helps us find the longest wiggle subsequence in a good time, about ( O(n) ).

Code Example (Python)

def wiggleMaxLength(nums):
    if len(nums) < 2:
        return len(nums)
    
    count = 1
    prev_diff = 0
    
    for i in range(1, len(nums)):
        diff = nums[i] - nums[i - 1]
        if (diff > 0 and prev_diff <= 0) or (diff < 0 and prev_diff >= 0):
            count += 1
            prev_diff = diff
            
    return count

# Example usage
nums = [1, 7, 4, 9, 2, 5]
print(wiggleMaxLength(nums))  # Output: 4

This code shows how to find the wiggle subsequence. It is a simple way to understand this concept.

Dynamic Programming Approach in Java for Wiggle Subsequence

We can solve the Wiggle Subsequence problem with dynamic programming in Java. Our goal is to find the longest subsequence where the differences between each element go up and down. Here are the steps to follow:

Define the State: We will use two arrays called up and down.
- up[i] shows the length of the longest wiggle subsequence ending at index i where the difference is positive.
- down[i] shows the length of the longest wiggle subsequence ending at index i where the difference is negative.
Initialization: We set both up[0] and down[0] to 1. This is because the shortest wiggle subsequence that includes the first element has a length of 1.
Recurrence Relation:
- For each element from the second to the last, we compare it with the previous element:
  - If nums[i] > nums[i-1], then:
    - up[i] = down[i-1] + 1
    - down[i] = down[i-1] (it does not change)
  - If nums[i] < nums[i-1], then:
    - down[i] = up[i-1] + 1
    - up[i] = up[i-1] (it does not change)
  - If they are the same, both up[i] and down[i] stay the same.
Final Result: The final answer is the bigger value between the last elements of up and down.

Here is the Java code for this approach:

public class WiggleSubsequence {
    public int wiggleMaxLength(int[] nums) {
        if (nums.length < 2) return nums.length;

        int[] up = new int[nums.length];
        int[] down = new int[nums.length];
        
        up[0] = 1;
        down[0] = 1;

        for (int i = 1; i < nums.length; i++) {
            if (nums[i] > nums[i - 1]) {
                up[i] = down[i - 1] + 1;
                down[i] = down[i - 1];
            } else if (nums[i] < nums[i - 1]) {
                down[i] = up[i - 1] + 1;
                up[i] = up[i - 1];
            } else {
                up[i] = up[i - 1];
                down[i] = down[i - 1];
            }
        }

        return Math.max(up[nums.length - 1], down[nums.length - 1]);
    }

    public static void main(String[] args) {
        WiggleSubsequence ws = new WiggleSubsequence();
        int[] nums = {1, 7, 4, 9, 2, 5};
        System.out.println("Length of Longest Wiggle Subsequence: " + ws.wiggleMaxLength(nums));
    }
}

This code creates a class WiggleSubsequence. It has a method called wiggleMaxLength that uses the dynamic programming approach to find the length of the longest wiggle subsequence. The main method shows how to use this method with an example array.

Using this dynamic programming method, we can find the solution in O(n) time and O(n) space. We can also make it better to O(1) space by only keeping track of the last lengths instead of using the full arrays.

Dynamic Programming Approach in Python for Wiggle Subsequence

We will solve the Wiggle Subsequence problem with dynamic programming in Python. We need to track two states. These states are the length of the longest wiggle subsequence that ends with an upward wiggle and a downward wiggle.

Problem Definition

We have an integer array. Our goal is to find the length of the longest subsequence that goes up and down.

Dynamic Programming Solution

Initialization: We create two arrays called up and down. They are the same length as the input array. Here:
- up[i] shows the length of the longest wiggle subsequence ending at index i with an upward wiggle.
- down[i] shows the length of the longest wiggle subsequence ending at index i with a downward wiggle.
At start, we set both up[0] and down[0] to 1 because a single element is a wiggle subsequence of length 1.
State Transition:
- For each index from 1 to n-1, we compare the current element with the previous one:
  - If nums[i] is greater than nums[i-1]:
    - We update up[i] to be down[i-1] + 1
    - We keep down[i] the same as down[i-1]
  - If nums[i] is less than nums[i-1]:
    - We update down[i] to be up[i-1] + 1
    - We keep up[i] the same as up[i-1]
  - If they are equal, both up[i] and down[i] stay the same as before.
Result: We get the result by finding the maximum value between the last elements of up and down.

Python Code

def wiggleMaxLength(nums):
    if not nums:
        return 0
    
    n = len(nums)
    if n < 2:
        return n
    
    up = [1] * n
    down = [1] * n

    for i in range(1, n):
        if nums[i] > nums[i - 1]:
            up[i] = down[i - 1] + 1
            down[i] = down[i - 1]
        elif nums[i] < nums[i - 1]:
            down[i] = up[i - 1] + 1
            up[i] = up[i - 1]
        else:
            up[i] = up[i - 1]
            down[i] = down[i - 1]

    return max(up[-1], down[-1])

# Example usage
nums = [1, 7, 4, 9, 2, 5]
print(wiggleMaxLength(nums))  # Output: 6

Complexity Analysis

Time Complexity: O(n). Here n is the length of the input array.
Space Complexity: O(n) because of the up and down arrays. We can make this O(1) by using two variables to track the lengths instead of arrays.

This way we compute the longest wiggle subsequence with dynamic programming in Python. For more reading on similar dynamic programming problems, look at Dynamic Programming - Fibonacci Number.

Dynamic Programming Approach in C++ for Wiggle Subsequence

To solve the Wiggle Subsequence problem using Dynamic Programming in C++, we need to keep track of two states. One state is for the length of the longest wiggle subsequence ending with an upward movement. The other state is for a downward movement. We will go through the array and update these states based on the relationship between the numbers next to each other.

C++ Implementation

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int wiggleMaxLength(vector<int>& nums) {
    if (nums.size() < 2) return nums.size();
    
    int up = 1, down = 1; // Start counts for ups and downs

    for (int i = 1; i < nums.size(); ++i) {
        if (nums[i] > nums[i - 1]) {
            up = down + 1; // Update up count
        } else if (nums[i] < nums[i - 1]) {
            down = up + 1; // Update down count
        }
    }
    
    return max(up, down); // Return the biggest wiggle length
}

int main() {
    vector<int> nums = {1, 7, 4, 9, 2, 5};
    cout << "Length of longest wiggle subsequence: " << wiggleMaxLength(nums) << endl;
    return 0;
}

Explanation of the Code

The function wiggleMaxLength takes a vector of integers as input.
It starts two variables, up and down, to keep track of the lengths of the longest wiggle subsequence. One is for the upward and other is for downward movement.
The loop goes through the nums array starting from the second element. It checks if the current number is bigger or smaller than the previous one. Then it updates up or down.
Finally, we return the maximum of up and down. This tells us the length of the longest wiggle subsequence.

Complexity Analysis

Time Complexity: O(n), where n is the size of the input array.
Space Complexity: O(1), because we use just a fixed amount of space.

This way helps us find the longest wiggle subsequence in an efficient way. For more reading on similar dynamic programming problems, we can check articles like Dynamic Programming - Longest Increasing Subsequence or Dynamic Programming - Maximum Subarray.

Optimizing Space Complexity for Wiggle Subsequence

We can make the space needed for the Wiggle Subsequence problem smaller. Instead of using O(n) space, we can change it to O(1). We do this by keeping only the important variables that track the lengths of the wiggle subsequence. We do not need a full dynamic programming array. We just track the lengths of the last two wiggle subsequences while we go through the array.

Code Example

Here is a space-saving way to do this in Java, Python, and C++.

Java Implementation:

public class WiggleSubsequence {
    public int wiggleMaxLength(int[] nums) {
        if (nums.length < 2) return nums.length;

        int up = 1, down = 1;

        for (int i = 1; i < nums.length; i++) {
            if (nums[i] > nums[i - 1]) {
                up = down + 1;
            } else if (nums[i] < nums[i - 1]) {
                down = up + 1;
            }
        }

        return Math.max(up, down);
    }
}

Python Implementation:

def wiggleMaxLength(nums):
    if len(nums) < 2:
        return len(nums)
    
    up, down = 1, 1

    for i in range(1, len(nums)):
        if nums[i] > nums[i - 1]:
            up = down + 1
        elif nums[i] < nums[i - 1]:
            down = up + 1

    return max(up, down)

C++ Implementation:

class Solution {
public:
    int wiggleMaxLength(vector<int>& nums) {
        if (nums.size() < 2) return nums.size();

        int up = 1, down = 1;

        for (int i = 1; i < nums.size(); i++) {
            if (nums[i] > nums[i - 1]) {
                up = down + 1;
            } else if (nums[i] < nums[i - 1]) {
                down = up + 1;
            }
        }

        return max(up, down);
    }
};

Explanation

Variables Used:
- up: This keeps the length of the longest wiggle subsequence that ends with a “up” move.
- down: This keeps the length of the longest wiggle subsequence that ends with a “down” move.
Time Complexity: O(n), where n is the size of the input array.
Space Complexity: O(1), because we use only a constant amount of space.

By using this better way, we lower the space needed a lot. We keep the time efficiency the same. This makes our method good for bigger input sizes.

Comparing Different Approaches for Wiggle Subsequence

When we look at the Wiggle Subsequence problem, we can use different methods. Each one has its own pros and cons. The main methods we can think of are Dynamic Programming, Greedy, and a simple brute-force method. Here is a comparison of these methods based on how complex they are, how fast they work, and how easy they are to use.

1. Dynamic Programming Approach

Time Complexity: O(n) where n is the length of the input array.
Space Complexity: O(n) but can be improved to O(1).
Description: This method builds a DP table. It tracks the longest wiggle subsequence for each index. We keep two states. One for when the last wiggle goes up. The other for when it goes down.

Java Implementation:

public int wiggleMaxLength(int[] nums) {
    if (nums.length < 2) return nums.length;

    int up = 1, down = 1;

    for (int i = 1; i < nums.length; i++) {
        if (nums[i] > nums[i - 1]) {
            up = down + 1;
        } else if (nums[i] < nums[i - 1]) {
            down = up + 1;
        }
    }

    return Math.max(up, down);
}

2. Greedy Approach

Time Complexity: O(n).
Space Complexity: O(1).
Description: This method goes through the array and counts wiggles. It compares each pair of neighboring elements. We increase the count when we see a wiggle, which means a change in direction.

Python Implementation:

def wiggleMaxLength(nums):
    if len(nums) < 2:
        return len(nums)

    count = 1
    for i in range(1, len(nums)):
        if (nums[i] > nums[i - 1] and (i == 1 or nums[i - 1] <= nums[i - 2])) or \
           (nums[i] < nums[i - 1] and (i == 1 or nums[i - 1] >= nums[i - 2])):
            count += 1

    return count

3. Brute-Force Approach

Time Complexity: O(2^n) - exponential.
Space Complexity: O(n).
Description: This method makes all possible subsequences. It checks each one to see if it is a wiggle. This method is usually not useful for bigger inputs because it is slow.

C++ Implementation:

int wiggleMaxLength(vector<int>& nums) {
    if (nums.size() < 2) return nums.size();
    
    int count = 1;
    for (int i = 1; i < nums.size(); ++i) {
        if ((nums[i] > nums[i - 1] && (i == 1 || nums[i - 1] <= nums[i - 2])) ||
            (nums[i] < nums[i - 1] && (i == 1 || nums[i - 1] >= nums[i - 2]))) {
            count++;
        }
    }
    return count;
}

Conclusion of Approaches

The Dynamic Programming method is good but takes more space.
The Greedy method is fast and uses less space, but we need to be careful with edge cases.
The Brute-Force method is not a good choice for real use because it is too slow.

Choosing the right method depends on what we need for the problem. For most cases, we prefer the Greedy or Dynamic Programming methods because they are more efficient.

Common Mistakes in Solving Wiggle Subsequence Problem

When we solve the Wiggle Subsequence problem with dynamic programming, we can make some common mistakes. Knowing these mistakes can help us to create a better solution.

Incorrect Understanding of Wiggle Sequence:
- One mistake is not understanding what a “wiggle” is. It should switch between increasing and decreasing. We need to spot these changes when we go through the sequence.
Mismanaging State Variables:
- Some of us might not manage the state variables well. These variables track the number of wiggles. We should keep separate counts for wiggles that end with an upward or downward change.
Ignoring Edge Cases:
- We should not forget edge cases like sequences that are 0 or 1 in length. If we do, we can get wrong answers. We need to handle these cases clearly by returning 0 or 1.
Improper Initialization:
- It is very important to initialize dynamic programming arrays correctly. We must set the first element based on whether it is part of a wiggle sequence.
Inefficient Space Complexity:
- Some solutions may use too much memory. It is better to use a constant space solution when we can, using simple variables instead of big arrays.
Looping Over Unnecessary Elements:
- We should not check all pairs of elements. We need to look for transitions directly. This will make our time complexity much better.
Failure to Update States Properly:
- We must update our states correctly after checking each transition. If we do not, we can get the wrong count of the wiggle subsequence.
Not Considering Non-Adjacent Elements:
- The wiggle subsequence can skip some elements. We must make sure our logic allows for non-adjacent elements to cause a wiggle.
Overcomplicating the Logic:
- Some solutions get too complicated with too many condition checks. We should aim for a simple approach that meets the problem needs.
Neglecting to Optimize the Final Count:

After we process the array, we need to return the maximum count of the wiggle subsequence. This is usually found in the last element of our state variable.

By paying attention to these common mistakes, we can create a stronger and more efficient solution for the Wiggle Subsequence problem with dynamic programming. For more reading on dynamic programming techniques, we can look at related articles like Dynamic Programming: Fibonacci Number and Dynamic Programming: Longest Increasing Subsequence.

Best Practices for Implementing Wiggle Subsequence Solutions

When we implement solutions for the Wiggle Subsequence problem using dynamic programming, we need to follow some best practices. This helps us make our code efficient, clear, and easy to maintain.

Understand the Problem Statement: We must have a clear idea of what a wiggle sequence is. A wiggle sequence is where the differences between consecutive numbers switch between positive and negative.
Optimal Substructure: We can build the solution from the solutions of smaller parts. For the Wiggle Subsequence, we track two things:
- up[i]: the length of the longest wiggle subsequence ending at index i with a positive difference.
- down[i]: the length of the longest wiggle subsequence ending at index i with a negative difference.
Iterative Approach: We should use an iterative way instead of a recursive one. This helps us avoid problems like stack overflow and makes our code faster. It also keeps our data flow clear.
Space Optimization: Instead of using arrays for up and down, we can just use two variables. This cuts down space usage from O(n) to O(1).
Edge Cases: We need to think about edge cases like:
- Arrays with less than two elements (no wiggle sequence is possible).
- Arrays where all elements are the same (the longest wiggle subsequence is 1).
Code Readability: We should make sure our code is easy to read. We can do this by adding comments and using clear variable names. It is also good to keep formatting the same throughout the code.

Example Code in Python

def wiggleMaxLength(nums):
    if len(nums) < 2:
        return len(nums)

    up = down = 1  # Start counters for up and down

    for i in range(1, len(nums)):
        if nums[i] > nums[i - 1]:
            up = down + 1
        elif nums[i] < nums[i - 1]:
            down = up + 1

    return max(up, down)

# Example usage
nums = [1, 7, 4, 9, 2, 5]
print(wiggleMaxLength(nums))  # Output: 6

Testing: We should write good unit tests to check many situations, including edge cases. This helps us make sure our code works correctly.
Performance Analysis: We need to check the time and space usage of our solution. The best solution should run in O(n) time and O(1) space. This makes it work well for big inputs.
Documentation: We need to write documentation for our code and give examples. This helps others understand what we did quickly.

By following these best practices, we can make a strong and efficient solution for the Wiggle Subsequence problem. This way, our code will be effective and easy to maintain. For more reading on dynamic programming ideas, we can look at resources like Dynamic Programming: Fibonacci Number and Dynamic Programming: Longest Increasing Subsequence.

Frequently Asked Questions

What is a wiggle subsequence in dynamic programming?

A wiggle subsequence is a kind of sequence. In this sequence, the differences between the numbers change direction. So, we can say it goes up and down. For a sequence to be a wiggle subsequence, it needs to show this up and down pattern. The dynamic programming method helps us find the longest wiggle subsequence from a given list. It does this by keeping track of increases and decreases.

How do I implement a dynamic programming solution for the wiggle subsequence problem?

To make a dynamic programming solution for the wiggle subsequence problem, we can use two variables. One variable will hold the longest wiggle subsequence that ends with an upward movement. The other will hold the one that ends with a downward movement. We will go through the input array and update these values based on how the current number relates to the previous one. This way, we can find the longest subsequence in O(n) time.

What is the time complexity of the wiggle subsequence dynamic programming solution?

The time complexity of the dynamic programming solution for the wiggle subsequence problem is O(n). Here, n is the length of the input array. We get this efficiency by making one pass through the array. While we do this, we update the counts of the longest wiggle subsequence based on the increases and decreases.

How can I optimize space complexity for the wiggle subsequence solution?

To make the space complexity better in the wiggle subsequence solution, we can use just two variables instead of using separate arrays. By tracking the lengths of the longest wiggle subsequences that end in up and down states, we can achieve a space complexity of O(1). This is the best we can do for this problem.

What are common mistakes when solving the wiggle subsequence problem?

Some common mistakes when solving the wiggle subsequence problem are misunderstanding what wiggle subsequences are, not managing the up and down state changes well, and not considering special cases. For example, we need to think about sequences with no elements or where all elements are the same. It is very important to track the alternating pattern correctly to avoid these mistakes.

For more reading about similar dynamic programming problems, you can check out articles on Dynamic Programming: Fibonacci Number and Dynamic Programming: Longest Increasing Subsequence.