Bird
Raised Fist0

The following code attempts to implement the optimal wiggle subsequence algorithm. Identify the line containing the subtle bug that causes incorrect results on inputs with consecutive equal elements.

medium🐞 Bug Identification Q14 of Q15
Greedy Algorithms - Wiggle Subsequence
The following code attempts to implement the optimal wiggle subsequence algorithm. Identify the line containing the subtle bug that causes incorrect results on inputs with consecutive equal elements.
def wiggleMaxLength(nums):
    if not nums:
        return 0
    count = 1
    last_diff = 0
    for i in range(1, len(nums)):
        diff = nums[i] - nums[i - 1]
        if (diff > 0 and last_diff < 0) or (diff < 0 and last_diff > 0):
            count += 1
            last_diff = diff
    return count
ALine 6: Using strict inequalities (last_diff < 0 and last_diff > 0) instead of inclusive (<= 0 and >= 0)
BLine 3: Initializing count to 1 instead of 0
CLine 7: Updating last_diff inside the if condition
DLine 2: Returning 0 if nums is empty
Step-by-Step Solution
Solution:
  1. Step 1: Understand the condition for counting wiggles

    The condition must allow last_diff to be zero or equal to zero to handle initial or equal consecutive elements correctly.
  2. Step 2: Identify the bug

    Using strict inequalities excludes cases where last_diff is zero, causing the algorithm to skip valid wiggles after equal elements, leading to incorrect counts.
  3. Final Answer:

    Option A -> Option A
  4. Quick Check:

    Inclusive inequalities fix counting on equal consecutive elements [OK]
Quick Trick: Use <= 0 and >= 0 to handle zero last_diff correctly
Common Mistakes:
MISTAKES
  • Using strict inequalities causing missed wiggles
  • Incorrect initialization of counters
  • Updating last_diff outside condition
Trap Explanation:
PITFALL
  • Strict inequalities look cleaner but break handling of zero differences.
Interviewer Note:
CONTEXT
  • Tests attention to subtle boundary conditions and correctness on edge cases.
Master "Wiggle Subsequence" in Greedy Algorithms

3 interactive learning modes - each teaches the same concept differently

Want More Practice?

15+ quiz questions · All difficulty levels · Free

Free Signup - Practice All Questions
More Greedy Algorithms Quizzes