The O(n) Club: Wiggle Subsequence — Try Not To Flatline

The O(n) Club: Wiggle Subsequence — Try Not To Flatline

⚡ TL;DR

Find the length of the longest up-down-up-down (no meh in the middle) subsequence. Don’t store history, don’t overthink. Here’s the Java gist:

// Brute force? Sure, if your favorite runtime is 'forever'.
// Do it right:
int up = 1, down = 1;
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;
    // flats? They don’t wiggle.
}
return Math.max(up, down);

🧠 How Devs Usually Mess This Up

If “subsequence” makes you see a 2D DP table or contemplate a recursive tree of doom, you’ve gone too far, Ross. Most mess-ups come from:

• Forgetting subsequences aren’t contiguous: You can skip numbers.
• Counting flats as wiggles: If nums[i] == nums[i-1], that’s a snooze, not a wiggle.
• Panicking about the first move: It’s fine. Up, down, whatever—the method adapts like a good sitcom cast.

🔍 What’s Actually Going On

This is just a zig-zag dance: you keep track of the longest climb and drop—no repeats, no flat moves, just pure alternation. Think of it as a party where only people who change direction get invited. You don’t even remember the steps; you just compare with your last ‘move’ and decide if you need to switch partners… or ignore the boring ones.

🛠️ PseudoCode

• Start with up = 1 and down = 1 since a single value is a valid wiggle (sort of like calling a single potato chip a “snack”).
• Loop from i = 1 to end:
  • If nums[i] > nums[i-1], set up = down + 1. (Just had an upswing!)
  • If nums[i] < nums[i-1], set down = up + 1. (Rollercoaster drops.)
  • If nums[i] == nums[i-1], do nothing. Boring, like unbuttered toast.
• Return the bigger of up and down at the end.

💻 The Code

public class WiggleSubsequence {
    public int wiggleMaxLength(int[] nums) {
        if (nums == null || nums.length == 0) return 0;
        int up = 1, down = 1;
        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;
            }
            // Ignore flats, like you ignore cold calls.
        }
        return Math.max(up, down);
    }
}

⚠️ Pitfalls, Traps & Runtime Smacks

• Zero differences don’t count: Flats don’t wiggle—don’t let your code think they do.
• Multiple right answers: There can be several longest wiggly paths; you only care about length.
• Edge cases: Empty array? Return 0. One number? Return 1 (sure, why not). Two different nums? Always 2.
• Complexity: Time: O(n), Space: O(1). That’s right: quick and cheap, like a developer lunch.

🧠 Interviewer Brain-Tattoo

“Real devs don’t waste time on flats. If you’re writing DP tables for this, you’re coding in the wrong reality.”