Distant Barcodes

LeetCode 1054: Distant Barcodes Solution & Explanation

Problem Overview

TL;DR: To ensure no two adjacent barcodes are identical, we greedily select the most frequent available barcode that is different from the previously placed one using a Max Heap.

The LeetCode 1054 problem, titled "Distant Barcodes," asks us to rearrange an array of integers (representing barcodes) such that no two adjacent elements are equal. We are guaranteed that a solution always exists for the given input. This is a classic combinatorial optimization problem that requires organizing data based on frequency constraints.

Brute Force Approach for Distant Barcodes

The naive approach to solving Distant Barcodes involves generating every possible permutation of the input array and checking each one for validity.

1. Generate all unique permutations of the barcodes array.
2. Iterate through each permutation.
3. For each permutation, check if arr[i] == arr[i+1] for any i.
4. Return the first permutation that satisfies the condition.

1# Pseudo-code for Brute Force
2def rearrangeBarcodes(barcodes):
3    for perm in generate_all_permutations(barcodes):
4        valid = True
5        for i in range(len(perm) - 1):
6            if perm[i] == perm[i+1]:
7                valid = False
8                break
9        if valid:
10            return perm

Time Complexity: $O(N! \cdot N)$. Generating permutations is factorial in complexity. Space Complexity: $O(N)$ to store the recursion stack or current permutation.

Why it fails: The constraints state that barcodes.length can be up to 10,000. Calculating $10000!$ is computationally impossible. This approach will result in a Time Limit Exceeded (TLE) error almost immediately for any non-trivial input.

Algorithm Strategy: Greedy Patterns

To implement the Greedy - Task Scheduling strategy, we utilize a Max Heap (Priority Queue).

1. Frequency Map: First, count the occurrences of each barcode.
2. Max Heap Construction: Insert all unique barcodes into a Max Heap, ordered by their frequency counts. This allows $O(1)$ access to the most frequent available barcode.
3. Greedy Placement:
   • Extract the most frequent element (current) from the heap.
   • Append it to the result array.
   • Decrement its count.
   • Blocking Mechanism: We cannot immediately push current back into the heap because it might be picked again in the very next step (which would violate the adjacency rule).
   • Instead, we hold current in a temporary variable (previous).
   • We push the old previous (if it has a count $> 0$) back into the heap.
   • This ensures that at any step, the heap contains all valid candidates except the one just placed.
4. Termination: Repeat until the result array is full.

Execution Flow

Let's trace the algorithm with barcodes = [1, 1, 1, 2, 2, 3].

1. Count Frequencies: {1: 3, 2: 2, 3: 1}.
2. Initialize Heap: [(3, 1), (2, 2), (1, 3)] (Format: (count, value)).
3. Initialize Variables: result = [], previous = null.

Iteration 1:

• Pop (3, 1) from heap. Heap is [(2, 2), (1, 3)].
• Append 1 to result. result = [1].
• Decrement count: (2, 1).
• previous was null, so nothing to push back.
• Update previous = (2, 1).

Iteration 2:

• Pop (2, 2) from heap. Heap is [(1, 3)].
• Append 2 to result. result = [1, 2].
• Decrement count: (1, 2).
• Push previous (which is (2, 1)) back to heap. Heap is [(2, 1), (1, 3)].
• Update previous = (1, 2).

Iteration 3:

• Pop (2, 1) from heap. Heap is [(1, 3)].
• Append 1 to result. result = [1, 2, 1].
• Decrement count: (1, 1).
• Push previous (which is (1, 2)) back to heap. Heap is [(1, 2), (1, 3)].
• Update previous = (1, 1).

Iteration 4:

• Pop (1, 2) from heap. Heap is [(1, 3)].
• Append 2 to result. result = [1, 2, 1, 2].
• Decrement count: (0, 2).
• Push previous (which is (1, 1)) back to heap. Heap is [(1, 1), (1, 3)].
• Update previous = (0, 2).

Iteration 5:

• Pop (1, 1) from heap. Heap is [(1, 3)].
• Append 1 to result. result = [1, 2, 1, 2, 1].
• Decrement count: (0, 1).
• Push previous (which is (0, 2)) back. (Count is 0, typically we discard it).
• Update previous = (0, 1).

Iteration 6:

• Pop (1, 3) from heap. Heap is empty.
• Append 3 to result. result = [1, 2, 1, 2, 1, 3].
• Decrement count: (0, 3).
• Update previous = (0, 3).

End: Heap is empty. Result is [1, 2, 1, 2, 1, 3]. Note that this is a valid permutation where no adjacent elements are equal.

Proof of Correctness

The correctness relies on the invariant that we always reduce the count of the majority element.

Let $N$ be the total number of barcodes and $F_{max}$ be the frequency of the most common barcode. The problem guarantees a solution exists, which implies $F_{max} \le \lceil N/2 \rceil$.

