Introduction

The standard way to rearrange an array so that equal items are not adjacent is to always place the most frequent available item that is different from the one you just used. That makes the problem a good fit for a greedy algorithm backed by a max-heap or priority queue.

First check whether a valid arrangement exists

Not every input can be rearranged successfully. If one value appears too many times, it is impossible to separate all copies.

For an array of length n, a valid arrangement exists only if the maximum frequency is at most:

• '(n + 1) // 2'

For example:

• '[1, 1, 1, 2, 2] can be rearranged as [1, 2, 1, 2, 1]'
• '[1, 1, 1, 1, 2] cannot be rearranged without adjacent 1s'

That quick frequency test saves wasted work on impossible inputs.

Use a max-heap of remaining counts

The greedy idea is:

1. count the occurrences of each value
2. push them into a max-heap by remaining count
3. repeatedly take the most frequent available value
4. hold the previously used value out of the heap for one step so it cannot be chosen immediately again

This "cooldown of one position" is the crucial trick.

1from collections import Counter
2import heapq
3
4def rearrange(items):
5    counts = Counter(items)
6    n = len(items)
7
8    if max(counts.values()) > (n + 1) // 2:
9        return None
10
11    heap = [(-count, value) for value, count in counts.items()]
12    heapq.heapify(heap)
13
14    result = []
15    prev_count, prev_value = 0, None
16
17    while heap:
18        count, value = heapq.heappop(heap)
19        result.append(value)
20
21        if prev_count < 0:
22            heapq.heappush(heap, (prev_count, prev_value))
23
24        count += 1
25        prev_count, prev_value = count, value
26
27    return result
28
29
30print(rearrange([1, 1, 2, 2, 3, 3, 3]))

The heap stores negative counts because Python's heapq is a min-heap.

Why the greedy strategy works

The most frequent item is the hardest to place because it creates the highest risk of collisions. Using it as early as possible, while still preventing immediate repetition, reduces the chance of getting stuck later with several identical items remaining.

The held-back previous item is what keeps the arrangement valid. At each step:

• the just-used value cannot be chosen again immediately
• all other values remain eligible
• the most constrained remaining value still gets priority

That is why the approach works well for the adjacency constraint.

Variations of the same problem

This algorithm also appears in related tasks:

• reorganizing strings so identical characters are not adjacent
• scheduling tasks with a one-step cooldown
• interleaving categories to avoid clustering

If the rule becomes "keep identical items at least k positions apart," the same idea generalizes, but you need a longer cooldown queue instead of holding back only the previous item.

Complexity

Let n be the array length and k the number of distinct values.

• counting frequencies is O(n)
• each heap push or pop is O(log k)
• the full algorithm is O(n log k)

That is efficient enough for most practical inputs and much better than brute-force permutation search.

Common Pitfalls

The biggest mistake is trying to solve the problem by simple sorting or pairwise swapping. That may work on a few examples but fails when frequencies are uneven.

Another mistake is not checking feasibility first. If the most frequent item appears too often, no arrangement exists and the algorithm should return failure clearly.

Developers also forget to hold the previous item out of the heap for one step. Without that cooldown, the heap can immediately choose the same value again.

Finally, do not confuse this with the stronger k-distance version of the problem. Avoiding adjacency only needs a cooldown of one placement.

Summary

• The standard solution is greedy plus a max-heap of remaining frequencies.
• First check whether the maximum frequency exceeds (n + 1) // 2.
• Hold the previously used item out of the heap for one step to avoid immediate repetition.
• The resulting algorithm runs in O(n log k) time.
• The same pattern generalizes to strings, schedulers, and larger separation constraints.