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. Given the following code and input, what is the final output printed?

def maximumUnits(boxTypes, truckSize):
    boxTypes.sort(key=lambda x: x[1], reverse=True)
    totalUnits = 0
    for boxes, units in boxTypes:
        if truckSize == 0:
            break
        take = min(boxes, truckSize)
        totalUnits += take * units
        truckSize -= take
    return totalUnits

boxTypes = [[1,3],[2,2],[3,1]]
truckSize = 4
print(maximumUnits(boxTypes, truckSize))

easy

A. 7

B. 8

C. 9

D. 6

Solution

1. Step 1: Sort boxTypes by units descending

   Sorted list: [[1,3],[2,2],[3,1]] (already sorted)

2. Step 2: Iterate and pick boxes until truckSize=0

   Take 1 box with 3 units -> totalUnits=3, truckSize=3 left; take 2 boxes with 2 units -> totalUnits=3+4=7, truckSize=1 left; take 1 box with 1 unit -> totalUnits=7+1=8, truckSize=0 stop.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Sum matches manual calculation [OK]

Hint: Sort by units descending and pick greedily [OK]

Common Mistakes:

• Off-by-one in take calculation
• Not stopping when truckSize=0
• Incorrect sorting order

2. You have two arrays representing the top and bottom halves of dominoes. You want to make all values in one row uniform by rotating some dominoes. Which algorithmic approach guarantees an optimal solution with minimal rotations?

easy

A. Dynamic Programming that tries all possible uniform values and stores intermediate results

B. Greedy approach checking only the two candidate values from the first domino

C. Backtracking to try all rotation combinations exhaustively

D. Sorting both arrays and then matching values to minimize rotations

Solution

1. Step 1: Identify candidate values from the first domino

   The only possible uniform values are the top or bottom value of the first domino, since all dominoes must match one of these.

2. Step 2: Check feasibility and count rotations

   For each candidate, verify if all dominoes can be rotated to match it and count minimal rotations needed.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Checking only two candidates reduces complexity and guarantees correctness [OK]

Hint: Only two candidates from first domino suffice [OK]

Common Mistakes:

• Trying all numbers 1-6 unnecessarily
• Using DP or backtracking wasting time

3. What is the time complexity of the optimal max heap approach to reorganize a string of length n with k unique characters?

medium

A. O(n²) because each character insertion may require scanning the entire string

B. O(n log k) because each of the n characters is pushed and popped from a heap of size k

C. O(k log n) because the heap operations depend on the string length

D. O(n) because each character is processed once without extra overhead

Solution

1. Step 1: Identify heap operations per character

   Each character is pushed and popped at most once per occurrence, total n operations.

2. Step 2: Analyze heap size and operation cost

   Heap size is at most k (unique chars), each push/pop is O(log k), so total O(n log k).

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Heap operations dominate, not scanning entire string [OK]

Hint: Heap ops cost O(log k) per character [OK]

Common Mistakes:

• Confusing n and k in complexity
• Assuming linear time without heap cost
• Mistaking quadratic due to nested loops

4. Suppose the problem is modified so that children can have equal ratings but must still have strictly more candies than neighbors with lower ratings. Which modification to the optimal algorithm correctly handles this variant?

hard

A. Change comparison from '>' to '>=' in both passes to handle equal ratings

B. Keep '>' comparisons but initialize candies with zeros and adjust accordingly

C. Use the same two-pass greedy with '>' comparisons but do not update candies if ratings are equal

D. Replace two-pass greedy with a sorting-based approach to assign candies in rating order

Solution

1. Step 1: Understand new requirement

   Children with equal ratings do not require more candies than each other, only strictly higher ratings require more candies.

2. Step 2: Adjust comparisons in algorithm

   Keep '>' comparisons to ensure only strictly higher ratings get more candies; do not update candies when ratings are equal.

3. Step 3: Avoid changing to '>=' which would incorrectly increase candies for equal ratings

   Changing to '>=' breaks minimality and correctness.

4. Final Answer:

   Option C -> Option C

5. Quick Check:

   Strict '>' comparisons preserve problem constraints with equal ratings [OK]

Hint: Strict '>' comparisons handle equal ratings correctly [OK]

Common Mistakes:

• Changing '>' to '>=' causing over-assignment
• Initializing candies with zeros
• Using sorting unnecessarily

5. Suppose now you can reuse sticks after merging (i.e., merged sticks remain available for future merges without removal). Which modification to the algorithm correctly computes the minimum cost to connect all sticks under this new rule?

hard

A. Use a dynamic programming approach to consider all merge sequences

B. Sort sticks once and merge sticks in ascending order without a heap

C. The problem becomes ill-defined; no algorithm can guarantee minimum cost with reuse

D. Use the same min-heap approach but do not remove merged sticks from the heap

Solution

1. Step 1: Understand reuse impact

   If sticks can be reused infinitely, merges do not reduce the number of sticks, so the problem changes fundamentally.

2. Step 2: Analyze problem feasibility

   Because sticks remain after merging, the process can continue indefinitely, making minimum total cost undefined or infinite.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Reuse breaks the problem constraints -> no minimal cost solution [OK]

Hint: Reusing sticks breaks problem constraints -> no minimal cost [OK]

Common Mistakes:

• Assuming min-heap still works without removing merged sticks
• Trying to sort once ignoring dynamic merges
• Attempting DP without problem redefinition