Easy Java | O(N) | Tiny


  • 0
    A

    Idea:

    1. Remove duplicate elements from the array.
    2. Now any three numbers are in Wiggle Subsequence when:
      a) nums[i] - nums[i-1] > 0 && nums[i-1] - nums[i-2] < 0 or,
      b) nums[i] - nums[i-1] < 0 && nums[i-1] - nums[i-2] > 0 or,

    We can just write: ((nums[i-1] - nums[i-2]) * (nums[i] - nums[i-1]) < 0)
    If the signs are different, the numbers comply the above criteria.

    public int wiggleMaxLength(int[] nums) {
            if(nums.length <= 1) return nums.length;
            
            int index = 1;
            for(int i = 1; i < nums.length; i++) 
                if(nums[i] != nums[i-1]) nums[index++] = nums[i];
            
            int count = (index >= 2 ) ? 2 : index;
            for(int i = 2; i < index; i++) 
                if((nums[i-1] - nums[i-2]) * (nums[i] - nums[i-1]) < 0) count++;
            
            return count;
        }

Log in to reply
 

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