Wiggle Subsequence

Medium

Asked by:

11 views

Topics:

ArraysGreedy AlgorithmsDynamic Programming

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.

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

Example 1:

Input: nums = [1,7,4,9,2,5]
Output: 6
Explanation: The entire sequence is a wiggle sequence with differences (6, -3, 5, -7, 3).

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] with differences (16, -7, 3, -3, 6, -8).

Example 3:

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

Constraints:

1 <= nums.length <= 1000
0 <= nums[i] <= 1000

Follow up: Could you solve this in O(n) time?

Try coding it in LeetCode

Wiggle Subsequence

Medium

Asked by:

11 views

Topics:

ArraysGreedy AlgorithmsDynamic Programming

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.

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

Example 1:

Input: nums = [1,7,4,9,2,5]
Output: 6
Explanation: The entire sequence is a wiggle sequence with differences (6, -3, 5, -7, 3).

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] with differences (16, -7, 3, -3, 6, -8).

Example 3:

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

Constraints:

1 <= nums.length <= 1000
0 <= nums[i] <= 1000

Follow up: Could you solve this in O(n) time?

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the range of values within the input array? Can I expect negative numbers, zeros, or only positive integers?
Can the input array be empty or null? If so, what should I return in those cases?
Are duplicate numbers considered a 'wiggle'? For example, is `[1, 2, 2, 3]` a wiggle subsequence of length 3 or 2?
If there are multiple valid wiggle subsequences of the same maximum length, is any one of them acceptable?
What is the expected data type of the returned result? Should I return the length of the wiggle sequence, or the sequence itself?

Brute Force Solution

Approach

The wiggle subsequence problem asks us to find the longest sequence within a given sequence where the differences between consecutive numbers alternate between positive and negative. The brute force approach involves checking every possible subsequence to see if it wiggles and then picking the longest one.

Here's how the algorithm would work step-by-step:

Consider all possible subsequences of the original sequence. A subsequence is formed by picking some numbers from the original sequence, keeping them in the same order, but potentially skipping some.
For each subsequence we create, check if it's a wiggle subsequence. This means looking at the differences between each pair of consecutive numbers in the subsequence.
To be a wiggle subsequence, these differences must alternate in sign - positive, negative, positive, negative, and so on, or negative, positive, negative, positive, and so on.
If a subsequence is a wiggle subsequence, keep track of its length.
After checking all possible subsequences, find the wiggle subsequence with the greatest length.
Return that length as the answer.

Code Implementation

def wiggle_subsequence_brute_force(numbers):
    maximum_length = 0

    def is_wiggle(subsequence):
        if len(subsequence) < 2:
            return True
        
        sign = 0
        for i in range(1, len(subsequence)):
            difference = subsequence[i] - subsequence[i - 1]
            
            if difference == 0:
                return False
            
            current_sign = 1 if difference > 0 else -1
            
            if sign == 0:
                sign = current_sign
            elif sign == current_sign:
                return False
            else:
                sign = current_sign
                
        return True

    def find_subsequences(index, current_subsequence):
        nonlocal maximum_length

        # If we reach the end of the original sequence, check the subsequence.
        if index == len(numbers):
            if is_wiggle(current_subsequence):
                maximum_length = max(maximum_length, len(current_subsequence))
            return

        # Explore the possibility of including the current number in the subsequence.
        find_subsequences(index + 1, current_subsequence + [numbers[index]])

        # Explore the possibility of excluding the current number.
        find_subsequences(index + 1, current_subsequence)

    # Start the recursive search for wiggle subsequences.
    find_subsequences(0, [])

    return maximum_length

Big(O) Analysis

Time Complexity

O(2^n * n) – The brute force approach considers all possible subsequences of the input sequence of size n. There are 2^n possible subsequences. For each subsequence, we need to verify if it's a wiggle sequence, which involves iterating through the subsequence in the worst case (size of n). Thus the total time complexity is dominated by generating all subsequences and verifying each one, resulting in O(2^n * n).

Space Complexity

O(1) – The brute force approach, as described, iterates through all possible subsequences and checks if they are wiggle subsequences. No explicit auxiliary data structures like arrays, hash maps, or sets are mentioned to store intermediate subsequences. The length of the longest wiggle subsequence found is also tracked using a single variable. Thus the space usage remains constant, independent of the size of the input sequence.

Optimal Solution

Approach

The goal is to find the longest sequence where the differences between adjacent numbers alternate between positive and negative. We can find this sequence by keeping track of the last positive and negative 'peaks' we've seen and extending the sequence whenever we find a number that forms a new peak.

Here's how the algorithm would work step-by-step:

Start by assuming the first number is part of the wiggle sequence.
Go through the rest of the numbers one by one.
If the current number is bigger than the last number in our increasing wiggle sequence, it extends the increasing wiggle sequence.
If the current number is smaller than the last number in our decreasing wiggle sequence, it extends the decreasing wiggle sequence.
If the current number doesn't extend either sequence, it's not useful, so we ignore it.
The length of the wiggle sequence is the number of times we've extended either an increasing or decreasing sequence.

Code Implementation

def wiggle_subsequence(numbers):
    if not numbers:
        return 0

    sequence_length = 1
    up_peak = numbers[0]
    down_peak = numbers[0]

    for index in range(1, len(numbers)):
        current_number = numbers[index]

        # Extend increasing seq.
        if current_number > up_peak:
            sequence_length += 1
            down_peak = current_number

        # Extend decreasing seq.
        elif current_number < down_peak:
            sequence_length += 1
            up_peak = current_number

    return sequence_length

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the input array of size n exactly once. During this single pass, it performs constant-time operations to compare each element with the previously tracked increasing and decreasing peaks. No nested loops or recursive calls are involved; the number of operations grows linearly with the input size n. Therefore, the time complexity is O(n).

Space Complexity

O(1) – The algorithm does not use any auxiliary data structures that scale with the input size, N (the number of elements in the input array). It only keeps track of the last number in the increasing and decreasing wiggle subsequences implicitly by comparing the current number to the previous one, effectively storing at most a couple of values representing these peaks. Therefore, the space required remains constant regardless of the size of the input array. This results in a space complexity of O(1).

Edge Cases

Case	How to Handle
Empty or null input array	Return 0, as an empty array has no wiggle subsequence.
Array with one element	Return 1, as a single element forms a wiggle subsequence of length 1.
Array with two identical elements	Return 1, as two identical elements do not form a wiggle subsequence.
Array with two distinct elements	Return 2, as any two distinct elements form a wiggle subsequence.
Array with all identical elements	Return 1, as all identical elements do not form any wiggle.
Array with strictly increasing or decreasing elements	The algorithm should correctly identify the first increase or decrease and count the elements accordingly.
Array with alternating positive and negative differences	The algorithm should correctly count each alternating change as part of the wiggle subsequence.
Large input array with potential integer overflow in difference calculation	Use a data type that can accommodate larger differences (e.g., long) if necessary.