Today, we will solve the 18th problem of the March LeetCoding Challenge.

Problem Statement

Given an integer array nums, return the length of the longest **wiggle sequence**.

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 fewer than two elements is trivially a wiggle sequence.

• For example, [1, 7, 4, 9, 2, 5] is a wiggle sequence because the differences (6, -3, 5, -7, 3) are alternately positive and negative.

• In contrast, [1, 4, 7, 2, 5] and [1, 7, 4, 5, 5] are not wiggle sequences, the first because its first two differences are positive and the second because its last difference is zero.

A subsequence is obtained by deleting some elements (eventually, also zero) from the original sequence, leaving the remaining elements in their original order.

Example 1:

**Input:** nums = [1,7,4,9,2,5]
**Output:** 6
**Explanation:** The entire sequence is a wiggle sequence.

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].

Example 3:

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

Solution

With this problem, we have to find the longest wiggle subsequence. Wiggle subsequence means that the difference between successive elements is alternating between positive and negative.

For solving this problem we will use dynamic programming. We will go through two approaches, one with O(n²) and another one with O(n).

Approach 1: We will use two arrays up and down. up array refers to the length of the longest wiggle subsequence where the ending element is a rising wiggle. Similarly, the down array refers to the length of the longest wiggle subsequence where the ending element is a falling wiggle.

We will update the up[i] when we find a rising wiggle at index i. But there is a catch. We have to consider the previous wiggle subsequence which ends with a falling wiggle (because we need to make sure that the subsequence overall is wiggle). We follow the same in the case of down[i].

The code is given below.

Here we are using two loops. To check the longest wiggle subsequence at index i , we check for each element from 0 to i-1.

Time complexity: O(n²), n is the length of the array

Space complexity: O(n), n is the length of the array

Approach 2: With this approach, we only use a single loop and two arrays named up and down. Here, we have 3 cases.

• When nums[i]>nums[i-1]:it means it wiggles up. So the element before it must be in down position. Therefore, up[i] = down[i-1]+1 and down[i] will be same as down[i-1].

• When nums[i]<nums[i-1]: it means the wiggles down, the element before it must be in up position. Therefore down[i] = 1+up[i-1] and up[i] will be same as up[i-1].

• If nums[i]=nums[i-1],then up[i] will be up[i-1] and down[i] will be down[i-1].

The code is given below.

Space complexity: O(n), n is the length of the array

The code can be found here

Check out my other posts on March LeetCoding Challenge 2021.

1. March LeetCoding Challenge — Day 1 — Distribute Candies

2. March LeetCoding Challenge — Day 2 — Set Mismatch

3. March LeetCoding Challenge — Day 3 — Missing Number

4. March LeetCoding Challenge — Day 4 — Intersection of Two Linked Lists

5. March LeetCoding Challenge — Day 5 — Average of Levels in Binary Tree

6. March LeetCoding Challenge — Day 6 — Short Encoding of Words

7. March LeetCoding Challenge — Day 7 — Design HashMap

8. March LeetCoding Challenge — Day 8 — Remove Palindromic Subsequences

9. March LeetCoding Challenge — Day 10 — Integer to Roman

10. March LeetCoding Challenge — Day 12 — Check If a String Contains All Binary Codes of Size K

11. March LeetCoding Challenge — Day 14 — Swapping Nodes in a Linked List

12. March LeetCoding Challenge — Day 15 — Encode and Decode TinyURL