Wiggle Sort II

📋

Problem

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

Given an unsorted array nums, reorder it such that nums[0] < nums[1] > nums[2] < nums[3] > nums[4] < nums[5].... 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

Edge cases: All elements are equal → output is the same arrayArray with only one element → output is the same arrayArray with two elements → output is sorted to satisfy wiggle

</>

IDE

def wiggleSort(nums: list[int]) -> None:public void wiggleSort(int[] nums)void wiggleSort(vector<int>& nums)function wiggleSort(nums)

def wiggleSort(nums):
    # Write your solution here
    pass

class Solution {
    public void wiggleSort(int[] nums) {
        // Write your solution here
    }
}

#include <vector>
using namespace std;

void wiggleSort(vector<int>& nums) {
    // Write your solution here
}

function wiggleSort(nums) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: [1, 1, 1, 4, 5, 6]Output is sorted ascending without interleaving; fails wiggle property.✅ Interleave smaller half and larger half elements using virtual indexing after sorting.

Wrong: [1, 5, 1, 1, 4, 6]Incorrect placement of larger elements at even indices instead of odd indices.✅ Place larger elements at odd indices and smaller elements at even indices after median partition.

Wrong: [2, 2, 3, 3, 1, 1]Greedy approach ignoring median partition leads to duplicates clustered together.✅ Use three-way partitioning around median and virtual indexing to separate duplicates properly.

Wrong: [5, 5, 6, 6, 6, 4]Incorrect handling of duplicates and 0/1 usage confusion causing repeated elements in wrong positions.✅ Ensure each element is used once and placed correctly using median partition and virtual indexing.

Wrong: Timeout or crash on large inputBrute force or sorting-based approach with O(n^2) complexity.✅ Implement median finding and three-way partitioning with virtual indexing for O(n) average time complexity.

✓

Test Cases

Make sure your solution works on small and trivial inputs before tackling edge cases.

Focus on handling duplicates and median partitioning correctly to avoid common pitfalls.

Optimize your approach to run in linear or linearithmic time for large inputs.

t1_01basic

Input{"nums":[1,6,1,5,1,4]}

Expectednull

⏱ Performance - must finish in 2000ms

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

💡 Try sorting the array first to understand the order of elements.

💡 Use the median to partition the array and place larger elements at odd indices.

💡 Interleave smaller half and larger half elements to achieve the wiggle property.

Why it failed: Output does not satisfy wiggle property; likely incorrect partition or placement of elements. Fix by correctly interleaving smaller and larger halves using virtual indexing.

✓ Correctly rearranged array satisfying the wiggle property.

t1_02basic

Input{"nums":[5,6,4,5]}

Expectednull

⏱ Performance - must finish in 2000ms

Array rearranged so that nums[0] < nums[1] > nums[2] < nums[3].

💡 Sort the array and find the median to split into two halves.

💡 Place the larger half elements at odd indices and smaller half at even indices.

💡 Use virtual indexing to avoid overwriting elements during rearrangement.

Why it failed: Fails to maintain wiggle property due to incorrect element placement or ignoring duplicates. Fix by careful median partition and virtual index mapping.

✓ Array correctly wiggle sorted with duplicates handled.

t2_01edge

Input{"nums":[]}

Expected[]

⏱ Performance - must finish in 2000ms

Empty array remains empty; no rearrangement needed.

💡 Check how your code handles empty input arrays.

💡 Ensure no index out-of-bound errors occur with zero length.

💡 Return immediately or handle empty case gracefully.

Why it failed: Code crashes or errors on empty input due to missing boundary checks. Fix by adding early return for empty array.

✓ Handles empty input without errors.

t2_02edge

Input{"nums":[10]}

Expectednull

⏱ Performance - must finish in 2000ms

Single element array remains unchanged; trivially satisfies wiggle property.

💡 Consider arrays with only one element as a base case.

💡 No rearrangement needed if length is 1.

💡 Return early or skip processing for single element arrays.

Why it failed: Fails or modifies single element array unnecessarily. Fix by adding condition to skip rearrangement if length is 1.

✓ Correctly handles single element arrays.

t2_03edge

Input{"nums":[1,2]}

Expectednull

⏱ Performance - must finish in 2000ms

Two elements sorted to satisfy nums[0] < nums[1].

