Simple O(n) C# solution with constant storage and explanation


  • 0
    W

    My solution takes advantage of the underlying concept in this problem that removing values will not increase the wiggle count, and instead what is important is the number of changes between negative/positive.

    Take for example the following sequence: 1,4,7,2,5
    This has the difference sequence of: 3,3,-5,3
    If we remove 7, we combine the differences around it, so the 3 and -5 combine to yield this new sequence: 3,-2,3
    Notice how we didn't gain any wiggles. If you keep testing examples, you'll see that you can never add wiggles by removing elements, but will only remove wiggles.

    Now, take for example the following example sequence: 1,1,3,3,4
    If we look at the differences, we see: 0,+,0,+
    Zero differences do not contribute to the wiggle count, so we can effectively reduce this difference sequence to: +, which has a count of 2 (wiggle from 1 to 4).

    Taking these two insights into account, all one needs to do is increment the count whenever the state changes from zero to anything or between positive/negative, so here is my code:

    public enum State{
        Positive,
        Zero,
        Negative
    }
    public int WiggleMaxLength(int[] nums) {
        if (nums.Length < 2) return nums.Length;
        
        var prevailingState = State.Positive;
        var count = 2;
        if (nums[1] == nums[0]) {
            prevailingState = State.Zero;
            count = 1;
        }
        else if (nums[1] < nums[0]) 
            prevailingState = State.Negative;
        
        for(int i=2;i<nums.Length;i++) {
            if(nums[i] == nums[i-1]) continue;
            var curState = State.Positive;
            if(nums[i] < nums[i-1]) curState = State.Negative;
            if(curState != prevailingState) {
                count++;
                prevailingState = curState;
            }
        }
        
        return count;
    }
    

Log in to reply
 

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