algoadvance

Leetcode 376. Wiggle Subsequence

Problem Statement:

A wiggle sequence is a sequence where the differences between successive numbers strictly alternate between positive and 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 (7-1=6), (4-7=-3), (9-4=5), (2-9=-7), and (5-2=3) are alternately positive and negative. Another example is [1, 4, 7, 2, 5] which is not a wiggle sequence because [4-1=3] and [7-4=3] are not alternating.

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

Example

  1. Input: nums = [1,7,4,9,2,5] Output: 6
  2. Input: nums = [1,17,5,10,13,15,10,5,16,8] Output: 7
  3. Input: nums = [1,2,3,4,5,6,7,8,9] Output: 2

Constraints:

Clarifying Questions:

  1. Q: Are there any constraints on the elements of the array (e.g., non-negative)? A: Yes, the elements range from 0 to 1000.

  2. Q: Should the sequence be strictly alternating or can it have consecutive equal elements? A: The sequence should have strictly alternating differences between consecutive elements.

  3. Q: How should single-element arrays be treated? A: A single-element array is trivially a wiggle sequence, so the length should be 1.

Strategy:

To tackle this problem efficiently, we will use a greedy approach. The idea is to iterate over the array and maintain two variables: up and down.

While iterating through the array:

  1. If the current element is greater than the previous one, it means we have an upward wiggle, so we update up.
  2. If the current element is less than the previous one, it means we have a downward wiggle, so we update down.
  3. If the current element equals the previous one, we move on as it doesn’t contribute to a wiggle sequence.

By the end of the traversal, the maximum of up and down will give us the length of the longest wiggle sequence.

Code:

public class Solution {
    public int wiggleMaxLength(int[] nums) {
        if (nums.length < 2) {
            return nums.length;
        }

        // Initialize up and down
        int up = 1;
        int down = 1;

        // Traverse the array from the second element
        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;
            }
        }

        // The result is the maximum between up and down
        return Math.max(up, down);
    }
}

Time Complexity:

The time complexity of the above code is O(n), where n is the number of elements in the input array nums. This is because we are iterating through the array once.

Feel free to ask any further questions or for additional explanations!

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI