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.

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

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

The code can be found here

# LeetCode

I have been solving Leetcode problems for around a year or so. Suddenly I have developed a passion of writing tutorials for these problems. I am starting with Leetcode problem, in future I will try to make tutorials on Spring,Android,Java,Algorithms and many more.

Follow me on medium - https://sourav-saikia.medium.com

Follow me on dev.to - https://dev.to/sksaikia

Follow me on twitter - https://twitter.com/sourav__saikia

Connect on Linkedin - www.linkedin.com/in/sourav-kumar-saikia

The following table contains all the problems with their respective solution tutorials. I will try to add more articles to it soon.

Problem Name | Problem No | Article Links |
---|---|---|

Contains Duplicate | 217 | https://sourav-saikia.medium.com/leetcode-217-contains-duplicate-solution-36f48793bce0 |

Jewels and Stones | 771 | https://sourav-saikia.medium.com/leetcode-771-jewels-and-stones-e35a368fc37 |

## March LeetCoding Challenge

Problem Name | Problem No | Article Links |
---|---|---|

Distribute Candies | 575 | https://medium.com/dev-genius/march-leetcoding-challenge-2021-problem-1-distribute-candies-f37f66ea7ee9 |

Set Mismatch | 645 | https://sourav-saikia.medium.com/march-leetcoding-challenge-2021-day-2-set-mismatch-4abd5ee491c9 |

Missing Number | 268 | https://sourav-saikia.medium.com/march-leetcoding-challenge-2021-day-3-missing-number-ae8ee45a58cb |

Intersection of Two Linked Lists | 160 | https://sourav-saikia.medium.com/march-leetcoding-challenge-2021-day-4-intersection-of-two-linked-lists-a775449b5563 |

Average of Levels in Binary Tree | 637 | https://medium.com/dev-genius/march-leetcoding-challenge-2021-day-5-average-of-levels-in-binary-tree-ac886b2b42e8 |

Short Encoding of Words | 820 | https://sourav-saikia.medium.com/march-leetcoding-challenge-2021-day-6-short-encoding-of-words-7fed4bfae557 |

Remove Palindromic Subsequences | 1332 |

Check out my other posts on March LeetCoding Challenge 2021.

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

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

March LeetCoding Challenge — Day 6 — Short Encoding of Words

March LeetCoding Challenge — Day 8 — Remove Palindromic Subsequences

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

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

March LeetCoding Challenge — Day 15 — Encode and Decode TinyURL

## Discussion (0)