Wiggle Subsequence

🎯

Wiggle Subsequence

mediumGREEDYAmazonGoogle

Imagine tracking stock prices that fluctuate daily and wanting to find the longest sequence of ups and downs to maximize trading opportunities.

💡 This problem asks for the longest subsequence where the differences between consecutive numbers strictly alternate between positive and negative. Beginners often struggle because it looks like a dynamic programming problem but can be solved greedily by understanding the pattern of peaks and valleys.

📋

Problem Statement

Given an integer array nums, return the length of the longest wiggle subsequence. A wiggle sequence is one 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 subsequence is obtained by deleting some elements (possibly zero) from the original sequence, leaving the remaining elements in their original order.

1 ≤ nums.length ≤ 10^5-10^9 ≤ nums[i] ≤ 10^9

💡

Example

Input"[1,7,4,9,2,5]"

Output6

The entire sequence is a wiggle sequence: differences are +6, -3, +5, -7, +3 alternating signs.

Input"[1,17,5,10,13,15,10,5,16,8]"

Output7

One longest wiggle subsequence is [1,17,10,13,10,16,8].

Input"[1,2,3,4,5,6,7,8,9]"

Output2

Longest wiggle subsequence is any two consecutive numbers since all differences are positive.

• Single element array → output 1
• All elements equal → output 1
• Strictly increasing array → output 2
• Strictly decreasing array → output 2

⚠️

Common Mistakes

Not handling equal consecutive elements properly

Incorrectly counting or skipping wiggles, leading to wrong answer

✅ Ignore zero differences when updating counts or last difference

Confusing subsequence with substring

Trying to find contiguous wiggle sequences instead of subsequences, missing longer solutions

✅ Remember subsequences can skip elements, so do not require contiguous indices

Using brute force in interviews without pruning

Code runs too slowly and times out

✅ Explain brute force but quickly move to greedy approach

Incorrect initialization of counters or last difference

Off-by-one errors leading to wrong counts

✅ Initialize counts to 1 and last difference to 0 carefully

Not testing edge cases like single element or all equal elements

Code may crash or return wrong results

✅ Add explicit checks for these cases

🧠

Brute Force (Pure Recursion)

💡 This approach explores all subsequences to find the longest wiggle subsequence. It is extremely inefficient but helps understand the problem deeply by considering every possibility.

Intuition

Try every subsequence by recursively deciding whether to include or exclude each element, checking if the wiggle property holds.

Algorithm

1. Start from the first element and recursively explore subsequences.
2. At each step, decide to include the current element if it forms a wiggle with the previous included element.
3. Keep track of the last difference sign to ensure alternation.
4. Return the maximum length found among all valid subsequences.

💡 The recursion explores all subsequences, which is conceptually simple but computationally expensive.

</>

Code

def wiggleMaxLength(nums):
    def dfs(index, prev, diff):
        if index == len(nums):
            return 0
        taken = 0
        if diff == 0 or (nums[index] - prev) * diff < 0:
            taken = 1 + dfs(index + 1, nums[index], nums[index] - prev)
        not_taken = dfs(index + 1, prev, diff)
        return max(taken, not_taken)

    if not nums:
        return 0
    return 1 + dfs(1, nums[0], 0)

# Driver code
if __name__ == '__main__':
    print(wiggleMaxLength([1,7,4,9,2,5]))  # Expected output: 6

Line Notes

def dfs(index, prev, diff):Defines recursive helper to explore subsequences from current index

if index == len(nums):Base case: reached end of array, no more elements to consider

if diff == 0 or (nums[index] - prev) * diff < 0:Check if current difference alternates sign or is first difference

taken = 1 + dfs(index + 1, nums[index], nums[index] - prev)Include current element and recurse

not_taken = dfs(index + 1, prev, diff)Exclude current element and recurse

return max(taken, not_taken)Choose the better option between taking or skipping current element

if not nums:Handle empty input edge case

return 1 + dfs(1, nums[0], 0)Start recursion with first element included and no previous difference

