LeetCode 1054 - Distant Barcodes

The problem is asking us to rearrange a list of barcodes so that no two adjacent barcodes are the same. The input is an array barcodes of integers where each integer represents a type of barcode. The output should be a rearranged array that satisfies the adjacency constraint.

leetcodemediumarrayhash-tablegreedysortingheap-(priority-queue)counting

LeetCode Problem 1054

Difficulty: 🟡 Medium
Topics: Array, Hash Table, Greedy, Sorting, Heap (Priority Queue), Counting

Solution

Problem Understanding

The problem is asking us to rearrange a list of barcodes so that no two adjacent barcodes are the same. The input is an array barcodes of integers where each integer represents a type of barcode. The output should be a rearranged array that satisfies the adjacency constraint. The constraints specify that the array length is at most 10,000 and barcode values are positive integers up to 10,000.

This tells us the input size is moderate and we need an efficient algorithm, preferably O(n log n) or O(n). The problem guarantees that a solution exists, so we do not need to handle impossible cases. Important edge cases include an array where all barcodes are the same except one, or arrays where multiple barcodes have the same maximum frequency. These could trip up naive solutions if they try to place the same barcode consecutively without checking.

Approaches

A brute-force approach would generate all possible permutations of the array and check each one for the adjacency constraint. This is guaranteed to find a correct solution because we are checking every arrangement, but the time complexity is factorial in the size of the input (O(n!)), which is infeasible for arrays up to length 10,000.

The key observation for an optimal solution is that if we always place the most frequent remaining barcode at positions that maximize distance from identical barcodes, we can avoid adjacency conflicts. Specifically, using a max-heap (priority queue) to always pick the barcode with the highest remaining count ensures that no two identical barcodes are adjacent. If we place barcodes in a pattern where the most frequent items occupy alternating positions first, the problem can be solved efficiently in O(n log k) time, where k is the number of distinct barcodes.

Approach Time Complexity Space Complexity Notes
Brute Force O(n!) O(n) Generate all permutations and check adjacency
Optimal O(n log k) O(k) Use a max-heap to place most frequent barcodes first

Algorithm Walkthrough

  1. Count the frequency of each barcode using a hash map. This allows us to know which barcode appears the most and how many times we need to place it.
  2. Push each barcode along with its negative frequency into a max-heap (priority queue). Using negative frequency ensures the heap acts as a max-heap since most languages provide min-heap by default.
  3. Initialize an empty list for the result.
  4. While the heap has more than one element, pop the two most frequent barcodes. This guarantees we never place the same barcode consecutively.
  5. Append the two barcodes to the result list in order. Decrease their counts and if either still has remaining frequency, push them back into the heap.
  6. If there is one barcode left in the heap after the loop, append it to the result.
  7. Return the result array.

Why it works: The algorithm always places the most frequent barcode available at positions that prevent adjacency with the same barcode. By always taking the top two barcodes from the heap, we ensure that no identical barcodes are adjacent. This property guarantees a valid solution.

Python Solution

from typing import List
from collections import Counter
import heapq

class Solution:
    def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]:
        # Step 1: Count frequencies
        freq = Counter(barcodes)
        
        # Step 2: Build max-heap with negative counts
        max_heap = [(-count, barcode) for barcode, count in freq.items()]
        heapq.heapify(max_heap)
        
        result = []
        
        # Step 4-5: Pop two most frequent barcodes at a time
        while len(max_heap) > 1:
            count1, barcode1 = heapq.heappop(max_heap)
            count2, barcode2 = heapq.heappop(max_heap)
            
            result.append(barcode1)
            result.append(barcode2)
            
            if count1 + 1 < 0:
                heapq.heappush(max_heap, (count1 + 1, barcode1))
            if count2 + 1 < 0:
                heapq.heappush(max_heap, (count2 + 1, barcode2))
        
        # Step 6: Handle the last barcode if any
        if max_heap:
            result.append(max_heap[0][1])
        
        return result

The implementation first counts barcode frequencies and stores them in a heap for efficient retrieval of the most frequent barcodes. The main loop extracts the two most frequent barcodes and appends them to the result while decrementing their counts. Remaining barcodes are pushed back into the heap. Finally, if one barcode remains, it is appended to the end. This directly mirrors the algorithm steps and ensures no two identical barcodes are adjacent.

Go Solution

package main

import (
    "container/heap"
)

type Item struct {
    val   int
    count int
}

type MaxHeap []Item

func (h MaxHeap) Len() int            { return len(h) }
func (h MaxHeap) Less(i, j int) bool  { return h[i].count > h[j].count }
func (h MaxHeap) Swap(i, j int)       { h[i], h[j] = h[j], h[i] }
func (h *MaxHeap) Push(x any)         { *h = append(*h, x.(Item)) }
func (h *MaxHeap) Pop() any {
    old := *h
    n := len(old)
    item := old[n-1]
    *h = old[0 : n-1]
    return item
}

func rearrangeBarcodes(barcodes []int) []int {
    freq := make(map[int]int)
    for _, b := range barcodes {
        freq[b]++
    }

    h := &MaxHeap{}
    heap.Init(h)
    for val, count := range freq {
        heap.Push(h, Item{val, count})
    }

    result := make([]int, 0, len(barcodes))
    for h.Len() > 1 {
        first := heap.Pop(h).(Item)
        second := heap.Pop(h).(Item)

        result = append(result, first.val, second.val)
        first.count--
        second.count--
        if first.count > 0 {
            heap.Push(h, first)
        }
        if second.count > 0 {
            heap.Push(h, second)
        }
    }

    if h.Len() > 0 {
        result = append(result, heap.Pop(h).(Item).val)
    }

    return result
}

The Go version mirrors the Python solution but uses the container/heap package to implement a max-heap. Structs are used to store barcode values and counts. The heap operations handle push and pop efficiently. Unlike Python, Go requires explicit struct handling for heap elements.

Worked Examples

Example 1: [1,1,1,2,2,2]

Step Heap Content (-count, barcode) Result
Initial [(-3,1),(-3,2)] []
1 Pop (-3,1), (-3,2) [1,2]
Push back (-2,1), (-2,2) [(-2,1),(-2,2)]
2 Pop (-2,1), (-2,2) [1,2,1,2]
Push back (-1,1), (-1,2) [(-1,1),(-1,2)]
3 Pop (-1,1), (-1,2) [1,2,1,2,1,2]

Example 2: [1,1,1,1,2,2,3,3]

Step Heap Content Result
Initial [(-4,1),(-2,2),(-2,3)] []
1 Pop (-4,1), (-2,2) [1,2]
Push back (-3,1), (-1,2) [(-3,1),(-2,3),(-1,2)]
2 Pop (-3,1), (-2,3) [1,2,1,3]
Push back (-2,1), (-1,3) [(-2,1),(-1,2),(-1,3)]
3 Pop (-2,1), (-1,2) [1,2,1,3,1,2]
4 Pop (-1,1), (-1,3) [1,2,1,3,1,2,1,3]

Complexity Analysis

Measure Complexity Explanation
Time O(n log k) Counting takes O(n), heap operations take O(log k) per element, with n elements total
Space O(k) Frequency map and heap store up to k unique barcodes

The complexity reasoning is based on the fact that each element is pushed and popped at most once from the heap, and k is the number of distinct barcodes, which is at most n.

Test Cases

# Provided examples
assert sorted(Solution().rearrangeBarcodes([1,1,1,2,2,2])) == [1,1,1,2,2,2]  # adjacency valid
assert