## DEV Community is a community of 698,340 amazing developers

We're a place where coders share, stay up-to-date and grow their careers. # March LeetCoding Challenge 2021 — Day 18: Wiggle Subsequence Sourav
I am just a simple man making his way through the galaxy.

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