public class Solution {
    public int wiggleMaxLength(int[] nums) {
        return nums.length == 0 ? 0 : 1 + dfs(nums, 1, nums[0], 0);
    }

    private int dfs(int[] nums, int index, int prev, int diff) {
        if (index == nums.length) return 0;
        int taken = 0;
        if (diff == 0 || (nums[index] - prev) * diff < 0) {
            taken = 1 + dfs(nums, index + 1, nums[index], nums[index] - prev);
        }
        int notTaken = dfs(nums, index + 1, prev, diff);
        return Math.max(taken, notTaken);
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.wiggleMaxLength(new int[]{1,7,4,9,2,5})); // Expected: 6
    }
}

Line Notes

public int wiggleMaxLength(int[] nums)Entry point for solution, handles empty array

return nums.length == 0 ? 0 : 1 + dfs(...)Start recursion with first element included

private int dfs(int[] nums, int index, int prev, int diff)Recursive helper exploring subsequences

if (index == nums.length) return 0;Base case: no more elements to process

if (diff == 0 || (nums[index] - prev) * diff < 0)Check if current difference alternates sign

taken = 1 + dfs(...)Include current element and recurse

int notTaken = dfs(...)Exclude current element and recurse

return Math.max(taken, notTaken);Choose best option

#include <iostream>
#include <vector>
using namespace std;

class Solution {
public:
    int dfs(const vector<int>& nums, int index, int prev, int diff) {
        if (index == nums.size()) return 0;
        int taken = 0;
        if (diff == 0 || (nums[index] - prev) * diff < 0) {
            taken = 1 + dfs(nums, index + 1, nums[index], nums[index] - prev);
        }
        int notTaken = dfs(nums, index + 1, prev, diff);
        return max(taken, notTaken);
    }

    int wiggleMaxLength(vector<int>& nums) {
        if (nums.empty()) return 0;
        return 1 + dfs(nums, 1, nums[0], 0);
    }
};

int main() {
    Solution sol;
    vector<int> nums = {1,7,4,9,2,5};
    cout << sol.wiggleMaxLength(nums) << endl; // Expected: 6
    return 0;
}

Line Notes

int dfs(const vector<int>& nums, int index, int prev, int diff)Recursive helper exploring subsequences

if (index == nums.size()) return 0;Base case: no more elements

if (diff == 0 || (nums[index] - prev) * diff < 0)Check if difference alternates sign

taken = 1 + dfs(...)Include current element and recurse

int notTaken = dfs(...)Exclude current element and recurse

return max(taken, notTaken);Choose the better option

if (nums.empty()) return 0;Handle empty input

return 1 + dfs(nums, 1, nums[0], 0);Start recursion with first element included

function wiggleMaxLength(nums) {
    function dfs(index, prev, diff) {
        if (index === nums.length) return 0;
        let taken = 0;
        if (diff === 0 || (nums[index] - prev) * diff < 0) {
            taken = 1 + dfs(index + 1, nums[index], nums[index] - prev);
        }
        let notTaken = dfs(index + 1, prev, diff);
        return Math.max(taken, notTaken);
    }
    if (nums.length === 0) return 0;
    return 1 + dfs(1, nums[0], 0);
}

// Test
console.log(wiggleMaxLength([1,7,4,9,2,5])); // Expected: 6

Line Notes

function dfs(index, prev, diff)Recursive helper to explore subsequences

if (index === nums.length) return 0;Base case: no more elements

if (diff === 0 || (nums[index] - prev) * diff < 0)Check if difference alternates sign

taken = 1 + dfs(...)Include current element and recurse

let notTaken = dfs(...)Exclude current element and recurse

return Math.max(taken, notTaken);Choose best option

if (nums.length === 0) return 0;Handle empty input

return 1 + dfs(1, nums[0], 0);Start recursion with first element included

⏱

Complexity

TimeO(2^n)

SpaceO(n)

Each element can be included or excluded, leading to exponential subsequences. Recursion stack depth is O(n).

💡 For n=20, this means over a million calls, which is impractical in interviews.

Interview Verdict: TLE

This approach is too slow for large inputs but is useful to understand the problem and motivate better solutions.

