Make the Array Beautiful (Sort + Greedy)

▶

Steps

setup

Count frequencies of elements

Count how many times each element appears in the input array using a frequency map.

💡 Knowing frequencies is essential to decide if a valid arrangement is possible and to prepare the heap.

Line:

freq = Counter(arr)

💡 Frequency counts reveal the distribution of elements and the maximum frequency.

setup

Check if arrangement is possible

Calculate the maximum frequency and verify if it exceeds half the array length rounded up, which would make arrangement impossible.

💡 This check prevents futile attempts when one element dominates the array.

Line:

max_freq = max(freq.values())
n = len(arr)
if max_freq > (n + 1) // 2:
    return []

💡 If max frequency is too high, no valid arrangement exists; here it is valid.

setup

Build max heap from frequencies

Create a max heap by pushing negative counts and their elements, so the element with highest frequency is on top.

💡 Using negative counts allows Python's min-heap to behave like a max heap.

Line:

heap = [(-count, num) for num, count in freq.items()]
heapq.heapify(heap)

💡 Heap structure enables efficient retrieval of the most frequent elements.

traverse

Pop first element from heap

Pop the element with the highest frequency from the heap to append it to the result array.

💡 Picking the most frequent element first helps distribute it evenly in the result.

Line:

count, num = heapq.heappop(heap)

💡 The element popped is the current candidate to add to the result.

insert

Append popped element to result

Add the popped element to the result array and prepare to push back the previous element if still available.

💡 Appending elements one by one builds the final rearranged array.

Line:

res.append(num)

💡 The result array grows stepwise with chosen elements.

insert

Push previous element back if count remains

If the previously used element still has remaining count, push it back into the heap for future use.

💡 This step ensures elements are reused correctly without adjacency.

Line:

if prev_count < 0:
    heapq.heappush(heap, (prev_count, prev_num))

💡 No element to push back on first iteration.

insert

Update previous element to current popped

Set the current popped element as the previous element with its count incremented (since one occurrence used).

💡 Tracking previous element prevents placing the same element consecutively.

Line:

prev_count, prev_num = count + 1, num

💡 The previous element is now the last appended element with updated count.

traverse

Pop second element from heap

Pop the next most frequent element from the heap to append it to the result array.

💡 Alternating elements prevents adjacent duplicates.

Line:

count, num = heapq.heappop(heap)

💡 The second element is chosen to alternate with the previous one.

insert

Append second popped element to result

Add the second popped element to the result array, continuing to build the rearranged array.

💡 Appending different elements alternately avoids adjacency.

Line:

res.append(num)

💡 Result array now has two elements, both different.

insert

Push previous element back if count remains

Push the previous element back into the heap if it still has remaining count after use.

💡 This step recycles elements to be used later without adjacency.

Line:

if prev_count < 0:
    heapq.heappush(heap, (prev_count, prev_num))

💡 The previously used element is reinserted for future placement.

insert

Update previous element to current popped

Update the previous element to the current popped element with its count incremented.

💡 Tracking the last appended element is key to avoid duplicates.

Line:

prev_count, prev_num = count + 1, num

💡 The previous element pointer moves forward with updated count.

traverse

Pop next element from heap

Pop the next most frequent element from the heap to append to the result array.

💡 Continuing to alternate elements keeps the array beautiful.

Line:

count, num = heapq.heappop(heap)

💡 Heap always provides the next best candidate element.

insert

Append popped element to result

Add the popped element to the result array, continuing the alternating pattern.

💡 Appending elements one by one builds the final solution.

Line:

res.append(num)

💡 Result array grows with no two adjacent elements equal.

insert

Push previous element back if count remains

Push the previous element back into the heap if it still has remaining count.

💡 This step ensures elements are reused properly.

Line:

if prev_count < 0:
    heapq.heappush(heap, (prev_count, prev_num))

💡 Heap is updated dynamically to reflect leftover counts.

insert

Update previous element to current popped

Update the previous element to the current popped element with incremented count.

💡 Tracking leftover counts is crucial for correctness.

Line:

prev_count, prev_num = count + 1, num

💡 Previous element pointer moves forward with updated count.

traverse

Pop next element from heap

Pop the next most frequent element from the heap to append to the result array.

💡 Continuing the alternating pattern to avoid duplicates.

Line:

count, num = heapq.heappop(heap)

💡 Heap provides the next candidate element.

insert

Append popped element to result

Add the popped element to the result array, continuing the pattern.

💡 Appending elements one by one builds the final solution.

Line:

res.append(num)

💡 Result array grows with no two adjacent elements equal.

insert

Push previous element back if count remains

Push the previous element back into the heap if it still has remaining count.

💡 This step ensures elements are reused properly.

Line:

if prev_count < 0:
    heapq.heappush(heap, (prev_count, prev_num))

💡 Heap is updated dynamically to reflect leftover counts.

insert

Update previous element to current popped

Update the previous element to the current popped element with incremented count.

💡 Tracking leftover counts is crucial for correctness.

Line:

prev_count, prev_num = count + 1, num

💡 Previous element pointer moves forward with updated count.

traverse

Pop last element and append to result

Pop the last element from the heap and append it to the result array, completing the rearrangement.

💡 Appending the last element finishes the array without adjacent duplicates.

Line:

count, num = heapq.heappop(heap)
res.append(num)

💡 The final element is placed ensuring no two adjacent elements are equal.

from collections import Counter
import heapq

def make_array_beautiful_heap(arr):
    freq = Counter(arr)  # STEP 1
    max_freq = max(freq.values())  # STEP 2
    n = len(arr)
    if max_freq > (n + 1) // 2:
        return []  # STEP 2 decision
    heap = [(-count, num) for num, count in freq.items()]  # STEP 3
    heapq.heapify(heap)  # STEP 3
    res = []
    prev_count, prev_num = 0, None
    while heap:
        count, num = heapq.heappop(heap)  # STEP 4,8,12,16,20
        res.append(num)  # STEP 5,9,13,17,20
        if prev_count < 0:
            heapq.heappush(heap, (prev_count, prev_num))  # STEP 6,10,14,18
        prev_count, prev_num = count + 1, num  # STEP 7,11,15,19
    return res

if __name__ == '__main__':
    arr = [1,1,2,2,3,3]
    print(make_array_beautiful_heap(arr))

📊

Make the Array Beautiful (Sort + Greedy) - Watch the Algorithm Execute, Step by Step

Watching each step reveals how the heap structure and greedy choices prevent adjacent duplicates, which is hard to grasp from code alone.

record

1

0

1

1

2

2

2

3

3

4

3

5

Result: {}

compare

1

0

1

1

2

2

2

3

3

4

3

5

Result: {}

expand

heap_top

1

0

1

1

2

2

2

3

3

4

3

5

Result: []

move_left

Result: []

record

res_end

1

0

Result: [1]

prune

1

0

Result: [1]

record

prev

1

0

Result: [1]

move_left

heap_top

1

0

Result: [1]

record

1

0

res_end

2

1

Result: [1,2]

expand

heap_top

1

0

2

1

Result: [1,2]

record

1

0

prev

2

1

Result: [1,2]

move_left

heap_top

1

0

2

1

Result: [1,2]

record

1

0

2

1

res_end

1

2

Result: [1,2,1]

expand

heap_top

1

0

2

1

1

2

Result: [1,2,1]

record

1

0

2

1

prev

1

2

Result: [1,2,1]

move_left

heap_top

1

0

2

1

1

2

Result: [1,2,1]

record

1

0

2

1

1

2

res_end

3

3

Result: [1,2,1,3]

expand

heap_top

1

0

2

1

1

2

3

3

Result: [1,2,1,3]

record

1

0

2

1

1

2

prev

3

3

Result: [1,2,1,3]

record

1

0

2

1

1

2

3

3

2

4

res_end

3

5

Result: [1,2,1,3,2,3]

Key Takeaways

✓ Using a max heap to always pick the two most frequent elements ensures no two adjacent elements are the same.

This insight is hard to see from code alone because the heap operations and greedy logic are intertwined.

✓ Tracking the previously used element and pushing it back only if it still has remaining count prevents immediate repetition.

This mechanism is subtle and watching the pointer updates clarifies how adjacency is avoided.

✓ The frequency check at the start quickly determines if a valid arrangement is possible, saving unnecessary computation.

Understanding this early pruning is easier when you see the frequency counts and max frequency visually.

Practice

1. Consider the following Python function that finds the minimum time difference between time points. What is the returned value when the input is ["01:01", "02:01", "01:02"]?

def findMinDifference(timePoints):
    seen = [False] * 1440
    for t in timePoints:
        h, m = map(int, t.split(':'))
        total = h * 60 + m
        if seen[total]:
            return 0
        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

easy

A. 59

B. 0

C. 60

D. 1

Solution

1. Step 1: Convert times to minutes and mark seen

   "01:01" -> 61, "02:01" -> 121, "01:02" -> 62; all unique, so no early return 0.

2. Step 2: Iterate over seen array to find minimum adjacent difference

   Adjacent times are 61 and 62 (diff 1), 62 and 121 (diff 59). Minimum difference is 1.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Minimum adjacent difference found is 1 minute [OK]

Hint: Check adjacent differences after sorting times [OK]

Common Mistakes:

• Confusing difference between 61 and 121 as minimum
• Forgetting to check circular difference
• Returning 0 incorrectly when no duplicates

2. Consider the following Python code implementing the Dutch National Flag algorithm:

def sortColors(nums):
    low, mid, high = 0, 0, len(nums) - 1
    while mid <= high:
        if nums[mid] == 0:
            nums[low], nums[mid] = nums[mid], nums[low]
            low += 1
            mid += 1
        elif nums[mid] == 1:
            mid += 1
        else:  # nums[mid] == 2
            nums[mid], nums[high] = nums[high], nums[mid]
            high -= 1

arr = [2, 0, 1]
sortColors(arr)
print(arr)

What is the output after the function call?

easy

A. [1, 0, 2]

B. [0, 2, 1]

C. [0, 1, 2]

D. [2, 0, 1]

Solution

1. Step 1: Trace first iteration with mid=0, high=2

   nums[mid]=2 triggers swap with nums[high]=1, array becomes [1,0,2], high=1, mid=0.

2. Step 2: Trace second iteration with mid=0, high=1

   nums[mid]=1, mid increments to 1; nums[mid]=0 triggers swap with nums[low]=1, array becomes [0,1,2], low=1, mid=2.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Array sorted as [0,1,2] after one pass [OK]

Hint: Swapping 2 with high pointer reduces problem size [OK]

Common Mistakes:

• Not updating mid after swapping 0
• Incrementing mid after swapping 2 (should not)
• Confusing low and mid pointers

3. You are given a matrix and asked to sort each diagonal (from top-left to bottom-right) independently in ascending order. Which algorithmic approach best guarantees an efficient and correct solution?

easy

A. Use a greedy approach to swap elements along diagonals until sorted.

B. Sort the entire matrix row-wise and column-wise repeatedly until diagonals are sorted.

C. Group elements by their diagonal key (row - column), sort each group, then reassign back.

D. Apply dynamic programming to find the longest sorted subsequence along diagonals.

Solution

1. Step 1: Identify diagonal grouping key

   Each diagonal can be uniquely identified by the difference between its row and column indices (row - col). Grouping elements by this key allows independent sorting.

2. Step 2: Sort and reassign elements per diagonal group

   Sorting each group separately and then placing elements back ensures diagonals are sorted without affecting others.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Grouping by row - col and sorting each group sorts diagonals correctly [OK]

Hint: Group by row - col to isolate diagonals [OK]

Common Mistakes:

• Trying to sort entire matrix repeatedly
• Using greedy swaps that don't guarantee sorted diagonals
• Applying DP unrelated to sorting diagonals

4. Given the following code snippet implementing the optimal wiggle sort, what is the content of the array nums after the while loop completes when the input is [1, 3, 2]?

easy

A. [2, 3, 1]

B. [1, 3, 2]

C. [3, 1, 2]

D. [1, 2, 3]

Solution

1. Step 1: Sort and find median

   Sorted nums = [1, 2, 3], median = nums[(3-1)//2] = nums[1] = 2.

2. Step 2: Apply virtual indexing and partition

   Virtual indices for i=0,1,2 are (1+2*0)%3=1, (1+2*1)%3=0, (1+2*2)%3=2. - i=0: nums[1]=2 equals median -> i=1 - i=1: nums[0]=1 less than median -> swap with nums[virtual_index(right=2)]=nums[2]=3, right=1 - After swap: nums=[3,2,1], i=1, right=1 - i=1: nums[0]=3 greater than median -> swap with nums[virtual_index(left=0)]=nums[1]=2, left=1, i=2 - Final nums=[2,3,1]

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Final array satisfies wiggle property: 2 < 3 > 1 [OK]

Hint: Trace virtual indices carefully to get final array [OK]

Common Mistakes:

• Confusing virtual index mapping
• Off-by-one in median calculation
• Not updating pointers correctly

5. The following code attempts to implement the Dutch National Flag algorithm but contains a subtle bug:

def sortColors(nums):
    low, mid, high = 0, 0, len(nums) - 1
    while mid <= high:
        if nums[mid] == 0:
            nums[low], nums[mid] = nums[mid], nums[low]
            low += 1
            # mid += 1  # Missing increment here
        elif nums[mid] == 1:
            mid += 1
        else:  # nums[mid] == 2
            nums[mid], nums[high] = nums[high], nums[mid]
            high -= 1

Which line contains the bug that causes incorrect behavior or infinite loops?

medium

A. Line where mid is incremented after swapping 0 (missing here)

B. Line where nums[mid] and nums[high] are swapped and high is decremented

C. Line where mid is incremented when nums[mid] == 1

D. Line where nums[low], nums[mid] are swapped and low is incremented

Solution

1. Step 1: Identify missing pointer update

   After swapping 0 to the front, mid must increment to avoid reprocessing the same element.

2. Step 2: Consequence of missing mid increment

   Without mid increment, mid stays pointing to swapped 0, causing infinite loop or incorrect order.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Missing mid increment after swapping 0 causes infinite loop [OK]

Hint: Always increment mid after swapping 0 to front [OK]

Common Mistakes:

• Forgetting to increment mid after swapping 0
• Incrementing mid after swapping 2 (wrong)
• Confusing roles of low and mid pointers