Skip to main content

376. Wiggle Subsequence

medium

Find the longest subsequence whose consecutive differences strictly alternate sign. A two-state DP (last direction up vs down) collapsing to two scalars.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Problem

A wiggle sequence is a sequence 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 sequence with one element and a sequence with two non-equal elements are trivially wiggle sequences. Given an integer array nums, return the length of the longest wiggle subsequence of nums.

Constraints

  • 1 <= nums.length <= 1000
  • 0 <= nums[i] <= 1000

Examples

Example 1

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

Explanation: The entire sequence is a wiggle sequence with differences (6, -3, 5, -7, 3).

Example 2

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

Explanation: There are several subsequences that achieve this length. One is [1, 17, 10, 13, 10, 16, 8] with differences (16, -7, 3, -3, 6, -8).

Example 3

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

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

Two states per index: longest wiggle ending up (last diff positive) and longest wiggle ending down.

Hint 2

If nums[i] > nums[i-1] then up = down + 1. If less, down = up + 1. Otherwise neither changes.

Hint 3

Track up and down as scalars; answer is max(up, down).

Solution approach

Reveal approach

Two-state DP collapsed to two scalars. Let up = length of the longest wiggle subsequence ending with a positive difference and down = length ending with a negative difference. Initialize up = down = 1. For i from 1 to n-1: if nums[i] > nums[i-1] then up = down + 1 (extend a down-ending subsequence by going up); if nums[i] < nums[i-1] then down = up + 1; if equal do nothing. Return max(up, down). The greedy is correct because at each strict inequality you can always replace the previous endpoint to extend by exactly one. O(n) time, O(1) space.

Complexity

Time
O(n)
Space
O(1)

Related patterns

  • dynamic-programming
  • greedy
  • state-machine

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Amazon

Practice these live with InterviewChamp.AI

Drill Wiggle Subsequence and DP 1D problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →