grid47 Exploring patterns and algorithms
Sep 30, 2024
7 min read
Solution to LeetCode 376: Wiggle Subsequence Problem
A wiggle subsequence 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. Given an integer array nums, return the length of the longest wiggle subsequence of nums.
Problem
Approach
Steps
Complexity
Input: You are given an integer array `nums`.
Example: nums = [1, 8, 3, 5, 2, 7]
Constraints:
• 1 <= nums.length <= 1000
• 0 <= nums[i] <= 1000
Output: Return the length of the longest subsequence that forms a wiggle sequence.
Example: Output: 6
Constraints:
Goal: Determine the longest subsequence that alternates between increasing and decreasing differences.
Steps:
• Create two arrays to store the lengths of the wiggle subsequences that end in an upward or downward direction.
• Iterate through the array and for each element, update the subsequence lengths based on the current and previous elements.
• The final answer is the maximum value between the two subsequence lengths at the end of the array.
Goal: The array should have at least one element, and each element must be a non-negative integer.
Steps:
• 1 <= nums.length <= 1000
• 0 <= nums[i] <= 1000
Assumptions:
• The array `nums` is non-empty and contains at least one integer.
• Input: nums = [1, 8, 3, 5, 2, 7]
• Explanation: In this case, the entire sequence is a valid wiggle sequence, and the differences between consecutive elements alternate between positive and negative.
• Input: nums = [10, 15, 12, 9, 18, 7, 11, 13]
• Explanation: In this case, a valid wiggle subsequence can be formed as `[10, 15, 9, 18, 7, 13]`.
Approach: To solve the problem efficiently, we can use dynamic programming.
Observations:
• We can maintain two states: one where the current element is part of an increasing subsequence, and one where it is part of a decreasing subsequence.
• Dynamic programming can be used to store the lengths of subsequences that end in an increasing or decreasing direction.
Steps:
• Create two arrays: `up` and `down` to store the length of the subsequence ending in an increasing or decreasing direction, respectively.
• Initialize the first element as 1 for both `up` and `down`.
• Iterate over the array and update `up` and `down` based on the current element compared to the previous one.
• Return the maximum value between `up` and `down` at the end of the array.
Empty Inputs:
• There are no empty inputs as per the constraints.
Large Inputs:
• The algorithm should efficiently handle inputs up to the size of 1000.
Special Values:
• The input may contain repeated elements, but this does not affect the logic since we are only concerned with the differences between consecutive elements.
Constraints:
• The array should not contain negative numbers or be empty.
This is the function definition for `wiggleMaxLength`, which computes the maximum length of a wiggle subsequence. It takes a vector `nums` as input.
2 : Edge Case Handling
if(nums.size() ==0) return0;
Checks if the input array `nums` is empty. If it is, the function returns 0 as there is no wiggle subsequence possible.
3 : Size Calculation
int n = nums.size();
Calculates the size `n` of the input vector `nums`, which is used to initialize dynamic programming tables.
4 : Dynamic Programming Array Initialization
vector<int> up(n, 0);
Declares a vector `up` of size `n` initialized to zero, which will track the length of the longest subsequence ending in an upward direction.
5 : Dynamic Programming Array Initialization
vector<int> down(n, 0);
Declares a vector `down` of size `n` initialized to zero, which will track the length of the longest subsequence ending in a downward direction.
6 : Initial Condition Setup
up[0] =1;
Sets the base case: the first element of the `nums` array is considered to be part of a wiggle sequence of length 1, starting with an upward direction.
7 : Initial Condition Setup
down[0] =1;
Sets the base case: the first element of the `nums` array is considered to be part of a wiggle sequence of length 1, starting with a downward direction.
8 : Loop Iteration
for(int i =1; i < n; i++) {
This loop iterates through the `nums` array starting from the second element, checking whether each element is part of an increasing or decreasing subsequence.
9 : Condition Check (Decrease)
if(nums[i] < nums[i -1]) {
Checks if the current number `nums[i]` is less than the previous number `nums[i - 1]`. If true, it signifies a downward direction in the wiggle subsequence.
10 : Dynamic Programming Update (Decrease)
down[i] = up[i -1] +1;
Updates the `down[i]` value, representing the longest subsequence ending in a downward direction, considering the previous subsequence's upward direction.
11 : Dynamic Programming Update (Maintain Up)
up[i] = up[i -1];
Maintains the previous `up[i - 1]` value since the current number does not extend the upward sequence.
12 : Condition Check (Increase)
elseif(nums[i] > nums[i -1]) {
Checks if the current number `nums[i]` is greater than the previous number `nums[i - 1]`. If true, it signifies an upward direction in the wiggle subsequence.
13 : Dynamic Programming Update (Increase)
up[i] = down[i -1] +1;
Updates the `up[i]` value, representing the longest subsequence ending in an upward direction, considering the previous subsequence's downward direction.
14 : Dynamic Programming Update (Maintain Down)
down[i] = down[i -1];
Maintains the previous `down[i - 1]` value since the current number does not extend the downward sequence.
15 : Condition Check (No Change)
else {
Handles the case where the current number is equal to the previous number, meaning the sequence does not change direction.
16 : Dynamic Programming Update (No Change)
down[i] = down[i -1];
Maintains the previous `down[i - 1]` value since there is no change in direction.
17 : Dynamic Programming Update (Maintain Up)
up[i] = up[i -1];
Maintains the previous `up[i - 1]` value since there is no change in direction.
18 : Return Result
returnmax(down[n -1], up[n -1]);
Returns the maximum value between `down[n - 1]` and `up[n - 1]`, which represents the length of the longest wiggle subsequence.
Best Case: O(n)
Average Case: O(n)
Worst Case: O(n)
Description: The time complexity is linear because we only need to iterate through the array once.
Best Case: O(n)
Worst Case: O(n)
Description: The space complexity is O(n) due to the storage required for the `up` and `down` arrays.
