Leetcode Wiggle Subsequence problem solution

In this Leetcode Wiggle Subsequence problem solution, 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.

we have given an integer array nums, return the length of the longest wiggle subsequence of nums.

Leetcode Wiggle Subsequence problem solution

Topics we are covering

Problem solution in Python.

class Solution:
    def wiggleMaxLength(self, nums: List[int]) -> int:
        if len(nums) <= 1: return len(nums)
        prev_difference = nums[1] - nums[0]
        count = 2 if prev_difference != 0 else 1 
        for i in range(2, len(nums)):
            current_difference = nums[i] - nums[i-1]
            if (current_difference > 0 and prev_difference <=0 ) or (current_difference < 0 and prev_difference>=  0):
                count += 1
                prev_difference = current_difference
        return count

Problem solution in Java.

class Solution {
    public int wiggleMaxLength(int[] nums) {
        int up = 1;
        int 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(down, up);
    }
}

Problem solution in C++.

class Solution {
public:
    int wiggleMaxLength(vector<int>& nums)
    {
        vector<pair<int, int>> vp;
        if (nums.size() < 2) return 1;
        vp.push_back({nums[0], 1});
        vp.push_back({-nums[0], 1});
        int maxv = 1;
        for (int i = 1; i < nums.size(); i++)
        {
            int dif = nums[i] - nums[i - 1];
            bool inserted = false;

            for (auto& el : vp)
            {
                if ((dif > 0 && el.first < 0) || (dif < 0 && el.first > 0))
                {
                    el.first = dif;
                    el.second++;
                    if (el.second > maxv) maxv = el.second;
                    inserted = true;
                    break;
                }                
                else if (dif == 0) break;
            }
            if (inserted)
            {
               sort(vp.begin(), vp.end(), [](const pair<int,int>& p1, const pair<int,int>& p2) {return p1.second > p2.second;});
            }
            else if (!inserted && dif != 0)
            {
                vp.push_back({nums[0], 1});
            }
        }


        return maxv;      
    }
};

Problem solution in C.

int wiggleMaxLength(int* nums, int numsSize) {
    int i = 0;
    int diff = 0;
    int p_diff = 0;
    int n_diff = 0;
    int no_diff = 0;
    int count = 0;
    if(numsSize == 1)
        return 1;
    if(numsSize == 0)
        return 0;    
    while(i < numsSize - 1)
    {
        diff = nums[i+1] - nums[i];
        
        if(diff > 0)
        {
            n_diff = 0;
            if(p_diff == 0) count++;
            p_diff++;
            i++;
        }
        else if(diff < 0)
        {
            p_diff = 0;
            if(n_diff == 0) count++;
            i++;
            n_diff++;
        }
        else 
        {
            i++;
            no_diff++;
        }
    }
    return count+1;
}

coding problems solutions