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.