🧠

Greedy Approach with Peak-Valley Counting

💡 This approach uses the insight that the longest wiggle subsequence corresponds to counting peaks and valleys in the array, allowing a linear time solution.

Intuition

Track the direction of differences and count changes in direction, which correspond to wiggles.

Algorithm

1. Initialize two counters: up and down to 1 (minimum wiggle length).
2. Iterate through the array from the second element.
3. If current element > previous, update up = down + 1.
4. If current element < previous, update down = up + 1.
5. Return the maximum of up and down.

💡 This method efficiently tracks wiggle lengths by updating counters based on the current difference sign.

</>

Code

def wiggleMaxLength(nums):
    if not nums:
        return 0
    up = down = 1
    for i in range(1, len(nums)):
        if nums[i] > nums[i - 1]:
            up = down + 1
        elif nums[i] < nums[i - 1]:
            down = up + 1
    return max(up, down)

# Driver code
if __name__ == '__main__':
    print(wiggleMaxLength([1,7,4,9,2,5]))  # Expected output: 6

Line Notes

if not nums:Handle empty input edge case

up = down = 1Initialize counters for wiggle lengths starting at 1

for i in range(1, len(nums)):Iterate through array from second element

if nums[i] > nums[i - 1]:Current difference is positive, update up

up = down + 1Increase up count based on previous down count

elif nums[i] < nums[i - 1]:Current difference is negative, update down

down = up + 1Increase down count based on previous up count

return max(up, down)Return the maximum wiggle subsequence length

public class Solution {
    public int wiggleMaxLength(int[] nums) {
        if (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;
            }
        }
        return Math.max(up, down);
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.wiggleMaxLength(new int[]{1,7,4,9,2,5})); // Expected: 6
    }
}

Line Notes

if (nums.length == 0) return 0;Handle empty input

int up = 1, down = 1;Initialize counters for wiggle lengths

for (int i = 1; i < nums.length; i++)Iterate through array from second element

if (nums[i] > nums[i - 1])Positive difference detected

up = down + 1;Update up count based on previous down

else if (nums[i] < nums[i - 1])Negative difference detected

down = up + 1;Update down count based on previous up

return Math.max(up, down);Return maximum wiggle length

#include <iostream>
#include <vector>
using namespace std;

class Solution {
public:
    int wiggleMaxLength(vector<int>& nums) {
        if (nums.empty()) return 0;
        int up = 1, down = 1;
        for (int i = 1; i < nums.size(); i++) {
            if (nums[i] > nums[i - 1]) {
                up = down + 1;
            } else if (nums[i] < nums[i - 1]) {
                down = up + 1;
            }
        }
        return max(up, down);
    }
};

int main() {
    Solution sol;
    vector<int> nums = {1,7,4,9,2,5};
    cout << sol.wiggleMaxLength(nums) << endl; // Expected: 6
    return 0;
}

Line Notes

if (nums.empty()) return 0;Handle empty input

int up = 1, down = 1;Initialize counters for wiggle lengths

for (int i = 1; i < nums.size(); i++)Iterate from second element

if (nums[i] > nums[i - 1])Positive difference detected

up = down + 1;Update up count based on previous down

else if (nums[i] < nums[i - 1])Negative difference detected

down = up + 1;Update down count based on previous up

return max(up, down);Return maximum wiggle length

function wiggleMaxLength(nums) {
    if (nums.length === 0) return 0;
    let up = 1, down = 1;
    for (let 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;
        }
    }
    return Math.max(up, down);
}

// Test
console.log(wiggleMaxLength([1,7,4,9,2,5])); // Expected: 6

Line Notes

if (nums.length === 0) return 0;Handle empty input

let up = 1, down = 1;Initialize counters for wiggle lengths

for (let i = 1; i < nums.length; i++)Iterate from second element

if (nums[i] > nums[i - 1])Positive difference detected

up = down + 1;Update up count based on previous down

else if (nums[i] < nums[i - 1])Negative difference detected

down = up + 1;Update down count based on previous up

return Math.max(up, down);Return maximum wiggle length

⏱

