Leetcode 376. Wiggle Subsequence
Problem Explanation
The problem is about finding the longest sub-sequence that is a wiggle sequence from the given sequence of integers. A wiggle sequence is a sequence where the difference between the successive numbers strictly alternate between positive and negative. For example,
1Inputs: [1, 7, 4, 9, 2, 5] 2Outputs: 6
(Here, the differences are [6, -3, 5, -7, 3], which alternate between positive and negative.)
In the problem, you need to return the length of the longest subsequence that is a wiggle sequence. A subsequence is a subset of the original sequence where elements are in the same relative order. The problem also asks if it is possible to find this in O(n) time complexity.
For example, given this input sequence:
1[1,17,5,10,13,15,10,5,16,8]
The longest wiggle subsequence has length 7, with possible subsequences being [1,17,5,10,13,15,10] or [1,17,10,13,10,5,16].
Solution Approach
This problem can be solved by using dynamic programming. Two pointers, increasing and decreasing are used to keep track of the length of the most recent longest increasing and decreasing subsequences respectively.
As you iterate through the input sequence, you compare each pair of numbers. If the current number is greater than the previous one, it means the subsequence is increasing, so you update the length of the increasing subsequence (increasing = decreasing + 1). If the current number is less than the previous one, the subsequence is decreasing, so you update the length of decreasing subsequence (decreasing = increasing + 1).
Eventually, you return the maximum of the increasing and decreasing lengths, which is the length of the longest wiggle subsequence.
Python Solution:
1 2python 3class Solution: 4 def wiggleMaxLength(self, nums): 5 if not nums: 6 return 0 7 8 increasing = 1 9 decreasing = 1 10 11 for i in range(1, len(nums)): 12 # if current number is greater than previous 13 if nums[i] > nums[i - 1]: 14 increasing = decreasing + 1 15 # if current number is less than previous 16 elif nums[i] < nums[i - 1]: 17 decreasing = increasing + 1 18 19 return max(increasing, decreasing)
Java Solution:
1 2java 3public class Solution { 4 public int wiggleMaxLength(int[] nums) { 5 if (nums.length == 0) { 6 return 0; 7 } 8 9 int increasing = 1; 10 int decreasing = 1; 11 12 for (int i = 1; i < nums.length; i++) { 13 if (nums[i] > nums[i - 1]) { 14 increasing = decreasing + 1; 15 } else if (nums[i] < nums[i - 1]) { 16 decreasing = increasing + 1; 17 } 18 } 19 20 return Math.max(increasing, decreasing); 21 } 22}
Javascript Solution:
1 2javascript 3var wiggleMaxLength = function(nums) { 4 if(nums.length==0) return 0; 5 let increasing = 1; 6 let decreasing = 1; 7 for(let i=1; i<nums.length; i++) { 8 if(nums[i] > nums[i-1]) 9 increasing = decreasing + 1; 10 else if(nums[i] < nums[i-1]) 11 decreasing = increasing + 1; 12 } 13 return Math.max(increasing, decreasing); 14};
C++ Solution:
1 2c++ 3class Solution { 4public: 5 int wiggleMaxLength(vector<int>& nums) { 6 if(nums.empty()) return 0; 7 int increasing = 1; 8 int decreasing = 1; 9 for(int i=1; i<nums.size(); i++) { 10 if(nums[i] > nums[i-1]) 11 increasing = decreasing + 1; 12 else if(nums[i] < nums[i-1]) 13 decreasing = increasing + 1; 14 } 15 return max(increasing, decreasing); 16 } 17};
C# Solution:
1 2csharp 3public class Solution { 4 public int WiggleMaxLength(int[] nums) { 5 if(nums.Length==0) return 0; 6 int increasing = 1; 7 int decreasing = 1; 8 for (int i = 1; i < nums.Length; i++) { 9 if (nums[i] > nums[i - 1]) 10 increasing = decreasing + 1; 11 else if (nums[i] < nums[i - 1]) 12 decreasing = increasing + 1; 13 } 14 return Math.Max(increasing, decreasing); 15 } 16}
Swift Solution:
1 2swift 3class Solution { 4 func wiggleMaxLength(_ nums: [Int]) -> Int { 5 if nums.count == 0 { 6 return 0 7 } 8 9 var increasing = 1 10 var decreasing = 1 11 12 for i in 1..<nums.count { 13 if nums[i] > nums[i - 1] { 14 increasing = decreasing + 1 15 } else if nums[i] < nums[i - 1] { 16 decreasing = increasing + 1 17 } 18 } 19 20 return max(increasing, decreasing) 21 } 22}
Scala Solution:
1
2scala
3object Solution {
4 def wiggleMaxLength(nums: Array[Int]): Int = {
5 if(nums.isEmpty) return 0
6 var increasing = 1
7 var decreasing = 1
8 for (i <- 1 until nums.length) {
9 if (nums(i) > nums(i - 1))
10 increasing = decreasing + 1
11 else if (nums(i) < nums(i - 1))
12 decreasing = increasing + 1
13 }
14 increasing max decreasing
15 }
16}
PHP Solution:
1
2php
3class Solution {
4
5 function wiggleMaxLength($nums) {
6 if(count($nums)==0) return 0;
7 $increasing = 1;
8 $decreasing = 1;
9
10 for($i=1; $i<count($nums); $i++) {
11 if ($nums[$i] > $nums[$i - 1]) {
12 $increasing = $decreasing + 1;
13 } else if($nums[$i] < $nums[$i - 1]) {
14 $decreasing = $increasing + 1;
15 }
16 }
17
18 return max($increasing, $decreasing);
19 }
20}
All solutions presented here follow Dynamic Programming approach with time complexity of O(n) where 'n' is the length of the input sequence. It assumes all sequences not only have at least one element, but also contain integers. For empty or non-integer sequences, you would need to add relevant condition checks. In all of the codes, no additional data structures are used so the space complexity is O(1). The maximum length of the wiggle subsequence is computed and returned. The solutions are reliable, effective and solve the problem as expected.
Got a question?ย Ask the Teaching Assistantย anything you don't understand.
Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.