What is the brute force approach and complexity for Wiggle Subsequence?

Take or skip each number, then check each subsequence for the wiggle rule with time complexity O(N · 2^N) and space complexity O(N).

What is the optimal approach and complexity for Wiggle Subsequence?

Keep up and down; a rise sets up = down + 1, a fall sets down = up + 1 with optimal time complexity O(N) and space complexity O(1).

How do you identify the pattern for Wiggle Subsequence?

Look for key signals in the prompt: "wiggle" indicates The steps alternate between rises and falls. The state must remember the direction of the last step.; "subsequence" indicates Numbers can be skipped, so a rise can come from any earlier number, not only the one right before.; "equal numbers" indicates A flat step is not a rise or a fall, so it breaks a wiggle and changes nothing..

Wiggle Subsequence

Medium·LeetCode #376 Pro OnlyMedium

LeetCode

Problem Statement

A wiggle is a list of numbers where every step is a rise or a fall, and the steps alternate: up, down, up, down, and so on. A step that is flat (two equal numbers next to each other) breaks the wiggle.

You may drop any numbers from the list, but the rest must keep their order. Return the length of the longest subsequence that is a wiggle.

Input

nums, a list of whole numbers. The list is not sorted.

Output

The length of the longest wiggle subsequence.

Example 1

Input: nums = [1, 7, 4, 9, 2, 5]

Output: 6

The whole list is a wiggle. The steps are +6, −3, +5, −7, +3, which alternate.

Example 2

Input: nums = [1, 17, 5, 10, 13, 15, 10, 5, 16, 8]

Output: 7

One longest wiggle is 1, 17, 10, 13, 10, 16, 8, with steps +16, −7, +3, −3, +6, −8.

Example 3

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

Output: 2

Every step goes up, so the most we can keep is two numbers, such as 1 and 9.

Constraints

• 1 ≤ nums.length ≤ 1000
• 0 ≤ nums[i] ≤ 1000

Pattern Recognition Clues

Recognising these key signals in the problem description immediately identifies the pattern:

“wiggle”

→ The steps alternate between rises and falls. The state must remember the direction of the last step.

“subsequence”

→ Numbers can be skipped, so a rise can come from any earlier number, not only the one right before.

“equal numbers”

→ A flat step is not a rise or a fall, so it breaks a wiggle and changes nothing.

Approach Complexity Ladder

Brute Force — try every subsequenceO(N · 2^N)O(N)

Take or skip each number, then check each subsequence for the wiggle rule

Better — up and down for every positionO(N^2)O(N)

up[i] and down[i] are the longest wiggles ending at nums[i]; look back at every earlier j

Optimal — two variables, walk left to rightO(N)O(1)

Keep up and down; a rise sets up = down + 1, a fall sets down = up + 1

Brute Force Intuition

Each number is either taken or skipped, so there are 2^N subsequences. For each one, check the wiggle rule: every step must be non-zero, and the steps must alternate in sign. Keep the longest one that passes.

Recognition rule for this sub-pattern:

Same idea with a custom "can follow" rule; keep parent pointers to rebuild the chain.

Remember this · DP — Longest Increasing Subsequence

Trigger

Longest chain where each item must be bigger/fit inside the previous one (numbers, pairs, envelopes, words).

Think

Does each element extend the best chain ending at some smaller earlier element?

Key question

Sort first? Then what does "increasing" mean for these items?

Brute2Best Pro Content

Unlock Complete Visual Walkthrough & Optimal C++

The interactive animated dry-run player, optimized C++ implementation, state invariant derivations, and edge-case breakdown for this question are part of Brute2Best Pro. The anchor question of every sub-pattern is completely free.

All 440 visual dry runs & algorithms

Interactive step-by-step playback with pointer & array state transitions

52 comprehensive LLD chapters

Interactive UML diagrams, real-world stories (Food Delivery, Trading, RPG), and practice solutions

40 C++ basics labs & hardware memory models

Vtables, byte layouts, assembly insights, and multi-threading race conditions

Production-ready C++23 source code

Modern idioms, clean contracts, time/space complexity derivations, and interview takeaways

Create Free Account Log in

First anchor question per pattern, Part 1 LLD & Module 1 C++ basics are 100% Free forever.

Beyond The LeetCode Problem

How this concept connects to System Design & C++ Systems

Bridge DSA with production engineering

Top engineering interviews test whether you understand how algorithms like DP — Longest Increasing Subsequence translate into production architectures and low-level memory mechanics.

LLD Architecture