Complexity

TimeO(n)

SpaceO(1)

Single pass through the array with constant extra space.

💡 For n=100000, this means 100000 operations, which is efficient for interviews.

Interview Verdict: Accepted

This is the preferred approach in interviews due to its simplicity and efficiency.

🧠

Greedy with Explicit Direction Tracking

💡 This approach explicitly tracks the last difference sign and counts wiggles when the sign changes, making the logic very clear.

Intuition

Keep track of the last difference sign and increment count only when the current difference changes sign compared to the last.

Algorithm

1. Initialize count to 1 and last_diff to 0.
2. Iterate through the array from the second element.
3. Calculate current difference between current and previous element.
4. If current difference and last_diff have opposite signs, increment count and update last_diff.
5. Return count.

💡 This approach explicitly models the wiggle pattern by tracking sign changes, which is intuitive.

</>

Code

def wiggleMaxLength(nums):
    if not nums:
        return 0
    count = 1
    last_diff = 0
    for i in range(1, len(nums)):
        diff = nums[i] - nums[i - 1]
        if (diff > 0 and last_diff <= 0) or (diff < 0 and last_diff >= 0):
            count += 1
            last_diff = diff
    return count

# Driver code
if __name__ == '__main__':
    print(wiggleMaxLength([1,7,4,9,2,5]))  # Expected output: 6

Line Notes

if not nums:Handle empty input

count = 1Start count at 1 for first element

last_diff = 0Initialize last difference sign as zero (no difference yet)

for i in range(1, len(nums)):Iterate from second element

diff = nums[i] - nums[i - 1]Calculate current difference

if (diff > 0 and last_diff <= 0) or (diff < 0 and last_diff >= 0):Check if difference sign changed

count += 1Increment count on wiggle

last_diff = diffUpdate last difference sign

public class Solution {
    public int wiggleMaxLength(int[] nums) {
        if (nums.length == 0) return 0;
        int count = 1;
        int lastDiff = 0;
        for (int i = 1; i < nums.length; i++) {
            int diff = nums[i] - nums[i - 1];
            if ((diff > 0 && lastDiff <= 0) || (diff < 0 && lastDiff >= 0)) {
                count++;
                lastDiff = diff;
            }
        }
        return count;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.wiggleMaxLength(new int[]{1,7,4,9,2,5})); // Expected: 6
    }
}

Line Notes

if (nums.length == 0) return 0;Handle empty input

int count = 1;Initialize count for first element

int lastDiff = 0;Initialize last difference sign

for (int i = 1; i < nums.length; i++)Iterate from second element

int diff = nums[i] - nums[i - 1];Calculate current difference

if ((diff > 0 && lastDiff <= 0) || (diff < 0 && lastDiff >= 0))Check for sign change

count++;Increment count on wiggle

lastDiff = diff;Update last difference

#include <iostream>
#include <vector>
using namespace std;

class Solution {
public:
    int wiggleMaxLength(vector<int>& nums) {
        if (nums.empty()) return 0;
        int count = 1;
        int lastDiff = 0;
        for (int i = 1; i < nums.size(); i++) {
            int diff = nums[i] - nums[i - 1];
            if ((diff > 0 && lastDiff <= 0) || (diff < 0 && lastDiff >= 0)) {
                count++;
                lastDiff = diff;
            }
        }
        return count;
    }
};

int main() {
    Solution sol;
    vector<int> nums = {1,7,4,9,2,5};
    cout << sol.wiggleMaxLength(nums) << endl; // Expected: 6
    return 0;
}

Line Notes

if (nums.empty()) return 0;Handle empty input

int count = 1;Initialize count for first element

int lastDiff = 0;Initialize last difference sign

for (int i = 1; i < nums.size(); i++)Iterate from second element

int diff = nums[i] - nums[i - 1];Calculate current difference

if ((diff > 0 && lastDiff <= 0) || (diff < 0 && lastDiff >= 0))Check for sign change

count++;Increment count on wiggle

lastDiff = diff;Update last difference

