376. Wiggle Subsequence

Description

Given an integer array nums, return the length of the longest wiggle sequence.

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 fewer than two elements is trivially a wiggle sequence.

• For example, [1, 7, 4, 9, 2, 5] is a wiggle sequence because the differences (6, -3, 5, -7, 3) are alternately positive and negative.

• In contrast, [1, 4, 7, 2, 5] and [1, 7, 4, 5, 5] are not wiggle sequences, the first because its first two differences are positive and the second because its last difference is zero.

A subsequence is obtained by deleting some elements (eventually, also zero) from the original sequence, leaving the remaining elements in their original order.

Constraints

• 1 <= nums.length <= 1000

• 0 <= nums[i] <= 1000

Approach

Links

• GeeksforGeeks

• Leetcode

• ProgramCreek

• YouTube

Examples

Example 1

Input: nums = [1, 7, 4, 9, 2, 5]

Output: 6

Explanation: The entire sequence is a wiggle sequence.

Example 2

Input: nums = [1, 17, 5, 10, 13, 15, 10, 5, 16, 8]

Output: 7

Explanation: There are several subsequences that achieve this length. One is [1, 17, 10, 13, 10, 16, 8].

Example 3

Input: nums = [1, 2, 3, 4, 5, 6, 7, 8, 9]

Output: 2

Solutions

Solution 1

/**
 * Time complexity : O(N)
 * Space complexity : O(1)
 */

class Solution {
    public int wiggleMaxLength(int[] nums) {
        if(nums == null || nums.length == 0) {
            return 0;
        }
        
        int n = nums.length;
        int count = 1;
        
        for(int i = 0, j = 1; j < n; i = j, j++) {
            if(nums[i] < nums[j]) {
                count++;
                while(j+1 < n && nums[j] <= nums[j+1]) {
                    j++;
                }
            } else if(nums[i] > nums[j]) {
                count++;
                while(j+1 < n && nums[j] >= nums[j+1]) {
                    j++;
                }
            }
        }
        
        return count;
    }
}

Follow up