leetcode dp wiggle subsequence

A sequence of numbers is called a wiggle sequence if 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.

Given a sequence of integers, return the length of the longest subsequence that is a wiggle sequence. A subsequence is obtained by deleting some number of elements (eventually, also zero) from the original sequence, leaving the remaining elements in their original order.

In Wiggle Subsequence, think that the solution we need should be in a way that we get alternative higher, lower,higher number.
Eg: 2, 5, 3, 8, 6, 9
In above example, the sequence of numbers is small,big,small,big,small,big numbers (In shape of hill).

Now for explanation, we take example series:
2,1,4,5,6,3,3,4,8,4

First we check if the series is starting as (big, small) or (small, big). So as 2,1 is big, small. So we will start the loop as we need small number first that is 1 as 2 is already there.

Step 1: First we check our requirement is to get small number. As 1<2 4="" so="" the="" series="" will="" be="" 2,1="" step="" 2:="" now="" we="" need="" big="" number="" that="" is="" greater="" than="" 1.="" as="">1 so series will be
2,1,4
Step 3: Now we need small number. But 5>4 so 4 will be replaced by 5. So the series will become
2,1,5
Step 4: We need small number. But 6>5. Series will be
2,1,6
Step 5: Require small number. 3<6. 3="3." 4="" series="" will="" be="" 2,1,6,3="" step="" 6:="" require="" big="" number.="" no="" change="" in="" 7:="">3. Series will become
2,1,6,3,4
Step 8: Require small number. 8>4. 8 will replace 4 and series will become
2,1,6,3,8
Step 9: Require small number. 4<8. So final series will be
2,1,6,3,8,4
Answer is 6.

In the code, for constant space O(1) we will modify the same ‘num’ array to store the (small, big, small) hill shape values. So the code will not only calculate the length of the sequence but if the interviewers asks for the Wiggle series also then we can return the series too. The leetcode Online Judge skipped a test case if the series starts with same set of numbers. Thanks to @ztq63830398, modified the code to consider that test case also.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

public class  {
	public int wiggleMaxLength(int[] nums) {
		if (nums.length == 0 || nums.length == 1) {
			return nums.length;
		}
		int k = 0;
		//Skips all the same numbers from series beginning eg 5, 5, 5, 1
		while (k < nums.length - 1 && nums[k] == nums[k + 1]) {  
			k++;
		}
		if (k == nums.length - 1) {
			return 1;
		}
		int result = 2;     // This will track the result of result array
		//To check series starting pattern
		boolean smallReq = nums[k] < nums[k + 1];       
		for (int i = k + 1; i < nums.length - 1; i++) {
			if (smallReq && nums[i + 1] < nums[i]) {
				nums[result] = nums[i + 1];
				result++;
				//Toggle the requirement from small to big number
				smallReq = !smallReq;    
			} else {
				if (!smallReq && nums[i + 1] > nums[i]) {
					nums[result] = nums[i + 1];
					result++;
					//Toggle the requirement from big to small number
					smallReq = !smallReq;    
				}
			}
		}
		return result;
	}
}