💡 For two elements, simply sort to satisfy wiggle property.

💡 Check boundary conditions when array length is 2.

💡 Swap elements if needed to ensure nums[0] < nums[1].

Why it failed: Fails to reorder two elements correctly; outputs unsorted or wrong order. Fix by sorting or swapping two elements to satisfy wiggle.

✓ Correctly wiggle sorts two-element arrays.

t3_01corner

Input{"nums":[2,3,1,3,1,2]}

Expectednull

⏱ Performance - must finish in 2000ms

Handles duplicates and multiple median values correctly to maintain wiggle property.

💡 Beware of greedy approaches that place elements without median partitioning.

💡 Use three-way partitioning around median to handle duplicates properly.

💡 Apply virtual indexing to place elements in correct positions.

Why it failed: Greedy approach fails to handle duplicates and median correctly, breaking wiggle property. Fix by implementing median-based three-way partition and virtual indexing.

✓ Correctly handles duplicates and median partitioning.

t3_02corner

Input{"nums":[5,6,5,6,4,6]}

Expectednull

⏱ Performance - must finish in 2000ms

Tests correct handling of multiple identical large elements and proper placement.

💡 Avoid confusing 0/1 knapsack style unbounded placement with 0/1 placement here.

💡 Ensure each element is used exactly once in the rearrangement.

💡 Use median partition and virtual indexing to place elements uniquely.

Why it failed: Incorrectly treats elements as unbounded or duplicates misplaced, violating wiggle property. Fix by ensuring each element used once with median partition and virtual indexing.

✓ Correctly places duplicates respecting 0/1 usage.

t3_03corner

Input{"nums":[4,7,3,6,2,5,1]}

Expectednull

⏱ Performance - must finish in 2000ms

Tests off-by-one errors in median calculation and index mapping.

💡 Check median calculation carefully, especially for odd length arrays.

💡 Verify virtual index mapping formula to avoid off-by-one errors.

💡 Ensure correct halves are interleaved starting from median.

Why it failed: Off-by-one error in median or virtual index causes incorrect placement and wiggle violation. Fix by correcting median index and virtual index formula.

✓ Correct median and virtual indexing applied.

t4_01performance

Input{"nums":[1000000,999999,999998,999997,999996,999995,999994,999993,999992,999991,999990,999989,999988,999987,999986,999985,999984,999983,999982,999981,999980,999979,999978,999977,999976,999975,999974,999973,999972,999971,999970,999969,999968,999967,999966,999965,999964,999963,999962,999961,999960,999959,999958,999957,999956,999955,999954,999953,999952,999951,999950,999949,999948,999947,999946,999945,999944,999943,999942,999941,999940,999939,999938,999937,999936,999935,999934,999933,999932,999931,999930,999929,999928,999927,999926,999925,999924,999923,999922,999921,999920,999919,999918,999917,999916,999915,999914,999913,999912,999911,999910,999909,999908,999907,999906,999905,999904,999903,999902,999901]}

Expectednull

⏱ Performance - must finish in 2000ms

Large input with n=100 to test O(n) or O(n log n) solutions complete within 2 seconds.

💡 Brute force O(n^2) solutions will time out on large inputs.

💡 Use median finding with three-way partitioning for O(n) average time.

💡 Avoid sorting entire array if possible to meet time constraints.

Why it failed: TLE due to O(n^2) or worse complexity. Fix by implementing median-based partitioning and virtual indexing for O(n) average time.

✓ Solution runs within time limit using efficient O(n) or O(n log n) approach.

Practice

1. Given the following code for computing the h-index, what is the returned value when the input is [4, 1, 0, 5, 6]?

easy

A. 3

B. 4

C. 5

D. 2

Solution

1. Step 1: Sort citations descending

   Sorted list: [6,5,4,1,0]

2. Step 2: Binary search on h from 0 to 5

   Check mid=2: count papers >=2 is 3 (6,5,4) ≥2 -> low=3; mid=4: count ≥4 is 3 -> low=5; mid=5: count ≥5 is 2 -> high=4; loop ends with high=4.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Final h-index is 4 for this input [OK]

Hint: Count papers ≥ mid after sorting [OK]

Common Mistakes:

• Off-by-one in binary search boundaries
• Not breaking early in count loop
• Returning low instead of high