function wiggleMaxLength(nums) {
    if (nums.length === 0) return 0;
    let count = 1;
    let lastDiff = 0;
    for (let i = 1; i < nums.length; i++) {
        let diff = nums[i] - nums[i - 1];
        if ((diff > 0 && lastDiff <= 0) || (diff < 0 && lastDiff >= 0)) {
            count++;
            lastDiff = diff;
        }
    }
    return count;
}

// Test
console.log(wiggleMaxLength([1,7,4,9,2,5])); // Expected: 6

Line Notes

if (nums.length === 0) return 0;Handle empty input

let count = 1;Initialize count for first element

let lastDiff = 0;Initialize last difference sign

for (let i = 1; i < nums.length; i++)Iterate from second element

let diff = nums[i] - nums[i - 1];Calculate current difference

if ((diff > 0 && lastDiff <= 0) || (diff < 0 && lastDiff >= 0))Check for sign change

count++;Increment count on wiggle

lastDiff = diff;Update last difference

⏱

Complexity

TimeO(n)

SpaceO(1)

Single pass through array with constant space to track last difference and count.

💡 This approach is efficient and easy to implement, suitable for large inputs.

Interview Verdict: Accepted

This approach is optimal and clearly shows understanding of the wiggle pattern.

📊

All Approaches - One-Glance Tradeoffs

💡 The greedy approaches (2 and 3) are optimal and should be coded in interviews. Brute force is only for conceptual understanding.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	O(2^n)	O(n) recursion stack	Yes (deep recursion)	Yes	Mention only - never code
2. Greedy Peak-Valley Counting	O(n)	O(1)	No	No (length only)	Code this for optimal solution
3. Greedy with Explicit Direction Tracking	O(n)	O(1)	No	No (length only)	Alternative optimal approach, easy to explain

💼

Interview Strategy

💡 Use this guide to understand the problem deeply, practice coding the greedy solutions, and prepare to explain your reasoning clearly in interviews.

How to Present

Step 1: Clarify the problem and ask about input constraints.Step 2: Describe the brute force approach to show understanding.Step 3: Explain why brute force is inefficient.Step 4: Present the greedy peak-valley counting approach.Step 5: Code the greedy solution and test with examples.Step 6: Discuss edge cases and possible follow-ups.

Time Allocation

Clarify: 3min → Approach: 5min → Code: 10min → Test: 5min. Total ~23min

What the Interviewer Tests

The interviewer tests your ability to recognize the wiggle pattern, optimize from brute force to greedy, and write clean, efficient code.

Common Follow-ups

• Can you reconstruct the actual longest wiggle subsequence? → Yes, by tracking elements during iteration.
• What if equal consecutive elements are allowed? → Adjust conditions to handle zero differences.
• Can you solve this with DP? → Yes, but greedy is more optimal here.
• What if the input is very large? → Greedy approach handles large inputs efficiently.

💡 These follow-ups test deeper understanding and ability to adapt your solution to variations.

🔍

Pattern Recognition

When to Use

1) Asked for longest subsequence with alternating up/down differences; 2) Differences strictly alternate signs; 3) Subsequence (not substring) allowed; 4) Input size large enough to require O(n) solution.

Signature Phrases

'differences between successive numbers strictly alternate''longest wiggle subsequence'

NOT This Pattern When

Problems asking for contiguous alternating sequences or maximum sum subsequences are different patterns.

Similar Problems

Longest Increasing Subsequence - also about subsequences but monotonicLongest Alternating Subsequence - similar alternating patternZigzag Conversion - pattern recognition in sequences

Practice

1. Consider the following BFS-based jump function. What is the returned value when calling jump([2,1,1,1,4])?

easy

A. 3

B. 2

C. 4

D. 1

Solution

1. Step 1: Trace first BFS level

   Start at index 0 with jump length 2, enqueue indices 1 and 2, jumps = 1.

2. Step 2: Trace second BFS level

   From indices 1 and 2, enqueue reachable indices: from 1 (jump 1) -> 2 (visited), from 2 (jump 1) -> 3, jumps = 2.

