Wiggle Subsequence

📋

Problem

Imagine tracking stock prices that fluctuate daily and wanting to find the longest sequence of ups and downs to maximize trading opportunities.

Given an integer array nums, return the length of the longest wiggle subsequence. A wiggle sequence is one 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 subsequence is obtained by deleting some elements (possibly zero) from the original sequence, leaving the remaining elements in their original order.

1 ≤ nums.length ≤ 10^5-10^9 ≤ nums[i] ≤ 10^9

Edge cases: Single element array → output 1All elements equal → output 1Strictly increasing array → output 2

</>

IDE

def wiggleMaxLength(nums: list[int]) -> int:public int wiggleMaxLength(int[] nums)int wiggleMaxLength(vector<int>& nums)function wiggleMaxLength(nums)

def wiggleMaxLength(nums):
    # Write your solution here
    pass

class Solution {
    public int wiggleMaxLength(int[] nums) {
        // Write your solution here
        return 0;
    }
}

#include <vector>
using namespace std;

int wiggleMaxLength(vector<int>& nums) {
    // Write your solution here
    return 0;
}

function wiggleMaxLength(nums) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: 0Returning 0 for single element or empty input instead of 1 or 0 respectively.✅ Add explicit base case: if len(nums) == 0 return 0; if len(nums) == 1 return 1.

Wrong: Length equal to input size for all equal elementsCounting zero differences as wiggle steps, inflating count.✅ Skip zero differences when updating direction and counting wiggle length.

Wrong: Length equal to input size for strictly increasing or decreasing arraysCounting all elements instead of only first and last for monotonic sequences.✅ Count only first element and first difference sign change; ignore continuous same sign differences.

Wrong: Underestimated length due to greedy trapCounting only first peak and valley, missing intermediate wiggles.✅ Scan entire array for all sign changes in differences and count each valid wiggle.

Wrong: TLE on large inputsUsing brute force or DP with exponential or quadratic complexity.✅ Implement O(n) greedy peak-valley counting approach.

✓

Test Cases

Focus on handling minimal and boundary inputs correctly.

Think about common greedy pitfalls and subsequence constraints.

Optimize your solution to linear time to handle large inputs efficiently.

t1_01basic

Input{"nums":[1,7,4,9,2,5]}

Expected6

⏱ Performance - must finish in 2000ms

The entire sequence is a wiggle sequence: differences alternate +6, -3, +5, -7, +3.

💡 Consider the sign changes between consecutive differences.

💡 Track whether the current difference is positive or negative to decide inclusion.

💡 Use a greedy approach counting peaks and valleys to find max length.

Why it failed: Incorrect output means sign alternation logic is flawed; fix by ensuring difference signs strictly alternate and count initial element.

✓ Correctly identifies the full wiggle subsequence length.

t1_02basic

Input{"nums":[1,17,5,10,13,15,10,5,16,8]}

Expected7

⏱ Performance - must finish in 2000ms

Longest wiggle subsequence length is 7, e.g. [1,17,10,13,10,16,8] with alternating differences.

💡 Check differences between consecutive elements and their signs.

💡 Use a greedy method to count peaks and valleys, ignoring equal or same sign differences.

💡 Increment count only when difference sign flips compared to previous difference.

Why it failed: Output too low means missing sign flips; fix by updating direction only when difference sign changes and ignoring zero differences.

✓ Correctly counts all alternating peaks and valleys.

t2_01edge

Input{"nums":[5]}

Expected1

⏱ Performance - must finish in 2000ms

Single element array always has wiggle subsequence length 1.

💡 Consider the base case of a single element sequence.

💡 The wiggle subsequence length cannot be less than 1 if array is non-empty.

💡 Return 1 immediately if array length is 1.

Why it failed: Returning 0 or error on single element input; fix by handling length 1 input explicitly to return 1.

✓ Correctly handles single element base case.

t2_02edge

Input{"nums":[3,3,3,3,3]}

Expected1

⏱ Performance - must finish in 2000ms

All elements equal means no wiggle; max length is 1 (any single element).

💡 Check how zero differences affect wiggle counting.

💡 Equal consecutive elements do not contribute to wiggle length.

💡 Ignore zero differences and count only first element.

Why it failed: Counting zero differences as wiggles leads to wrong length; fix by skipping zero differences in logic.

✓ Correctly ignores equal elements and returns 1.

t2_03edge

Input{"nums":[1,2,3,4,5,6,7,8,9]}