By using a Max Heap, we ensure that if a barcode has a disproportionately high frequency, it is selected as often as possible (every other turn). This prevents the "pigeonhole principle" failure case where we are left with $k$ slots and $k$ identical items. The blocking mechanism (holding the previous item) strictly enforces the constraint result[i] != result[i-1]. Since a valid arrangement is guaranteed by the problem statement, this greedy consumption of the most frequent elements will always successfully construct the array.

Pattern Reuse Notes

The Greedy - Task Scheduling pattern used in LeetCode 1054 is highly transferable. Mastering this logic helps you solve:

• LeetCode 621: Task Scheduler: Instead of just rearranging, you calculate the total CPU intervals required including idle times. The core logic of processing the most frequent task first is identical.
• LeetCode 767: Reorganize String: This is virtually the same problem as Distant Barcodes, but with characters instead of integers. The constraints and the "hold/block" heap logic are exactly the same.

Reference Implementation

C++ Solution for LeetCode 1054

1#include <vector>
2#include <unordered_map>
3#include <queue>
4
5using namespace std;
6
7class Solution {
8public:
9    vector<int> rearrangeBarcodes(vector<int>& barcodes) {
10        // Step 1: Count frequencies
11        unordered_map<int, int> countMap;
12        for (int code : barcodes) {
13            countMap[code]++;
14        }
15
16        // Step 2: Max Heap to store {frequency, barcode}
17        priority_queue<pair<int, int>> maxHeap;
18        for (auto& entry : countMap) {
19            maxHeap.push({entry.second, entry.first});
20        }
21
22        vector<int> result;
23        // 'prev' holds the element we just placed so we don't pick it immediately
24        pair<int, int> prev = {-1, -1}; 
25
26        // Step 3: Greedy placement
27        while (!maxHeap.empty()) {
28            pair<int, int> current = maxHeap.top();
29            maxHeap.pop();
30
31            // Add to result
32            result.push_back(current.second);
33            current.first--;
34
35            // If the PREVIOUS element still has count > 0, put it back in heap
36            // We do this now because it is no longer adjacent to the current position
37            if (prev.first > 0) {
38                maxHeap.push(prev);
39            }
40
41            // Update prev to be the current element (blocked for next iteration)
42            prev = current;
43        }
44
45        return result;
46    }
47};

Java Solution for LeetCode 1054

1import java.util.*;
2
3class Solution {
4    public int[] rearrangeBarcodes(int[] barcodes) {
5        // Step 1: Count frequencies
6        Map<Integer, Integer> countMap = new HashMap<>();
7        for (int code : barcodes) {
8            countMap.put(code, countMap.getOrDefault(code, 0) + 1);
9        }
10
11        // Step 2: Max Heap (PriorityQueue) based on frequency
12        PriorityQueue<int[]> maxHeap = new PriorityQueue<>((a, b) -> b[0] - a[0]);
13        for (Map.Entry<Integer, Integer> entry : countMap.entrySet()) {
14            maxHeap.offer(new int[]{entry.getValue(), entry.getKey()});
15        }
16
17        int[] result = new int[barcodes.length];
18        int index = 0;
19        
20        // 'prev' holds the element just placed; blocked for immediate reuse
21        int[] prev = null;
22
23        // Step 3: Greedy placement
24        while (!maxHeap.isEmpty()) {
25            int[] current = maxHeap.poll();
26            
27            result[index++] = current[1];
28            current[0]--; // Decrement frequency
29
30            // If we had a previous element with remaining count, it's now safe to re-add
31            if (prev != null && prev[0] > 0) {
32                maxHeap.offer(prev);
33            }
34
35            // The current element becomes the previous one (blocked)
36            prev = current;
37        }
38
39        return result;
40    }
41}

Python Solution for LeetCode 1054

1import heapq
2from collections import Counter
3
4class Solution:
5    def rearrangeBarcodes(self, barcodes: list[int]) -> list[int]:
6        # Step 1: Count frequencies
7        count_map = Counter(barcodes)
8        
9        # Step 2: Max Heap. Python has min-heap, so we negate counts.
10        # Storing as (-count, value)
11        max_heap = []
12        for code, count in count_map.items():
13            heapq.heappush(max_heap, (-count, code))
14            
15        result = []
16        # 'prev_count' and 'prev_val' hold the blocked element
17        prev_count, prev_val = 0, 0
18        
19        # Step 3: Greedy placement
20        while max_heap:
21            count, val = heapq.heappop(max_heap)
22            
23            # Add to result
24            result.append(val)
25            
26            # Since we used one, increment the negative count (effectively decrementing)
27            # e.g., -3 becomes -2
28            count += 1
29            
30            # If there was a previous element blocked with remaining count, push it back
31            if prev_count < 0:
32                heapq.heappush(max_heap, (prev_count, prev_val))
33            
34            # Update prev to current
35            prev_count, prev_val = count, val
36            
37        return result