Make the Array Beautiful (Sort + Greedy)

📋

Problem

Imagine you have a messy collection of colored beads on a string, and you want to rearrange them so that no two adjacent beads share the same color, making the string 'beautiful'.

Given an array of integers, rearrange the elements so that no two adjacent elements are equal. Return any such rearrangement if possible; otherwise, return an empty array.

1 ≤ n ≤ 10^50 ≤ array elements ≤ 10^9

Edge cases: All elements are the same → return []Array of length 1 → return the array itselfArray with two elements both equal → return []

</>

IDE

def make_array_beautiful(arr: list) -> list:public int[] makeArrayBeautiful(int[] arr)vector<int> makeArrayBeautiful(vector<int> &arr)function makeArrayBeautiful(arr)

def make_array_beautiful(arr):
    # Write your solution here
    pass

class Solution {
    public int[] makeArrayBeautiful(int[] arr) {
        // Write your solution here
        return new int[0];
    }
}

#include <vector>
using namespace std;

vector<int> makeArrayBeautiful(vector<int> &arr) {
    // Write your solution here
    return {};
}

function makeArrayBeautiful(arr) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: Returning empty array for all inputs without attempting rearrangement.✅ Implement sorting and greedy rearrangement logic to produce valid output when possible.

Wrong: 112233Returning input as is without rearrangement, causing adjacent duplicates.✅ Sort and rearrange elements to ensure no two adjacent are equal.

Wrong: 11Failing to detect impossible rearrangement when max frequency > half array length.✅ Add frequency check and return empty array if rearrangement impossible.

Wrong: 122333Greedy trap: sorting only without frequency-based placement leads to adjacent duplicates.✅ Use frequency counts and place elements alternately to avoid adjacency.

✓

Test Cases

Focus on handling base cases and detecting impossible rearrangements early.

Understand the frequency-based greedy approach and how to avoid common pitfalls.

Optimize your solution to O(n log n) by sorting and using efficient data structures.

t1_01basic

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

Expected[1,2,1,3,2,3]

⏱ Performance - must finish in 2000ms

One possible rearrangement where no two adjacent elements are equal.

💡 Try sorting the array and then rearranging elements to avoid duplicates.

💡 Use a greedy approach to place the most frequent elements first, then fill gaps.

💡 Interleave the sorted halves or use a max frequency check to rearrange properly.

Why it failed: Failed to rearrange to avoid adjacent duplicates; likely missed sorting or greedy placement. Fix by sorting and placing elements alternately from two halves.

✓ Correct rearrangement with no two adjacent elements equal.

t1_02basic

Input{"arr":[4,4,5,5,6,6,7,7]}

Expected[4,5,4,6,5,7,6,7]

⏱ Performance - must finish in 2000ms

Another valid rearrangement with no two adjacent elements equal.

💡 Sort and count frequencies to identify the most frequent elements.

💡 Place elements in a way that the same elements are spaced apart.

💡 Use a two-pointer or heap approach to alternate elements and avoid adjacency.

Why it failed: Incorrect output due to placing identical elements adjacently; fix by sorting and alternating placement from two halves or using a max heap.

✓ Correctly rearranged array with no adjacent duplicates.

t2_01edge

Input{"arr":[]}

Expected[]

⏱ Performance - must finish in 2000ms

Empty array input should return empty array.

💡 Consider the base case of empty input.

💡 No elements means no adjacent duplicates by default.

💡 Return the input as is if empty.

Why it failed: Failed to handle empty input; code should return empty array immediately.

✓ Correctly handled empty input.

t2_02edge

Input{"arr":[10]}

Expected[10]

⏱ Performance - must finish in 2000ms

Single element array returns itself as no adjacent duplicates possible.

💡 Check if array length is 1.

💡 Single element arrays are trivially beautiful.

💡 Return the array as is without rearrangement.

Why it failed: Failed to handle single element array; should return input unchanged.

✓ Correctly returned single element array.

t2_03edge

Input{"arr":[2,2]}

Expected[]

⏱ Performance - must finish in 2000ms

Two identical elements cannot be rearranged to avoid adjacency; return empty array.

💡 Check if any element frequency exceeds half the array length rounded up.

💡 If max frequency > (n+1)//2, no valid rearrangement exists.

💡 Return empty array if rearrangement impossible.

Why it failed: Failed to detect impossibility when max frequency > half array length; add frequency check and return empty array.

✓ Correctly returned empty array for impossible rearrangement.

t3_01corner

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

Expected[1,2,1,3,1,2,3]

⏱ Performance - must finish in 2000ms

Max frequency element exactly half the array length rounded up; valid rearrangement exists.

💡 Check max frequency against (n+1)//2 boundary condition.

💡 Place the most frequent element at even indices first.

💡 Fill remaining positions with other elements to avoid adjacency.

Why it failed: Failed to handle exact boundary max frequency; fix by placing max frequency elements at even indices first.

✓ Correctly handled exact boundary frequency case.

t3_02corner

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

Expected[2,3,2,3,2,1,3,1]

⏱ Performance - must finish in 2000ms

Greedy trap: naive sorting then placing may fail; must use frequency-based placement.

💡 Sorting alone is insufficient; consider element frequencies.

💡 Use a max heap or frequency array to pick the most frequent elements alternately.

💡 Avoid placing same elements consecutively by alternating picks.

Why it failed: Greedy trap: sorting only leads to adjacent duplicates; fix by using frequency counts and alternating placement.

✓ Correctly avoided greedy trap with frequency-based rearrangement.

t3_03corner

Input{"arr":[1,1,1,1,2,3,4,5]}

Expected[]

⏱ Performance - must finish in 2000ms

Max frequency element exceeds half array length; no valid rearrangement possible.

💡 Check if max frequency > (n+1)//2 to detect impossibility.

💡 Return empty array immediately if condition met.

💡 Avoid attempting rearrangement when impossible.

Why it failed: Failed to detect impossibility due to max frequency > half array length; add frequency check and return empty array.

✓ Correctly detected no solution due to high max frequency.

t4_01performance

Input{"arr":[1000000000,999999999,999999998,999999997,999999996,999999995,999999994,999999993,999999992,999999991,1000000000,999999999,999999998,999999997,999999996,999999995,999999994,999999993,999999992,999999991,1000000000,999999999,999999998,999999997,999999996,999999995,999999994,999999993,999999992,999999991,1000000000,999999999,999999998,999999997,999999996,999999995,999999994,999999993,999999992,999999991,1000000000,999999999,999999998,999999997,999999996,999999995,999999994,999999993,999999992,999999991,1000000000,999999999,999999998,999999997,999999996,999999995,999999994,999999993,999999992,999999991,1000000000,999999999,999999998,999999997,999999996,999999995,999999994,999999993,999999992,999999991,1000000000,999999999,999999998,999999997,999999996,999999995,999999994,999999993,999999992,999999991,1000000000,999999999,999999998,999999997,999999996,999999995,999999994,999999993,999999992,999999991,1000000000,999999999,999999998,999999997,999999996,999999995,999999994,999999993,999999992,999999991]}

Expectednull

⏱ Performance - must finish in 2000ms

Large input with n=100 to test O(n log n) or better complexity; must complete within 2 seconds.

💡 Sorting and frequency counting is O(n log n).

💡 Avoid brute force permutations which are O(n!).

💡 Use greedy rearrangement with max frequency check.

Why it failed: TLE due to brute force or inefficient approach; fix by using sorting + greedy frequency-based rearrangement with O(n log n) complexity.

✓ Efficient O(n log n) solution confirmed by passing performance test.

Practice

1. Consider the following Python code for finding the maximum gap in a list of integers. What is the value of max_gap after the second iteration of the for-loop when the input is [3, 6, 9, 1]?

from typing import List

def maximumGap(nums: List[int]) -> int:
    if len(nums) < 2:
        return 0
    min_num, max_num = min(nums), max(nums)
    if min_num == max_num:
        return 0
    nums.sort()
    max_gap = 0
    for i in range(1, len(nums)):
        max_gap = max(max_gap, nums[i] - nums[i-1])
    return max_gap

print(maximumGap([3,6,9,1]))  # Output: ?

easy

A. 3

B. 5

C. 6

D. 8

Solution

1. Step 1: Sort the input array

   Input: [3,6,9,1] -> Sorted: [1,3,6,9]

2. Step 2: Trace max_gap updates in the loop

   Iteration 1 (i=1): max_gap = max(0, 3-1) = 2 Iteration 2 (i=2): max_gap = max(2, 6-3) = 3

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   max_gap after second iteration is 3 [OK]

Hint: Sort first, then scan adjacent differences [OK]

Common Mistakes:

• Off-by-one errors in loop
• Using unsorted array differences
• Confusing iteration indices

2. Consider the following Python function to find the minimum absolute difference in an array. What is the returned value when the input is [4, 2, 1, 3]?

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

print(minimum_abs_difference([4, 2, 1, 3]))

easy

A. 1

B. 3

C. 2

D. 0

Solution

1. Step 1: Sort the array

   Sorted array is [1, 2, 3, 4].

2. Step 2: Iterate and check adjacent differences

   Differences: 2-1=1 -> triggers early return 1.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Early exit on diff==1 returns 1 [OK]

Hint: Early exit returns 1 on first adjacent difference of 1 [OK]

Common Mistakes:

• Forgetting early exit
• Returning difference between non-adjacent pairs

3. You are given an array containing only three distinct values representing colors: red, white, and blue. The goal is to sort the array so that all reds come first, followed by whites, then blues, in a single pass with constant extra space. Which algorithmic approach guarantees this optimal solution?

easy

A. Use a standard comparison-based sort like quicksort or mergesort to sort the array.

B. Use a three-pointer partitioning approach that rearranges elements in one pass, known as the Dutch National Flag algorithm.

C. Count the occurrences of each color and then overwrite the array in multiple passes.

D. Use dynamic programming to decide the position of each color based on previous states.

Solution

1. Step 1: Understand the problem constraints

   The problem requires sorting three distinct values in a single pass with O(1) extra space.

2. Step 2: Identify the algorithm that meets these constraints

   The Dutch National Flag algorithm uses three pointers to partition the array in one pass without extra space.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   One-pass, constant space sorting of three distinct values matches Dutch National Flag algorithm [OK]

Hint: One-pass, three-pointer partitioning solves this optimally [OK]

Common Mistakes:

• Thinking counting sort is optimal despite multiple passes
• Assuming comparison-based sorts are needed
• Confusing DP with sorting problems

4. Given the following code and input nums = [-4, -2, 2, 4], a = 1, b = 3, c = 5, what is the final returned array?

easy

A. [3, 9, 33, 15]

B. [33, 15, 9, 3]

C. [3, 9, 15, 33]

D. [15, 3, 9, 33]

Solution

1. Step 1: Compute transformed values

   For nums = [-4, -2, 2, 4], quad(x) = x² + 3x + 5: -4 -> 16 -12 + 5 = 9 -2 -> 4 -6 + 5 = 3 2 -> 4 + 6 + 5 = 15 4 -> 16 + 12 + 5 = 33

2. Step 2: Two pointers fill from end

   a >= 0, so fill result from end: Compare left_val=9 and right_val=33 -> 33 > 9, place 33 at result[3] Move right pointer left Next compare 9 and 15 -> 15 > 9, place 15 at result[2] Move right pointer left Next compare 9 and 3 -> 9 > 3, place 9 at result[1] Move left pointer right Finally place 3 at result[0] Result array is [3, 9, 15, 33]

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Output is sorted ascending: [3, 9, 15, 33] [OK]

Hint: Two pointers fill output from end or start based on a sign [OK]

Common Mistakes:

• Confusing index direction for filling output
• Mixing up left and right pointer values

5. You are given an unsorted array of integers and need to reorder it so that nums[0] < nums[1] > nums[2] < nums[3] > nums[4] and so on, ensuring a "wiggle" pattern. Which approach guarantees an optimal solution that runs in O(n log n) time and uses O(1) extra space?

easy

A. Use a greedy approach by swapping adjacent elements whenever the wiggle property is violated.

B. Sort the array, find the median, then rearrange elements in-place using virtual indexing and three-way partitioning.

C. Use dynamic programming to find the longest wiggle subsequence and reconstruct the array accordingly.

D. Sort the array and then alternate picking elements from the start and end into a new array.

Solution

1. Step 1: Understand the wiggle property requirements

   The problem requires elements to be reordered so that nums[0] < nums[1] > nums[2] < nums[3] > nums[4]..., which is not guaranteed by simple sorting or greedy swaps.

2. Step 2: Identify the approach that ensures correct interleaving

   Sorting and then using the median with virtual indexing and three-way partitioning ensures elements greater than median are placed at odd indices and smaller at even indices, maintaining the wiggle property in O(n log n) time and O(1) space.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Virtual indexing and median partitioning guarantee wiggle order [OK]

Hint: Virtual indexing with median partitioning ensures wiggle order [OK]

Common Mistakes:

• Assuming greedy swaps fix all cases
• Using DP for rearrangement instead of subsequence
• Ignoring in-place rearrangement for space efficiency