This content originally appeared on Level Up Coding - Medium and was authored by Sourav Saikia
March LeetCoding Challenge 2021 — Day 18: Wiggle Subsequence
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
Check out my other posts on March LeetCoding Challenge 2021.
- March LeetCoding Challenge — Day 1 — Distribute Candies
- March LeetCoding Challenge — Day 2 — Set Mismatch
- March LeetCoding Challenge — Day 3 — Missing Number
- 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 7 — Design HashMap
- March LeetCoding Challenge — Day 8 — Remove Palindromic Subsequences
- March LeetCoding Challenge — Day 10 — Integer to Roman
- 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
March LeetCoding Challenge 2021 — Day 18: Wiggle Subsequence was originally published in Level Up Coding on Medium, where people are continuing the conversation by highlighting and responding to this story.
This content originally appeared on Level Up Coding - Medium and was authored by Sourav Saikia
Sourav Saikia | Sciencx (2021-03-20T23:52:19+00:00) March LeetCoding Challenge 2021 — Day 18: Wiggle Subsequence. Retrieved from https://www.scien.cx/2021/03/20/march-leetcoding-challenge-2021%e2%80%8a-%e2%80%8aday-18-wiggle-subsequence/
Please log in to upload a file.
There are no updates yet.
Click the Upload button above to add an update.