Skip to main content

Wiggle Sort II

LeetCode 324 | Difficulty: Medium​

Medium

Problem Description​

Given an integer array nums, reorder it such that nums[0] nums[2] < nums[3]....

You may assume the input array always has a valid answer.

Example 1:

Input: nums = [1,5,1,1,6,4]
Output: [1,6,1,5,1,4]
Explanation: [1,4,1,5,1,6] is also accepted.

Example 2:

Input: nums = [1,3,2,2,3,1]
Output: [2,3,1,3,1,2]

Constraints:

- `1 <= nums.length <= 5 * 10^4`

- `0 <= nums[i] <= 5000`

- It is guaranteed that there will be an answer for the given input `nums`.

Follow Up: Can you do it in O(n) time and/or in-place with O(1) extra space?

Topics: Array, Divide and Conquer, Greedy, Sorting, Quickselect

Approach​

Greedy​

At each step, make the locally optimal choice. The challenge is proving the greedy choice leads to a global optimum. Look for: can I sort by some criterion? Does choosing the best option now ever hurt future choices?

When to use

Interval scheduling, activity selection, minimum coins (certain denominations), Huffman coding.

Solutions​

Solution 1: C# (Best: 175 ms)​

MetricValue
Runtime175 ms
Memory45 MB
Date2022-01-25
Solution
public class Solution {
    public void WiggleSort(int[] nums) {
        int[] copy = new int[nums.Length];
        nums.CopyTo(copy, 0);
        Array.Sort(copy);
        
        int n = nums.Length;
        int left = (n+1)/2-1;
        int right = n-1;
        for(int i=0;i<n;i++)
        {
            if(i%2 == 1)
            {
                nums[i] = copy[right];
                right--;
            }
            else
            {
                nums[i] = copy[left];
                left--;
            }
        }
    }
}

Complexity Analysis​

ApproachTimeSpace
Sort + Process$O(n log n)$$O(1) to O(n)$

Interview Tips​

Key Points
  • Discuss the brute force approach first, then optimize. Explain your thought process.