3 lines Python, with Explanation / Proof


  • 115

    Solution

    Roughly speaking I put the smaller half of the numbers on the even indexes and the larger half on the odd indexes.

    def wiggleSort(self, nums):
        nums.sort()
        half = len(nums[::2])
        nums[::2], nums[1::2] = nums[:half][::-1], nums[half:][::-1]
    

    Alternative, maybe nicer, maybe not:

    def wiggleSort(self, nums):
        nums.sort()
        half = len(nums[::2]) - 1
        nums[::2], nums[1::2] = nums[half::-1], nums[:half:-1]
    

    Explanation / Proof

    I put the smaller half of the numbers on the even indexes and the larger half on the odd indexes, both from right to left:

    Example nums = [1,2,...,7]      Example nums = [1,2,...,8] 
    
    Small half:  4 . 3 . 2 . 1      Small half:  4 . 3 . 2 . 1 .
    Large half:  . 7 . 6 . 5 .      Large half:  . 8 . 7 . 6 . 5
    --------------------------      --------------------------
    Together:    4 7 3 6 2 5 1      Together:    4 8 3 7 2 6 1 5
    

    I want:

    • Odd-index numbers are larger than their neighbors.

    Since I put the larger numbers on the odd indexes, clearly I already have:

    • Odd-index numbers are larger than or equal to their neighbors.

    Could they be "equal to"? That would require some number M to appear both in the smaller and the larger half. It would be the largest in the smaller half and the smallest in the larger half. Examples again, where S means some number smaller than M and L means some number larger than M.

    Small half:  M . S . S . S      Small half:  M . S . S . S .
    Large half:  . L . L . M .      Large half:  . L . L . L . M
    --------------------------      --------------------------
    Together:    M L S L S M S      Together:    M L S L S L S M
    

    You can see the two M are quite far apart. Of course M could appear more than just twice, for example:

    Small half:  M . M . S . S      Small half:  M . S . S . S .
    Large half:  . L . L . M .      Large half:  . L . M . M . M
    --------------------------      --------------------------
    Together:    M L M L S M S      Together:    M L S M S M S M
    

    You can see that with seven numbers, three M are no problem. And with eight numbers, four M are no problem. Should be easy to see that in general, with n numbers, floor(n/2) times M is no problem. Now, if there were more M than that, then my method would fail. But... it would also be impossible:

    • If n is even, then having more than n/2 times the same number clearly is unsolvable, because you'd have to put two of them next to each other, no matter how you arrange them.
    • If n is odd, then the only way to successfully arrange a number appearing more than floor(n/2) times is if it appears exactly floor(n/2)+1 times and you put them on all the even indexes. And to have the wiggle-property, all the other numbers would have to be larger. But then we wouldn't have an M in both the smaller and the larger half.

    So if the input has a valid answer at all, then my code will find one.


  • 8
    B

    sort takes at least n*logn time


  • 0

    @berlino That's not true (for example, if the list is sorted already, then sort will detect that and only use linear time). Also, what's your point?


  • 0
    P

    I believe berlino is implying the O(n) time complexity solution.

    Anyway, very clean code ;)


  • 0
    Y

    +1 for great explanation by @StefanPochmann, same question as @berlino here. can we divide numbers into the smaller and larger half with O(n) time and O(1) space?


  • 0

    @yanggao Yes, find a median with median of medians, and then use three-way partitioning. You can even do the latter so that the numbers directly arrive at their final destinations, as I just showed here.


  • 0
    S

    @StefanPochmann If the list is not sorted then what is the complexity of sorting function here and what is over all complexity? Wouldn't that be O(n*logn)?


  • 0

    @SATM Yes, it's O(n*logn).


  • 5
    H

    Thank you for your solution! And I give the Java version of this thought:

    public void wiggleSort(int[] nums) {
        Arrays.sort(nums);
        for(int i = 0; i < nums.length/2; ++i ) { 
            int temp = nums[i]; 
            nums[i] = nums[nums.length - i - 1]; 
            nums[nums.length - i - 1] = temp; 
        }
        int half = nums.length / 2;
        int[] large = Arrays.copyOfRange(nums, 0, half);
        int[] small = Arrays.copyOfRange(nums, half, nums.length);
    
        for (int i = 0, j = 0, k = 0; i < nums.length; i++) {
            if (i % 2 == 0)
                nums[i] = small[j++];
            else
                nums[i] = large[k++];
        }
    }
    

  • 0
    Q

    This can be simplified

    
    public void wiggleSort(int[] nums) {
            Arrays.sort(nums);
            int[] copy = Arrays.copyOf(nums, nums.length);
            int smallEndIndex = (nums.length+1)/2-1;
            int largeEndIndex = nums.length-1;
            for (int i=0;i<nums.length;i++)
                nums[i] = i%2==0?copy[smallEndIndex-i/2]:copy[largeEndIndex-i/2];
        }
    </code>
    

  • 0

    @qgambit2
    Playing with that a bit more:

                nums[i] = i%2==0?copy[smallEndIndex-i/2]:copy[largeEndIndex-i/2];
                nums[i] = copy[i%2==0?smallEndIndex-i/2:largeEndIndex-i/2];
                nums[i] = copy[(i%2==0?smallEndIndex:largeEndIndex)-i/2];
    

    Or:

            int[] ends = {(nums.length+1)/2-1, nums.length-1};
            for (int i=0;i<nums.length;i++)
                nums[i] = copy[ends[i%2]-i/2];
    

  • 0
    N

    "Roughly speaking I put the smaller half of the numbers on the even indexes and the larger half on the odd indexes"(in the beginning of Solution)
    "I put the smaller half of the numbers on the odd indexes and the larger half on the even indexes, both from right to left" (in the beginning of Proof)
    type error? By the way, great idea, thank u.


  • 0

    Oh wow, how did that happen and nobody noticed until now :-)... thanks, fixed.


  • 0
    N

    Hi,
    So how can [4,5,5,6] pass the test if you are using this solution? Since small half will be 4,5 and the bigger one will be 5,6


  • 0
    This post is deleted!

  • 0

    @nguyli03 It leaves [5,6,4,5]. Is there a problem with that?


  • 0
    M

    simple yet powerful explanation, thank you


  • 0
    Z

    So this is O(n) extra space?


  • 0
    K

    @StefanPochmann What do you mean by the last sentence? "But then we wouldn't have an M in both the smaller and the larger half."
    I think it is possible that n is odd and M appears exactly floor(n/2)+1 times. Your method still works well in this circumstance.


  • 0

    @Kay77 I mean a situation like M=3 and the smaller half being {3,3,3} and the larger half being {4,5}, where M is only in the smaller half.


Log in to reply
 

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