Expected2

⏱ Performance - must finish in 2000ms

Strictly increasing array wiggle length is 2 (first and last elements).

💡 Strictly monotonic sequences have wiggle length 2.

💡 Count first element and first difference sign change only.

💡 Do not count continuous same sign differences beyond first.

Why it failed: Counting all elements in monotonic array leads to overcount; fix by counting only first difference sign change.

✓ Correctly returns 2 for strictly increasing sequence.

t3_01corner

Input{"nums":[1,7,4,5,5,5,6,7,2,1]}

Expected5

⏱ Performance - must finish in 2000ms

Sequence with repeated elements in middle; wiggle length 7 ignoring equal consecutive elements.

💡 Handle consecutive equal elements by ignoring zero differences.

💡 Track direction changes only on non-zero differences.

💡 Update direction only when difference sign flips, skip equal elements.

Why it failed: Including zero differences as wiggle steps inflates count; fix by skipping equal consecutive elements in direction updates.

✓ Correctly handles repeated elements and counts wiggle length.

t3_02corner

Input{"nums":[1,2,3,4,3,2,1,2,3,4]}

Expected4

⏱ Performance - must finish in 2000ms

Greedy trap test: local peaks and valleys must be counted correctly, not just first and last.

💡 Beware of greedy approaches that only count first peak and valley.

💡 Check all sign changes in differences, not just extremes.

💡 Count each valid peak and valley to maximize wiggle length.

Why it failed: Greedy approach counting only first peak and valley undercounts; fix by scanning entire array for all sign changes.

✓ Correctly counts all wiggle peaks and valleys.

t3_03corner

Input{"nums":[1,7,4,9,2,5,5,5,6,7,2,1]}

Expected7

⏱ Performance - must finish in 2000ms

Test for confusion between 0/1 knapsack and wiggle subsequence: must not reuse elements incorrectly.

💡 Ensure subsequence elements are strictly in original order without reuse.

💡 Do not treat problem as unbounded selection; each element used once.

💡 Track direction changes carefully to avoid counting duplicates.

Why it failed: Counting elements multiple times or reusing leads to wrong length; fix by enforcing subsequence order and single usage.

✓ Correctly enforces subsequence constraints.

t4_01performance

Input{"nums":[1000000000,999999999,1000000000,999999999,1000000000,999999999,1000000000,999999999,1000000000,999999999,1000000000,999999999,1000000000,999999999,1000000000,999999999,1000000000,999999999,1000000000,999999999,1000000000,999999999,1000000000,999999999,1000000000,999999999,1000000000,999999999,1000000000,999999999,1000000000,999999999,1000000000,999999999,1000000000,999999999,1000000000,999999999,1000000000,999999999,1000000000,999999999,1000000000,999999999,1000000000,999999999,1000000000,999999999,1000000000,999999999,1000000000,999999999,1000000000,999999999,1000000000,999999999,1000000000,999999999,1000000000,999999999,1000000000,999999999,1000000000,999999999,1000000000,999999999,1000000000,999999999,1000000000,999999999,1000000000,999999999,1000000000,999999999,1000000000,999999999,1000000000,999999999,1000000000,999999999,1000000000,999999999,1000000000,999999999,1000000000,999999999,1000000000,999999999,1000000000,999999999]}

Expectednull

⏱ Performance - must finish in 2000ms

Input size n=100 with alternating large values to test O(n) greedy solution performance within 2 seconds.

💡 Use O(n) time greedy approach to handle large input efficiently.

💡 Avoid exponential or quadratic time solutions.

💡 Track direction changes in a single pass without extra space.

Why it failed: TLE indicates exponential or quadratic complexity; fix by implementing O(n) greedy peak-valley counting.

✓ Solution runs in O(n) time confirming efficient complexity.

Practice

1. Consider the following buggy code for assigning cookies to children. Which line contains the subtle bug that can cause incorrect results?

medium

A. Line 5: Missing increment of j when cookie is assigned

B. Line 3: Incorrect loop condition including count < len(g)

C. Line 1: Missing sorting of g and s arrays

D. Line 7: Incrementing j only in else block

Solution

1. Step 1: Identify missing pointer increment

   When a cookie satisfies a child (s[j] ≥ g[i]), j should increment to avoid reusing the same cookie.

2. Step 2: Check code lines

   Line 5 increments count and i but does not increment j, causing the same cookie to be assigned multiple times.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Without j increment on assignment, cookie reuse occurs [OK]

