Wiggle Sort - Practice Coding Problems

Wiggle Sort - Problem

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

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

Example:

Input: nums = [3,5,2,1,6,4]
Output: [3,5,1,6,2,4]
Explanation: 3 <= 5 >= 1 <= 6 >= 2 <= 4

Input & Output

Example 1 — Basic Case

$ Input: nums = [3,5,2,1,6,4]

› Output: [3,5,1,6,2,4]

💡 Note: The array satisfies: 3 ≤ 5 ≥ 1 ≤ 6 ≥ 2 ≤ 4. Even indices are valleys (≤ next), odd indices are peaks (≥ next).

Example 2 — Already Wiggled

$ Input: nums = [1,3,2,4]

› Output: [1,3,2,4]

💡 Note: Already satisfies wiggle: 1 ≤ 3 ≥ 2 ≤ 4. No changes needed.

Example 3 — Two Elements

$ Input: nums = [2,1]

› Output: [1,2]

💡 Note: For two elements, ensure first ≤ second: swap to get 1 ≤ 2.

Constraints

1 ≤ nums.length ≤ 5 × 10⁴
0 ≤ nums[i] ≤ 5000

Visualization

Tap to expand

Understanding the Visualization

Input Array

Original array [3,5,2,1,6,4] with no pattern

Apply Wiggle Rule

Ensure nums[0] ≤ nums[1] ≥ nums[2] ≤ nums[3]...

Wiggle Pattern

Result [3,5,1,6,2,4] alternates valley-peak

Key Takeaway

🎯 Key Insight: Local swaps can fix wiggle violations without affecting already-correct portions

Asked in

G Google 25 f Facebook 20 a Amazon 18 M Microsoft 15

The key insight is that wiggle sort requires alternating valleys and peaks. The optimal greedy approach scans left-to-right and fixes violations with local swaps. Time: O(n), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ One Pass Greedy	O(n)	O(1)	Check each position and swap if wiggle pattern is violated
Sort Then Rearrange	O(n log n)	O(1)	Sort array then rearrange by placing elements at specific positions

One Pass Greedy — Algorithm Steps

Step 1: Iterate through each position
Step 2: Check if current position satisfies wiggle condition
Step 3: Swap with neighbor if violation found

Visualization

Tap to expand

Step-by-Step Walkthrough

Scan Left to Right

Check each position against wiggle requirement

Fix Violations

Swap with previous element when pattern breaks

Continue

Local fixes maintain global wiggle property

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int* solution(int* nums, int numsSize, int* returnSize) {
    *returnSize = numsSize;
    
    for (int i = 1; i < numsSize; i++) {
        // Even index should be <= next (valley)
        // Odd index should be >= next (peak)
        if ((i % 2 == 1 && nums[i] < nums[i-1]) || (i % 2 == 0 && nums[i] > nums[i-1])) {
            int temp = nums[i];
            nums[i] = nums[i-1];
            nums[i-1] = temp;
        }
    }
    
    return nums;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    // Parse array manually
    int nums[1000];
    int size = 0;
    char *ptr = line + 1; // skip [
    char *token = strtok(ptr, ",]");
    while (token != NULL) {
        nums[size++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    int returnSize;
    int* result = solution(nums, size, &returnSize);
    
    printf("[");
    for (int i = 0; i < returnSize; i++) {
        printf("%d", result[i]);
        if (i < returnSize - 1) printf(",");
    }
    printf("]\n");
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Single pass through array, constant work per element

✓ Linear Growth

Space Complexity

O(1)

Only uses constant extra space for swapping

✓ Linear Space

28.5K Views

Medium Frequency

~15 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

One Pass Greedy — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler