Wiggle Sort II

▶

Steps

setup

Sort the array

The input array is sorted in ascending order to prepare for median finding and rearrangement.

💡 Sorting organizes elements so the median can be easily found and the wiggle pattern can be constructed systematically.

Line:

nums.sort()

💡 Sorting is the foundation for the median-based partitioning that follows.

setup

Find the median

Calculate the median as the middle element of the sorted array, which is used to partition elements.

💡 The median divides the array into elements less than, equal to, and greater than itself, guiding the wiggle arrangement.

Line:

median = nums[(n - 1) // 2]

💡 Median is the pivot for three-way partitioning in the virtual index space.

setup

Initialize pointers

Set three pointers: left at 0, i at 0, and right at the last index to start the virtual index partitioning.

💡 These pointers control the partitioning of elements greater than, equal to, and less than the median in virtual index order.

Line:

left, i, right = 0, 0, n - 1

💡 Pointers are ready to traverse and rearrange the array in virtual index order.

compare

Calculate virtual index for i=0

Compute virtual index for i=0 using the formula (1 + 2*i) % (n | 1), mapping i=0 to virtual index 1.

💡 Virtual indexing rearranges indices to place larger elements at odd indices and smaller at even indices for wiggle property.

Line:

vi = virtual_index(i)

💡 Virtual index 1 corresponds to the second element in the array, which will be checked against the median.

compare

Compare nums[vi] to median (nums[1] = 1 vs median=1)

Check if nums at virtual index 1 is greater than, less than, or equal to the median (1). Here it equals the median.

💡 This comparison decides whether to swap with left, right, or just move i forward.

Line:

if nums[vi] > median: ... elif nums[vi] < median: ... else: i += 1

💡 Elements equal to median stay in the middle partition; i moves forward to check next element.

compare

Calculate virtual index for i=1

Compute virtual index for i=1: (1 + 2*1) % 7 = 3, mapping i=1 to virtual index 3.

💡 Virtual index 3 corresponds to the fourth element, which will be compared to the median next.

Line:

vi = virtual_index(i)

💡 Virtual indexing continues to map i to wiggle positions for comparison.

compare

Compare nums[vi] to median (nums[3] = 4 vs median=1)

nums[3] = 4 is greater than median 1, so swap with nums at virtual index of left pointer.

💡 Elements greater than median are moved to the left partition to satisfy wiggle property at odd indices.

Line:

if nums[vi] > median:
  vleft = virtual_index(left)
  nums[vi], nums[vleft] = nums[vleft], nums[vi]
  left += 1
  i += 1

💡 Swapping places larger elements at odd indices, advancing left and i to expand the greater-than-median partition.

compare

Calculate virtual index for i=2

Compute virtual index for i=2: (1 + 2*2) % 7 = 5, mapping i=2 to virtual index 5.

💡 Virtual index 5 corresponds to the sixth element, next to be compared to median.

Line:

vi = virtual_index(i)

💡 Virtual indexing continues to guide the rearrangement positions.

compare

Compare nums[vi] to median (nums[5] = 6 vs median=1)

nums[5] = 6 is greater than median 1, so swap with nums at virtual index of left pointer.

💡 Continue moving larger elements to the left partition to maintain wiggle order.

Line:

if nums[vi] > median:
  vleft = virtual_index(left)
  nums[vi], nums[vleft] = nums[vleft], nums[vi]
  left += 1
  i += 1

💡 Swapping places the next largest element at the correct wiggle position.

compare

Calculate virtual index for i=3

Compute virtual index for i=3: (1 + 2*3) % 7 = 0, mapping i=3 to virtual index 0.

💡 Virtual index 0 corresponds to the first element, next to be compared to median.

Line:

vi = virtual_index(i)

💡 Virtual indexing cycles through the array to place elements correctly.

compare

Compare nums[vi] to median (nums[0] = 1 vs median=1)

nums[0] = 1 equals the median, so increment i to check next element.

💡 Equal elements remain in the middle partition; i moves forward.

Line:

else:
  i += 1

💡 Middle partition elements are skipped over by advancing i.

compare

Calculate virtual index for i=4

Compute virtual index for i=4: (1 + 2*4) % 7 = 2, mapping i=4 to virtual index 2.

💡 Virtual index 2 corresponds to the third element, next to be compared.

Line:

vi = virtual_index(i)

💡 Virtual indexing continues to cycle through the array.

compare

Compare nums[vi] to median (nums[2] = 1 vs median=1)

nums[2] = 1 equals the median, so increment i to continue.

💡 Equal elements remain in place; i moves forward.

Line:

else:
  i += 1

💡 Middle partition elements are passed over by advancing i.

compare

Calculate virtual index for i=5

Compute virtual index for i=5: (1 + 2*5) % 7 = 4, mapping i=5 to virtual index 4.

💡 Virtual index 4 corresponds to the fifth element, next to be compared.

Line:

vi = virtual_index(i)

💡 Virtual indexing cycles through the array to place elements correctly.

compare

Compare nums[vi] to median (nums[4] = 5 vs median=1)

nums[4] = 5 is greater than median 1, so swap with nums at virtual index of left pointer.

💡 Elements greater than median are moved to the left partition to maintain wiggle order.

Line:

if nums[vi] > median:
  vleft = virtual_index(left)
  nums[vi], nums[vleft] = nums[vleft], nums[vi]
  left += 1
  i += 1

💡 Swapping places the last larger element at the correct wiggle position.

traverse

Loop ends as i > right

The pointer i has moved beyond right, ending the partitioning loop and completing the wiggle rearrangement.

💡 When i passes right, all elements are partitioned correctly according to the median and virtual indexing.

Line:

while i <= right: ... (loop ends)

💡 The array now satisfies the wiggle property with elements rearranged in-place.

reconstruct

Final wiggle sorted array

The array is now rearranged to satisfy nums[0] < nums[1] > nums[2] < nums[3] > nums[4] < nums[5].

💡 The rearrangement ensures the wiggle property without extra space by using virtual indexing and three pointers.

Line:

print(arr)

💡 The final array is the output of the algorithm, demonstrating the wiggle sort property.

def wiggleSort(nums):
    n = len(nums)  # STEP 1
    nums.sort()  # STEP 1
    median = nums[(n - 1) // 2]  # STEP 2

    def virtual_index(i):  # STEP 4
        return (1 + 2 * i) % (n | 1)

    left, i, right = 0, 0, n - 1  # STEP 3
    while i <= right:  # STEP 16
        vi = virtual_index(i)  # STEP 4,6,8,10,12,14
        if nums[vi] > median:  # STEP 7,9,15
            vleft = virtual_index(left)
            nums[vi], nums[vleft] = nums[vleft], nums[vi]
            left += 1
            i += 1
        elif nums[vi] < median:  # (not triggered in this example)
            vright = virtual_index(right)
            nums[vi], nums[vright] = nums[vright], nums[vi]
            right -= 1
        else:  # STEP 5,11,13
            i += 1

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

📊

Wiggle Sort II - Watch the Algorithm Execute, Step by Step

Watching each pointer move and swap helps you understand how the algorithm rearranges elements without extra space, which is hard to grasp from code alone.

compare

1

0

1

1

1

2

4

3

5

4

6

5

compare

1

0

1

1

1

2

4

3

5

4

6

5

Result: 1

compare

i

1

0

1

1

1

2

4

3

5

4

right

6

5

compare

i

1

0

vi

1

1

1

2

4

3

5

4

6

5

move_right

left

1

0

vi

1

1

1

2

4

3

5

4

right

6

5

compare

1

0

i

1

1

1

2

vi

4

3

5

4

6

5

swap

1

0

left

4

1

i

1

2

vi

1

3

5

4

right

6

5

compare

1

0

4

1

i

1

2

1

3

5

4

vi

6

5

swap

1

0

4

1

left

1

2

i

6

3

5

4

vi

1

5

compare

vi

1

0

4

1

1

2

i

6

3

5

4

1

5

move_right

vi

1

0

4

1

left

1

2

6

3

i

5

4

right

1

5

compare

1

0

4

1

vi

1

2

6

3

i

5

4

1

5

move_right

1

0

4

1

vi

1

2

6

3

5

4

right

1

5

compare

1

0

4

1

1

2

6

3

vi

5

4

i

1

5

swap

1

0

4

1

1

2

left

6

3

vi

1

4

right

5

5

compare

1

0

4

1

1

2

left

6

3

1

4

right

5

5

record

1

0

6

1

1

2

5

3

1

4

4

5

Result: ["1","6","1","5","1","4"]

Key Takeaways

✓ Virtual indexing remaps array indices to place larger elements at odd indices and smaller at even indices.

This insight is hard to see from code alone because the index mapping formula is non-intuitive without visualization.

✓ Three pointers (left, i, right) partition the array into elements greater than, equal to, and less than the median in virtual index order.

Seeing pointer movements and swaps clarifies how the algorithm rearranges elements in-place without extra space.

✓ Elements equal to the median are left in the middle partition by simply advancing the i pointer.

This subtlety is easy to miss in code but critical to maintaining the wiggle property and avoiding unnecessary swaps.

Practice

1. Consider the following Python code for generating the largest number from a list of integers. What is the output when the input is [3, 30, 34]?

from functools import cmp_to_key

def largestNumber(nums):
    nums_str = list(map(str, nums))

    def compare(a, b):
        return -1 if a + b > b + a else 1 if a + b < b + a else 0

    nums_str.sort(key=cmp_to_key(compare))
    if nums_str[0] == '0':
        return '0'
    return ''.join(nums_str)

print(largestNumber([3, 30, 34]))

easy

A. '34330'

B. '33034'

C. '33430'

D. '34303'

Solution

1. Step 1: Convert numbers to strings

   nums_str = ['3', '30', '34']

2. Step 2: Sort with custom comparator

   Compare pairs: - '3' + '30' = '330' vs '30' + '3' = '303' -> '330' > '303', so '3' before '30' - '34' + '3' = '343' vs '3' + '34' = '334' -> '343' > '334', so '34' before '3' - '34' + '30' = '3430' vs '30' + '34' = '3034' -> '3430' > '3034', so '34' before '30' Sorted order: ['34', '3', '30']

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Concatenation '34330' is largest [OK]

Hint: Compare concatenations a+b and b+a to order strings [OK]

Common Mistakes:

• Sorting lexicographically or numerically without custom comparator

2. You are given an array of integers and need to rearrange it so that no two adjacent elements are the same. Which approach guarantees an optimal solution for this problem?

easy

A. Count frequencies, then use a max heap to greedily place the most frequent elements first, ensuring spacing.

B. Use backtracking to generate all permutations and check for valid arrangements.

C. Sort the array and then swap adjacent elements to avoid duplicates.

D. Use dynamic programming to track valid sequences avoiding adjacent duplicates.

Solution

1. Step 1: Understand problem constraints

   The problem requires rearranging elements so no two adjacent are equal, which demands careful placement of frequent elements.

2. Step 2: Identify approach that handles frequency and spacing

   Using a max heap to always pick the most frequent element available and placing it ensures no two identical elements are adjacent, which brute force or simple sorting cannot guarantee efficiently.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Max heap approach handles frequency and spacing correctly [OK]

Hint: Max heap ensures spacing of frequent elements [OK]

Common Mistakes:

• Thinking sorting alone avoids adjacent duplicates
• Assuming DP solves this without frequency tracking

3. Consider the following Python code that sorts a matrix diagonally using min-heaps. What is the final matrix returned when the input is [[3,3,1,1],[2,2,1,2],[1,1,1,2]]?

from typing import List
import collections
import heapq

def diagonalSort(mat: List[List[int]]) -> List[List[int]]:
    m, n = len(mat), len(mat[0])
    diagonals = collections.defaultdict(list)
    for i in range(m):
        for j in range(n):
            heapq.heappush(diagonals[i - j], mat[i][j])
    for i in range(m):
        for j in range(n):
            mat[i][j] = heapq.heappop(diagonals[i - j])
    return mat

matrix = [[3,3,1,1],[2,2,1,2],[1,1,1,2]]
print(diagonalSort(matrix))

easy

A. [[1,1,1,1],[1,2,2,2],[1,2,3,3]]

B. [[1,1,1,1],[1,2,2,2],[1,1,3,3]]

C. [[1,1,1,1],[1,2,2,2],[1,2,3,3]]

D. [[1,1,1,1],[1,2,2,2],[1,1,1,2]]

Solution

1. Step 1: Build min-heaps keyed by diagonal (row - col)

   For each element, push into heap keyed by i - j. For example, diagonal key 0 has elements [3,2,1], which heapify to [1,2,3].

2. Step 2: Pop from heaps to replace matrix elements

   Traverse matrix again, replacing each element with the smallest from its diagonal heap. This sorts each diagonal ascending.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Diagonal keys and heaps produce sorted diagonals matching [[1,1,1,1],[1,2,2,2],[1,2,3,3]] [OK]

Hint: Heap per diagonal ensures sorted order on replacement [OK]

Common Mistakes:

• Off-by-one errors in heap keys
• Mixing up heap push/pop order
• Incorrectly reconstructing matrix from heaps

4. You are given a sorted array of integers and a quadratic function f(x) = ax² + bx + c. You need to return a sorted array of the values f(x) applied to each element x in the input array. Which approach guarantees an optimal O(n) time solution?

easy

A. Use two pointers at the start and end of the input array and fill the output array from the end or start depending on the sign of a, leveraging the parabola shape.

B. Use dynamic programming to store intermediate results and build the sorted transformed array incrementally.

C. Apply the quadratic function to each element and then sort the resulting array using a standard sorting algorithm.

D. Use a max-heap to insert transformed values and then extract them in sorted order.

Solution

1. Step 1: Understand the parabola shape

   The quadratic function forms a parabola. If a >= 0, the largest values are at the ends of the input array; if a < 0, the smallest values are at the ends.

2. Step 2: Use two pointers to fill output

   By comparing transformed values at both ends, we can fill the output array from the appropriate end in O(n) time without sorting.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Two pointers leverage sorted input and parabola shape for linear time [OK]

Hint: Two pointers exploit parabola shape for O(n) [OK]

Common Mistakes:

• Assuming sorting is always needed after transformation
• Trying DP without leveraging input order

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