Hint: Check pointer increments on both branches [OK]

Common Mistakes:

• Forgetting to sort arrays
• Incorrect loop conditions
• Not incrementing both pointers on assignment

2. What is the time complexity of the optimal solution that sorts the list of numbers (converted to strings) using a custom comparator which compares concatenations of pairs?

medium

A. O(n * k * log n), where n is number of elements and k is max digit length

B. O(n! * n * k), where n is number of elements and k is max digit length

C. O(n^2 * k), where n is number of elements and k is max digit length

D. O(n log n * k), where n is number of elements and k is max digit length

Solution

1. Step 1: Identify sorting complexity

   Sorting n elements takes O(n log n) comparisons.

2. Step 2: Each comparison involves concatenating two strings of max length k and comparing them

   Each comparison is O(k), so total is O(n log n * k).

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Sorting with custom comparator comparing concatenations costs O(k) per comparison [OK]

Hint: Each comparison costs O(k), sorting O(n log n) times [OK]

Common Mistakes:

• Confusing O(n*k*log n) with O(n log n * k)
• Assuming O(n^2) due to pairwise comparisons
• Forgetting string concat cost

3. The following code attempts to find the largest monotone increasing digits number less than or equal to n. Identify the bug that causes incorrect results on some inputs.

def monotoneIncreasingDigits(n: int) -> int:
    digits = list(map(int, str(n)))
    marker = len(digits)
    for i in range(len(digits) - 1, 0, -1):
        if digits[i] < digits[i - 1]:
            digits[i - 1] -= 1
            marker = i
    return int(''.join(map(str, digits)))

medium

A. The code does not set digits after the marker to 9, missing the largest monotone number

B. The code decrements digits[i - 1] without checking if it causes new violations earlier

C. The code converts digits back to integer before fixing all digits, causing runtime errors

D. The code ignores the case when all digits are equal, returning incorrect output

Solution

1. Step 1: Analyze the loop effect

   The loop decrements digits[i - 1] when a violation is found and updates marker, but does not fix digits after marker.

2. Step 2: Identify missing step to set trailing digits to 9

   Without setting digits from marker to end to 9, the number may not be the largest monotone number ≤ n.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Missing trailing digit fix leads to smaller-than-necessary result [OK]

Hint: Always set trailing digits to 9 after decrement to maximize number [OK]

Common Mistakes:

• Forgetting to set trailing digits to 9
• Assuming one decrement fixes all violations
• Ignoring edge cases with equal digits

4. What is the time complexity of the optimal Task Scheduler algorithm using a max-heap for t total tasks and m unique tasks?

medium

A. O(t log m) because each task is pushed and popped from a heap of size up to m

B. O(t + m) because counting frequencies and scheduling are linear

C. O(m log t) because heap operations depend on total tasks

D. O(t * m) because each task may be compared with all unique tasks

Solution

1. Step 1: Analyze heap operations

   Heap size is at most m (unique tasks). Each task is pushed and popped at most once per execution.

2. Step 2: Calculate total operations

   For t tasks, each heap operation costs O(log m), so total is O(t log m).

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Heap size depends on unique tasks, not total tasks [OK]

Hint: Heap operations scale with unique tasks, not total tasks [OK]

Common Mistakes:

• Confusing total tasks and unique tasks
• Assuming linear heap operations
• Ignoring log factor in heap push/pop

5. Identify the bug in the following code snippet for the Task Scheduler problem:

medium

A. Line with 'if cnt + 1 <= 0:' should be 'if cnt + 1 < 0:' to avoid pushing zero counts

B. Line with 'time += cycle if not max_heap else n + 1' should always add cycle, not n+1

C. Line with 'for _ in range(n + 1):' should be 'for _ in range(n):' to match cooldown

D. Line with 'heapq.heapify(max_heap)' should be after the while loop

Solution

1. Step 1: Understand frequency decrement logic

   When a task count reaches zero, it should not be pushed back into the heap.

2. Step 2: Check condition for pushing back tasks

   The condition cnt + 1 <= 0 incorrectly pushes zero counts back, causing infinite loops or extra scheduling.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Changing to cnt + 1 < 0 fixes the bug [OK]

Hint: Only push tasks back if remaining count is negative (still pending) [OK]

Common Mistakes:

• Pushing zero counts back causes infinite loops
• Miscounting cooldown cycles
• Incorrect loop ranges