Simple Java Solution with O(n) order run time 2ms ,detailed explanation


  • 0
    G

    Idea is to use List and array as a placeholder to keep the data as we keep progressing

    One placeholder will keep the difference as we encounter and as long as it is zig zag format
    as soon as we find any 2 consecutive difference are positive or negative we ignore that element

    As long as we are good we keep adding difference in wiggleCount and keep incrementing counter length.
    However on exception (2 consecutive positives or negatives we realize subsequence end is reached so we put the value of length into an array .
    We put one special if condition when difference is 0 also.

    We keep adding length into array
    After that we sort the array and get maximum value from the tail
    ...

     // boundary case if nums is null or blank then we simply return 0
    	if(nums==null || nums.length==0) {
    		return 0;
    	}
    	
    	// now create an arrayList of Integers we will use this as a placeholder , In the sense that if difference is 
       //  positive we store 0 and if difference is negative we store 1 . more explanation when logic comes
    	List <Integer> wiggleCount = new ArrayList<Integer>();
      // if list contains even 1 element we have to return 1 as default so initialize length as 1
    	int length=1;
    
      //  Initialize array to store the value of counter till we found that zig zag is not happening and we are done
      // we initialize it to size of input array to be on safe side as value of this array has to be less than this
     	int arrays[] = new int[nums.length];
    	int arrayIndex=0;
    	for(int a=0;a<nums.length;a++) {
    		// nothing to do with 1st element
    		if(a==0) {
    			continue;
    		}
    
           // get current elment and previous element and the difference
    		int curElement = nums[a];
    		int prevElement = nums[a-1];    		
    		int diff = curElement-prevElement;
    		
    		// if list is not empty 
    		if(wiggleCount.size()>0) {
                      // get previous computed difference from list
    			int prevDiff = wiggleCount.get(wiggleCount.size()-1);
    			//ignore if cur diff and prevDiff are same for positive number we store 0 and for negative we 
                        // we store 1 and if any 2 diff are of same sign we ignore
    			if((prevDiff<0 && diff<0) || (prevDiff==0 && diff> 0)) {
    				continue;
    			}
    		}
    		
    
                   // Here we add the difference to wiggleCount array ,as explained that for negative it is -1
                   //   and for   positive 0.
    		if(diff<0) {
    			wiggleCount.add(-1);
    		} else if(diff==0) {
    			continue;
    		}
    		
    		else {
    			wiggleCount.add(0);
    		}
    
    		++length;
    	}
    	
    	if(length>0) {
    		arrays[arrayIndex] = length;	
    	}
    	
       // we need max length so we sort the array first
    	Arrays.sort(arrays);
     // return maximum length from the tail of array
    	return arrays[arrays.length-1];
    

    ...


Log in to reply
 

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