3. Step 3: Trace third BFS level

   From index 3 (jump 1), enqueue index 4 (last index), jumps = 3, return 3.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Minimum jumps to reach end is 3 [OK]

Hint: Count BFS levels until last index reached [OK]

Common Mistakes:

• Off-by-one error in counting jumps
• Returning jumps too early
• Miscounting reachable indices

2. Consider the following Python code that computes the minimum cost to connect sticks using a min-heap. What is the value of total_cost returned when the input is [1, 8, 3, 5]?

easy

A. 30

B. 36

C. 33

D. 29

Solution

1. Step 1: Trace initial heap and first merge

   Heapify sticks: [1,3,5,8]. Pop 1 and 3 -> cost=4, total_cost=4. Push 4 back -> heap: [4,5,8]

2. Step 2: Trace second and third merges

   Pop 4 and 5 -> cost=9, total_cost=13. Push 9 -> heap: [8,9]. Pop 8 and 9 -> cost=17, total_cost=30. Push 17 -> heap: [17]. Loop ends.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Sum of merges: 4 + 9 + 17 = 30 [OK]

Hint: Sum merges stepwise using min-heap pops [OK]

Common Mistakes:

• Adding costs incorrectly or missing last merge
• Confusing heap order or popping wrong elements
• Off-by-one in loop iterations

3. What is the worst-case time complexity of the BFS-based solution for Jump Game II on an input array of length n?

medium

A. O(n^2)

B. O(n)

C. O(n log n)

D. O(n^3)

Solution

1. Step 1: Identify outer and inner loops

   The BFS processes each index once, but for each index, it may enqueue up to nums[pos] next positions, which can be up to n.

2. Step 2: Analyze nested iteration

   In worst case (e.g., nums[i] = n for all i), inner loop runs O(n) times for each of O(n) indices -> O(n^2) total.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Nested loops over n indices and jumps -> O(n^2) [OK]

Hint: Nested loops over n indices and jumps -> O(n^2) [OK]

Common Mistakes:

• Assuming BFS is always O(n)
• Confusing with greedy linear time
• Ignoring inner loop over jump range

4. What is the time complexity of the optimal greedy algorithm that finds the largest monotone increasing digits number less than or equal to n, where d is the number of digits in n?

medium

A. O(d), since it scans digits once from right to left and then sets trailing digits

B. O(log n), since the number of digits d is proportional to log n

C. O(d^2), because each decrement may cause re-checking previous digits multiple times

D. O(n * d), where n is the input number and d is the number of digits

Solution

1. Step 1: Understand the relationship between digits and input size

   The number of digits d in n is proportional to log₁₀ n.

2. Step 2: Express complexity in terms of n

   The algorithm runs in O(d) time, which is O(log n) when expressed in terms of n.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Expressing complexity in terms of n, O(log n) is correct and more standard [OK]

Hint: Algorithm runs in linear time relative to digit count, which is logarithmic in n [OK]

Common Mistakes:

• Confusing input size n with digit count d
• Assuming repeated decrements cause quadratic time
• Ignoring that digit count is log n

5. Identify the bug in the following code snippet for Two City Scheduling:

def twoCitySchedCost(costs):
    costs.sort(key=lambda x: abs(x[0] - x[1]))
    n = len(costs) // 2
    total = 0
    for i, cost in enumerate(costs):
        if i < n:
            total += cost[0]
        else:
            total += cost[1]
    return total

medium

A. Sorting by absolute difference instead of signed difference

B. Incorrect calculation of n as half the length

C. Adding cost[1] for the first half instead of cost[0]

D. Using enumerate instead of a simple for loop

Solution

1. Step 1: Analyze sorting key

   The code sorts by absolute difference abs(cost[0] - cost[1]) instead of signed difference cost[0] - cost[1].

2. Step 2: Effect of wrong sorting

   Sorting by absolute difference loses the direction of cost preference, causing suboptimal assignments and higher total cost.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Signed difference sorting is required for correct greedy assignment [OK]

Hint: Sort by signed difference, not absolute [OK]

Common Mistakes:

• Sorting by absolute difference
• Miscounting half the people
• Swapping city costs in assignment