Very Simple Java Solution with detail explanation


  • 58
    K

    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 so the series will be
     2,1
    
    Step 2: Now we need big number that is  greater than 1. As 4>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. Series will be
    2,1,6,3
    
    Step 6: Require big number. 3=3. No change in series
    2,1,6,3
    
    Step 7: Require big number. 4>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.

    Code:

        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;
    	}
    }
    

  • 28
    M

    Using same logic, little bit cleaner code with better var naming.

        public int wiggleMaxLength(int[] a) {
           if(a.length<2)
                return a.length;
           int maxLen=1;
           boolean increasing = a[1]>a[0];
           int prev = a[0];
           
           for(int i=1; i<a.length; i++){
               if(increasing){
                   if(a[i] >prev){
                       increasing = !increasing;
                       maxLen++;
                   }
               } else {
                   if(a[i] < prev){
                       increasing = !increasing;
                       maxLen++;
                   }
               }
               prev = a[i];
           }
           return maxLen;
        }
    

    The above no longer gets accepted. Here is new code that copes with equal values at beginning. Thanks to @Dangna for hints:

    public int wiggleMaxLength(int[] a) {
           if(a.length<2) return a.length;
           
           int start=1;
           while( (start<a.length) && (a[start] == a[start-1]) )
               start++;
           if(start==a.length)
                return 1;
            
           boolean increasing = a[start]>a[0];   // denoting if we are expecting increased relative to prev
           int prev = a[0], maxLen=1;
           for(int i=start; i<a.length; i++){
               if ( (increasing && (a[i] >prev)) || (!increasing && (a[i] < prev) ) ) {
                       increasing = !increasing;
                       maxLen++;
               }
               prev = a[i];
           }
           return maxLen;
      }
    

  • 7
    M

    Thanks for the logic. Tried to make it concise.

    public class Solution {
        public int wiggleMaxLength(int[] nums) {
            if (nums.length <= 1) return nums.length;
            int count = 1;
            boolean big = (nums[0] < nums[1]);
            for (int i=1;i<nums.length;i++){
                if((big && nums[i] > nums[i-1]) || (!big && nums[i] < nums[i-1])){
                    count ++;
                    big = !big;
                }
            }
            return count;
        }
    }

  • 18
    Z

    I think the sequence may be 3, 3, 3, 2, 5 and the answer will be wrong in this condition. But this is not included in the test cases.
    So I made the following solution:

            if(nums.length <= 1)
                return nums.length;
            int k = 1;
            while(k<nums.length && nums[k] == nums[k-1]) k++;
            if(k == nums.length)
                return 1;
            int maxLen = 2;
            boolean isIncreasing = nums[k] > nums[k-1];
            for(int i=k+1; i<nums.length; i++) {
                if(isIncreasing && nums[i] < nums[i-1]) {
                    maxLen++;
                    isIncreasing = false;
                } else if(!isIncreasing && nums[i] > nums[i-1]) {
                    maxLen++;
                    isIncreasing = true;
                }
            }
            
            return maxLen;
    

  • 0

    @ztq63830398 Thanks, I have added your test case.


  • 0
    S

    @ztq63830398 Yeah, that test case was not included. Good job!


  • 0
    G
    This post is deleted!

  • 1
    C

    @mmozum nice solution


  • 3
    Y

    shortened @ztq63830398 's solution a bit, the if clause inside the for loop can be combined.

    public int wiggleMaxLength(int[] nums) {
        if (nums.length <= 1) {
            return nums.length;
        }
        
        int k = 1;
        int maxLen = 2;
        
        while (k < nums.length && nums[k] == nums[k - 1]) {
            k++;
        }
        if (k == nums.length) {
            return 1;
        }
        
        boolean isIncreasing = nums[k] > nums[k - 1];
        
        for (int i = k + 1; i < nums.length; i++) {
            if ((isIncreasing && nums[i] < nums[i - 1]) || (!isIncreasing && nums[i] > nums[i - 1])) {
                maxLen++;
                isIncreasing = !isIncreasing;
            }
        }
        
        return maxLen;
    }

  • 2
    C

    While the length is correct, I think the for loop should be modified to achieve the purpose of getting the wiggle sequence

    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
    	}
    	else nums[result - 1] = nums[i + 1];
    }
    

  • 1
    D

    @mmozum so smart


  • 1
    L

    How do we prove it will create the longest subsequence?


  • 0
    This post is deleted!

  • 0
    Y

    Hi

    I used this test case, and confused about the answer.

    Test case : 1 17 5 10 13 15 10 5 9 8
    The run result i got is 7, but I think it's not correct, it should be 5, please help me analysis this test case, thx.


  • 0
    S

    @mmozum said in Very Simple Java Solution with detail explanation:

    public int wiggleMaxLength(int[] a) {
    if(a.length<2)
    return a.length;
    int maxLen=1;
    boolean increasing = a[1]>a[0];
    int prev = a[0];

       for(int i=1; i<a.length; i++){
           if(increasing){
               if(a[i] >prev){
                   increasing = !increasing;
                   maxLen++;
               }
           } else {
               if(a[i] < prev){
                   increasing = !increasing;
                   maxLen++;
               }
           }
           prev = a[i];
       }
       return maxLen;
    }
    

    While this is accepted, it does not consider the case a[0] == a[1]. For example, given test case [1,1,7,4,9,2,5], result should be 6, but the result given by this code is 5.


  • 0

    @sangyezi Thanks, I have just added your test case.


  • 0
    T

    According to your code, the test case [1,17,5,10,13,15,10,5,16,8] will return [1,17,5,15,10,16,8], also is 7 length. The test example is [1,17,10,13,10,16,8], so how do you prove your result is longest sequence?


  • 0
    S

    @msabhi
    [1,1,7,4,9,2,5]
    this case got WA


  • 1

    @mmozum this solution won't handle the situation where the sequence includes two consecutive equal numbers. For example: [1,1,7,4,9,2,5]


  • 0
    B

    @mmozum your code gets some cases wrong. Ex:[3,3,3,4,2] your answer:2 correct answer:3. It's necessary to deal with cases that start by some equal elements.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.