What happens if you using median as nums[n//2] without sorting or selecting?

Incorrect median leads to wrong partitioning and failed wiggle property Fix: Find median using quickselect or sort before picking median

What happens if you not handling duplicates properly in partitioning?

Equal elements cluster and break strict inequalities Fix: Use three-way partitioning to separate less than, equal to, and greater than median

What happens if you modifying the array while iterating without adjusting pointers?

Infinite loops or skipped elements during partitioning Fix: Adjust pointers carefully after swaps in three-way partitioning

Interview Prepsort-and-searchmediumGoogleAmazon

Wiggle Sort II

Choose your preparation mode4 modes available

Try It Solution Trace

🎯

Wiggle Sort II

mediumSORT_SEARCHGoogleAmazon

Imagine arranging a line of dancers so that their heights alternate between taller and shorter, creating a visually appealing zigzag pattern.

💡 This problem requires rearranging elements to satisfy a specific alternating order, which can be tricky because naive sorting doesn't guarantee the wiggle property. Beginners often struggle to understand how to place elements to maintain the strict inequalities required. Think of it like weaving two sorted halves of the array together so that the pattern of smaller and larger elements alternates.

📋

Problem Statement

Given an unsorted array nums, reorder it such that nums[0] < nums[1] > nums[2] < nums[3].... Input: An integer array nums. Output: Modify nums in-place to satisfy the wiggle property described.

1 ≤ nums.length ≤ 10^5-10^9 ≤ nums[i] ≤ 10^9

💡

Example

Input"[1, 5, 1, 1, 6, 4]"

Output[1, 6, 1, 5, 1, 4]

After rearrangement, the array satisfies nums[0] < nums[1] > nums[2] < nums[3] > nums[4] < nums[5].

All elements are equal → output is the same array
Array with only one element → output is the same array
Array with two elements → output is sorted to satisfy wiggle
Array with duplicates and multiple median values → correct partitioning needed

⚠️

Common Mistakes

Not using virtual indexing and placing elements directly by index

Wiggle property fails because elements are not properly interleaved

✅ Use virtual indexing to map indices to correct wiggle positions

Using median as nums[n//2] without sorting or selecting

Incorrect median leads to wrong partitioning and failed wiggle property

✅ Find median using quickselect or sort before picking median

Not handling duplicates properly in partitioning

Equal elements cluster and break strict inequalities

✅ Use three-way partitioning to separate less than, equal to, and greater than median

Modifying the array while iterating without adjusting pointers

Infinite loops or skipped elements during partitioning

✅ Adjust pointers carefully after swaps in three-way partitioning

Using extra space unnecessarily in optimal approach

Increased space complexity and possible interview penalty

✅ Implement in-place swaps with virtual indexing

🧠

Brute Force (Sorting and Rearranging with Extra Space)

💡 This approach exists to build intuition by directly sorting and then rearranging elements to meet the wiggle condition, even if it uses extra space and is not optimal. It helps beginners understand the problem by breaking it down into simpler steps.

Intuition

Sort the array, then place the smaller half of elements at even indices and the larger half at odd indices to try to satisfy the wiggle property.

Algorithm

Sort the input array.
Split the sorted array into two halves: smaller and larger.
Place elements from the smaller half at even indices in the result array.
Place elements from the larger half at odd indices in the result array.

💡 The main challenge is understanding how splitting and weaving sorted halves can create the wiggle pattern, even if it uses extra space. This approach is easy to implement and verify.

</>

Code

def wiggleSort(nums):
    n = len(nums)
    sorted_nums = sorted(nums)
    res = [0] * n
    left = (n - 1) // 2
    right = n - 1
    for i in range(n):
        if i % 2 == 0:
            res[i] = sorted_nums[left]
            left -= 1
        else:
            res[i] = sorted_nums[right]
            right -= 1
    for i in range(n):
        nums[i] = res[i]

# Driver code
if __name__ == '__main__':
    arr = [1, 5, 1, 1, 6, 4]
    wiggleSort(arr)
    print(arr)

Line Notes

n = len(nums)Calculate the length of the input array to manage indices and pointers.

sorted_nums = sorted(nums)Sort the array to organize elements for splitting into smaller and larger halves.

res = [0] * nCreate a new array to store the rearranged elements without modifying the original during processing.

left = (n - 1) // 2Initialize pointer at the end of the smaller half (middle of sorted array) to pick smaller elements from right to left.

right = n - 1Initialize pointer at the end of the larger half to pick larger elements from right to left.

for i in range(n)Copy rearranged elements back to the original array to modify in-place.

if i % 2 == 0Place smaller half elements at even indices to satisfy nums[even] < nums[odd].

res[i] = sorted_nums[left]Assign element from smaller half to current even index.

left -= 1Move pointer leftwards in smaller half to pick next smaller element.

elsePlace larger half elements at odd indices to satisfy nums[odd] > nums[even].

res[i] = sorted_nums[right]Assign element from larger half to current odd index.

right -= 1Move pointer leftwards in larger half to pick next larger element.

nums[i] = res[i]Overwrite original array with wiggle sorted elements.

import java.util.*;
public class Solution {
    public void wiggleSort(int[] nums) {
        int n = nums.length;
        int[] sorted = nums.clone();
        Arrays.sort(sorted);
        int[] res = new int[n];
        int left = (n - 1) / 2;
        int right = n - 1;
        for (int i = 0; i < n; i++) {
            if (i % 2 == 0) {
                res[i] = sorted[left--];
            } else {
                res[i] = sorted[right--];
            }
        }
        for (int i = 0; i < n; i++) {
            nums[i] = res[i];
        }
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        int[] arr = {1, 5, 1, 1, 6, 4};
        sol.wiggleSort(arr);
        System.out.println(Arrays.toString(arr));
    }
}

Line Notes

int n = nums.length;Get the length of the input array to manage indices and pointers.

int[] sorted = nums.clone();Clone the array to avoid modifying the original during sorting.

Arrays.sort(sorted);Sort the cloned array to split into smaller and larger halves.

int[] res = new int[n];Create a new array to store rearranged elements without affecting original during processing.

int left = (n - 1) / 2;Pointer for smaller half starting from the middle element, moving leftwards.

int right = n - 1;Pointer for larger half starting from the end, moving leftwards.

for (int i = 0; i < n; i++) {Copy rearranged elements back to original array.

if (i % 2 == 0) {Place smaller half elements at even indices to maintain wiggle property.

res[i] = sorted[left--];Assign element from smaller half and decrement pointer.

} else {Place larger half elements at odd indices.

res[i] = sorted[right--];Assign element from larger half and decrement pointer.

nums[i] = res[i];Overwrite original array with wiggle sorted elements.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

void wiggleSort(vector<int>& nums) {
    int n = nums.size();
    vector<int> sorted(nums);
    sort(sorted.begin(), sorted.end());
    vector<int> res(n);
    int left = (n - 1) / 2;
    int right = n - 1;
    for (int i = 0; i < n; i++) {
        if (i % 2 == 0) {
            res[i] = sorted[left--];
        } else {
            res[i] = sorted[right--];
        }
    }
    for (int i = 0; i < n; i++) {
        nums[i] = res[i];
    }
}

int main() {
    vector<int> arr = {1, 5, 1, 1, 6, 4};
    wiggleSort(arr);
    for (int num : arr) cout << num << " ";
    cout << endl;
    return 0;
}

Line Notes

int n = nums.size();Get size of input vector to manage indices and pointers.

vector<int> sorted(nums);Copy input to a new vector for sorting without modifying original.

sort(sorted.begin(), sorted.end());Sort the copied vector to split into smaller and larger halves.

vector<int> res(n);Create result vector to store rearranged elements separately.

int left = (n - 1) / 2;Pointer for smaller half starting at middle, moving leftwards.

int right = n - 1;Pointer for larger half starting at end, moving leftwards.

for (int i = 0; i < n; i++) {Copy rearranged elements back to original vector.

if (i % 2 == 0) {Place smaller half elements at even indices to maintain wiggle property.

res[i] = sorted[left--];Assign element from smaller half and decrement pointer.

} else {Place larger half elements at odd indices.

res[i] = sorted[right--];Assign element from larger half and decrement pointer.

nums[i] = res[i];Overwrite original vector with wiggle sorted elements.

var wiggleSort = function(nums) {
    const n = nums.length;
    const sorted = [...nums].sort((a,b) => a - b);
    const res = new Array(n);
    let left = Math.floor((n - 1) / 2);
    let right = n - 1;
    for (let i = 0; i < n; i++) {
        if (i % 2 === 0) {
            res[i] = sorted[left--];
        } else {
            res[i] = sorted[right--];
        }
    }
    for (let i = 0; i < n; i++) {
        nums[i] = res[i];
    }
};

// Driver code
const arr = [1,5,1,1,6,4];
wiggleSort(arr);
console.log(arr);

Line Notes

const n = nums.length;Get length of input array to manage indices and pointers.

const sorted = [...nums].sort((a,b) => a - b);Create sorted copy of input to split into halves without modifying original.

const res = new Array(n);Create new array for rearranged elements to avoid in-place conflicts.

let left = Math.floor((n - 1) / 2);Pointer for smaller half starting at middle, moving leftwards.

let right = n - 1;Pointer for larger half starting at end, moving leftwards.

for (let i = 0; i < n; i++) {Copy rearranged elements back to original array.

if (i % 2 === 0) {Place smaller half elements at even indices to maintain wiggle property.

res[i] = sorted[left--];Assign element from smaller half and decrement pointer.

} else {Place larger half elements at odd indices.

res[i] = sorted[right--];Assign element from larger half and decrement pointer.

nums[i] = res[i];Overwrite original array with wiggle sorted elements.

⏱

Complexity

TimeO(n log n)

SpaceO(n)

Sorting takes O(n log n), and rearranging takes O(n). Extra space is used for the result array to avoid in-place conflicts.

💡 For n=100,000, sorting is the most expensive step, but this approach is straightforward and easy to implement, making it a good starting point.

Interview Verdict: Accepted but not optimal due to extra space

This approach works but uses extra space and is slower than optimal solutions, so it's good for initial understanding but not ideal for interviews.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	`O(n log n)`	`O(n)`	No	N/A	Mention only - never code
2. Median Finding + Virtual Indexing	`O(n) average`	`O(1)`	Low (due to recursion in quickselect)	N/A	Code this for optimal solution
3. Sorting + In-place Rearrangement	`O(n log n)`	`O(1)`	No	N/A	Good fallback if median finding is complex

Practice

(1/5)

1. Consider the following Python code implementing the optimal approach for relative sorting. Given arr1 = [3,1,2,2] and arr2 = [2,3], what is the final returned list?

easy

A. [2, 3, 1, 2]

B. [3, 2, 2, 1]

C. [2, 2, 3, 1]

D. [1, 2, 2, 3]

3. The following code attempts to find the minimum absolute difference but contains a subtle bug. Which line causes incorrect results?

def minimum_abs_difference(arr):
    min_diff = float('inf')
    for i in range(len(arr) - 1):
        diff = arr[i + 1] - arr[i]
        if diff < min_diff:
            min_diff = diff
    arr.sort()
    return min_diff

medium

A. Line 2: initializing min_diff before sorting

B. Line 6: sorting after scanning pairs

C. Line 7: returning min_diff without recomputing

D. Line 3: iterating without sorting first

5. The following code attempts to find the minimum time difference between time points. Which line contains a subtle bug that causes incorrect results on inputs with duplicate times?

def findMinDifference(timePoints):
    seen = [False] * 1440
    for t in timePoints:
        h, m = map(int, t.split(':'))
        total = h * 60 + m
        seen[total] = True
    prev = -1
    first = -1
    min_diff = 1440
    for i in range(1440):
        if seen[i]:
            if prev != -1:
                min_diff = min(min_diff, i - prev)
            else:
                first = i
            prev = i
    min_diff = min(min_diff, 1440 - prev + first)
    return min_diff

medium

A. Line updating min_diff inside the loop

B. Line initializing prev = -1

C. Line that sets seen[total] = True without checking duplicates

D. Line computing min_diff with circular difference after the loop

Recommended

Ready to prove it?

Pass the test and this pattern moves unknown strong while earning +1 Grip toward your certificate.

10 questions~5 mineasy hard

Intuition

Algorithm

Intuition

Algorithm

Intuition

Algorithm

How to Present

Time Allocation

What the Interviewer Tests

Common Follow-ups

When to Use

Signature Phrases

NOT This Pattern When

Similar Problems

Practice

Solution

Step 1: Build frequency array for arr1

Step 2: Construct result using arr2 order then leftovers

Final Answer:

Quick Check:

Solution

Step 1: Identify sorting cost

Step 2: Identify scanning cost

Final Answer:

Quick Check:

Solution

Step 1: Identify order of operations

Step 2: Pinpoint the bug

Final Answer:

Quick Check:

Solution

Step 1: Mark times in a fixed-size boolean array

Step 2: Scan the fixed 1440-length array once

Final Answer:

Quick Check:

Solution

Step 1: Check duplicate detection logic

Step 2: Consequence of missing duplicate check

Final Answer:

Quick Check:

Ready to prove it?