Wiggle Subsequence – LeetCode Solution Java , Python 3, Python 2 , C , C++, Best and Optimal Solutions , All you need.
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 one element and a sequence with two non-equal elements are trivially wiggle sequences.
- For example,
[1, 7, 4, 9, 2, 5]
is a wiggle sequence because the differences(6, -3, 5, -7, 3)
alternate between positive and negative. - In contrast,
[1, 4, 7, 2, 5]
and[1, 7, 4, 5, 5]
are not wiggle sequences. The first is not because its first two differences are positive, and the second is not because its last difference is zero.
A subsequence is obtained by deleting some elements (possibly zero) from the original sequence, leaving the remaining elements in their original order.
Given an integer array nums
, return the length of the longest wiggle subsequence of nums
.
Example 1:
Input: nums = [1,7,4,9,2,5] Output: 6 Explanation: The entire sequence is a wiggle sequence with differences (6, -3, 5, -7, 3).
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] with differences (16, -7, 3, -3, 6, -8).
Example 3:
Input: nums = [1,2,3,4,5,6,7,8,9] Output: 2
Constraints:
1 <= nums.length <= 1000
0 <= nums[i] <= 1000
C++ Wiggle Subsequence LeetCode Solution
class Solution {
public:
int wiggleMaxLength(vector<int>& nums) {
int size=nums.size(), peak=1, valley=1;
for(int i=1; i<size; ++i){
if(nums[i]>nums[i-1]) peak = valley + 1;
else if(nums[i]<nums[i-1]) valley = peak + 1;
}
return max(peak , valley );
}
};
Java Wiggle Subsequence LeetCode Solution
public class Solution {
public int wiggleMaxLength(int[] nums) {
if (nums.length == 0 || nums.length == 1) {
return nums.length;
}
int k = 0;
while (k < nums.length - 1 && nums[k] == nums[k + 1]) { //Skips all the same numbers from series beginning eg 5, 5, 5, 1
k++;
}
if (k == nums.length - 1) {
return 1;
}
int result = 2; // This will track the result of result array
boolean smallReq = nums[k] < nums[k + 1]; //To check series starting pattern
for (int i = k + 1; i < nums.length - 1; i++) {
if (smallReq && nums[i + 1] < nums[i]) {
nums[result] = nums[i + 1];
result++;
smallReq = !smallReq; //Toggle the requirement from small to big number
} else {
if (!smallReq && nums[i + 1] > nums[i]) {
nums[result] = nums[i + 1];
result++;
smallReq = !smallReq; //Toggle the requirement from big to small number
}
}
}
return result;
}
}
Python 3 Wiggle Subsequence LeetCode Solution
class Solution:
def wiggleMaxLength(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
if not nums:
return 0
length = 1
up = None # current is increasing or not
for i in range(1, len(nums)):
if nums[i] > nums[i - 1] and up != True:
length += 1
up = True
if nums[i] < nums[i - 1] and up != False:
length += 1
up = False
return length
Array-1180
String-562
Hash Table-412
Dynamic Programming-390
Math-368
Sorting-264
Greedy-257
Depth-First Search-256
Database-215
Breadth-First Search-200
Tree-195
Binary Search-191
Matrix-176
Binary Tree-160
Two Pointers-151
Bit Manipulation-140
Stack-133
Heap (Priority Queue)-117
Design-116
Graph-108
Simulation-103
Prefix Sum-96
Backtracking-92
Counting-86
Sliding Window-73
Linked List-69
Union Find-66
Ordered Set-48
Monotonic Stack-47
Recursion-43
Trie-41
Binary Search Tree-40
Divide and Conquer-40
Enumeration-39
Bitmask-37
Queue-33
Memoization-32
Topological Sort-31
Geometry-30
Segment Tree-27
Game Theory-24
Hash Function-24
Binary Indexed Tree-21
Interactive-18
Data Stream-17
String Matching-17
Rolling Hash-17
Shortest Path-16
Number Theory-16
Combinatorics-15
Randomized-12
Monotonic Queue-9
Iterator-9
Merge Sort-9
Concurrency-9
Doubly-Linked List-8
Brainteaser-8
Probability and Statistics-7
Quickselect-7
Bucket Sort-6
Suffix Array-6
Minimum Spanning Tree-5
Counting Sort-5
Shell-4
Line Sweep-4
Reservoir Sampling-4
Eulerian Circuit-3
Radix Sort-3
Strongly Connected Componen-t2
Rejection Sampling-2
Biconnected Component-1