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
Top comments (0)