MEDIUM 1-D Dynamic Programming / Greedy

376. Wiggle Subsequence

📖 Problem

A wiggle sequence is a sequence where differences between successive numbers strictly alternate between positive and negative. The first difference (if one exists) may be either positive or negative. Given an integer array nums, return length of the longest wiggle subsequence of nums.

🧠 Visual Learning Aid

1 Model the input into the right structure
2 Choose the core technique and invariant
3 Execute step-by-step with a sample
4 Validate complexity and edge cases

JS/TS Refreshers

  • •Array methods (`push`, `pop`, `shift`, `slice`)
  • •Object/Map/Set usage patterns
  • •Function parameter and return typing
  • •Array DP table updates
  • •State transition thinking
  • •Base case initialization

Logical Thinking Concepts

  • •Define invariants before coding
  • •Check edge cases first (`[]`, single element, duplicates)
  • •Estimate time/space before implementation
  • •Apply Dynamic Programming reasoning pattern
  • •Apply Greedy reasoning pattern

💡 Approach

  • → Use greedy to capture all wiggle points
  • → For each number, check if it creates a wiggle with previous diff
  • → Count wiggle points as we find them
  • → Time: O(n), Space: O(1)

🛠️ Hints & Pitfalls

Hints

  • •Use greedy to capture all wiggle points
  • •For each number, check if it creates a wiggle with previous diff
  • •Count wiggle points as we find them

Common Pitfalls

  • •Time: O(n), Space: O(1)

🧪 Test Cases

Hidden tests on submit: 1

Test Case 1
Not run
Input:
wiggleMaxLength([1,7,4,9,2,5]);
Expected:
6
Test Case 2
Not run
Input:
wiggleMaxLength([0,0]);
Expected:
1
Test Case 3
Not run
Input:
wiggleMaxLength([1,2,3]);
Expected:
2

📝 Code Editor

📚 Reference Solution

▼
⌘K Search ⌘↩ Run ⌘S Submit