2. You are given a sorted list of unique integers and a range defined by lower and upper. You need to find all the missing continuous ranges within this interval that are not present in the list. Which algorithmic approach best guarantees an optimal solution in terms of time complexity?

easy

A. Sorting the list and then scanning linearly to find gaps

B. Using binary search to quickly locate missing ranges between elements

C. Dynamic programming to build missing ranges from subproblems

D. Greedy approach scanning the entire range and adding missing numbers one by one

Solution

1. Step 1: Understand problem constraints

   The problem requires finding missing ranges efficiently within a sorted list and a given interval.

2. Step 2: Identify approach that leverages sorted data

   Since the list is already sorted, scanning linearly to find gaps between consecutive elements is optimal and straightforward.

3. Step 3: Evaluate binary search approach

   Using binary search to locate missing ranges is unnecessary overhead because the list is sorted and unique; a linear scan suffices.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Linear scan over sorted unique list is O(n), optimal for this problem [OK]

Hint: Linear scan over sorted unique list is optimal for missing ranges [OK]

Common Mistakes:

• Assuming binary search is needed despite sorted input
• Confusing DP with range search
• Ignoring linear scan benefits

3. What is the time complexity of the bucket sort / pigeonhole principle approach to find the maximum gap in an unsorted array of size n, assuming the numbers are integers within a known range [min, max]? Choose the most accurate complexity considering both sorting and bucket operations.

medium

A. O(n) because bucket distribution and scanning are linear

B. O(n + k) where k is the number of buckets, which can be up to n+1

C. O(n log n) due to sorting the entire array

D. O(n²) because of nested bucket comparisons

Solution

1. Step 1: Understand bucket sort steps

   Bucket sort distributes n elements into k buckets, then scans buckets to find max gap.

2. Step 2: Analyze complexity components

   Distribution is O(n), scanning buckets is O(k). Since k ≈ n+1, total is O(n + k) = O(n).

3. Step 3: Simplify complexity

   Because k is proportional to n, O(n + k) simplifies to O(n).

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Bucket count k depends on input range but is linear in n [OK]

Hint: Bucket count k is linear in n, so O(n + k) = O(n) [OK]

Common Mistakes:

• Assuming sorting is always O(n log n)
• Ignoring bucket count impact
• Confusing bucket scanning with nested loops

4. What is the time complexity of the optimal bucket sort based solution for finding the minimum time difference among n time points, where each time is in "HH:MM" format?

medium

A. O(n + 1440) because we mark seen times and scan a fixed-size array

B. O(n log n) due to sorting the input times

C. O(n^2) because we compare all pairs of times

D. O(1440^2) since we scan all possible time pairs in the fixed range

Solution

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

   Marking each of the n times in a 1440-length array is O(n).

2. Step 2: Scan the fixed 1440-length array once

   Scanning the array to find minimum difference is O(1440), which is constant and independent of n.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Overall complexity is O(n + 1440) -> O(n) for large n [OK]

Hint: Fixed 1440 array makes scanning O(1) relative to n [OK]

Common Mistakes:

• Assuming sorting is needed -> O(n log n)
• Confusing nested loops -> O(n^2)
• Thinking scanning pairs in fixed array is quadratic

5. What is the time complexity of the optimal diagonal sorting algorithm that uses a min-heap per diagonal for an m x n matrix, where each diagonal is sorted independently?

medium

A. O(m * n * min(m, n)) because sorting each diagonal requires scanning all elements multiple times.

B. O(m * n * log(m * n)) because all elements are pushed into heaps together.

C. O(m * n) because each element is processed once with constant-time heap operations.

D. O(m * n * log(min(m, n))) because each diagonal has at most min(m, n) elements and heap operations cost log of diagonal length.

Solution

1. Step 1: Identify diagonal lengths

   Each diagonal has at most min(m, n) elements, so heap operations per element cost O(log(min(m, n))).

2. Step 2: Calculate total heap operations

   All m*n elements are pushed and popped once, each operation O(log(min(m, n))). Total time is O(m * n * log(min(m, n))).

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Heap operations dominate and depend on diagonal length, not total elements [OK]

Hint: Heap ops cost log of diagonal length, not total elements [OK]

Common Mistakes:

• Assuming log(m*n) instead of log(min(m,n))
• Ignoring heap operation cost
• Mistaking linear heap ops for constant time