Wiggle Subsequence

Wiggle Subsequence

What is this problem about?

The "Wiggle Subsequence" problem asks for the length of the longest subsequence that follows the wiggle pattern (differences between successive numbers alternate between positive and negative). Unlike the wiggle sort, this is about finding the longest subsequence (elements don't have to be contiguous), not reordering the whole array.

Why is this asked in interviews?

This is a classic Dynamic Programming and Greedy problem. Companies like Bloomberg ask this to see if a candidate can optimize a DP solution from O(N^2) down to O(N). It requires recognizing that we only care about the "peaks" and "valleys" of the array's trend.

Algorithmic pattern used

The optimal approach is Greedy. We only care about how many times the direction of the sequence changes (from increasing to decreasing or vice-versa). We can maintain two variables: up (the length of the longest wiggle sequence ending with an increasing step) and down (the length of the longest wiggle sequence ending with a decreasing step).

Example explanation

Array: [1, 7, 4, 9, 2, 5].

1. 1 -> 7: Increasing. up = down + 1 = 2.
2. 7 -> 4: Decreasing. down = up + 1 = 3.
3. 4 -> 9: Increasing. up = down + 1 = 4.
4. 9 -> 2: Decreasing. down = up + 1 = 5.
5. 2 -> 5: Increasing. up = down + 1 = 6. Longest wiggle subsequence length is 6. If the array was [1, 2, 3], the length would only be 2 because there is no direction change.

Common mistakes candidates make

• Counting adjacent duplicates: Failing to skip elements that are equal to the previous one, as they don't contribute to a wiggle.
• Overcomplicating with O(N^2) DP: Defining dp[i][j] when only two state variables are needed.
• Missing the first element: Forgetting to count the starting element of the sequence.

Interview preparation tip

When dealing with subsequences and trends, visualize the array as a line graph. The wiggle subsequence length is essentially the number of times the graph changes direction plus one. This "peak-valley" logic is a very efficient greedy pattern.