Distant Barcodes - Practice Coding Problems

Distant Barcodes - Problem

Array Hash Table Greedy Sorting Heap (Priority Queue) Counting Medium

In a warehouse, there is a row of barcodes, where the i-th barcode is barcodes[i].

Rearrange the barcodes so that no two adjacent barcodes are equal. You may return any answer, and it is guaranteed an answer exists.

Input & Output

Example 1 — Basic Case

$ Input: barcodes = [1,1,2,2,3,2]

› Output: [2,1,2,1,2,3]

💡 Note: Rearrange so no adjacent elements are equal. We place the most frequent element (2) in alternating positions, then fill remaining spots with other elements.

Example 2 — Minimum Size

$ Input: barcodes = [1,2]

› Output: [1,2]

💡 Note: Already arranged correctly - no two adjacent elements are the same.

Example 3 — All Same Frequency

$ Input: barcodes = [1,2,3,1,2,3]

› Output: [1,2,1,3,2,3]

💡 Note: When all elements have same frequency, any valid alternating arrangement works.

Constraints

1 ≤ barcodes.length ≤ 10⁴
1 ≤ barcodes[i] ≤ 10⁴

Visualization

Tap to expand

Understanding the Visualization

Input Array

Original barcodes with potential adjacent duplicates

Frequency Analysis

Count how often each barcode appears

Rearranged Output

No two adjacent barcodes are the same

Key Takeaway

🎯 Key Insight: Place the most frequent elements in alternating positions to prevent adjacent duplicates while using all elements efficiently.

Asked in

G Google 25 a Amazon 20 M Microsoft 15 f Facebook 12

The key insight is to place the most frequent elements first in alternating positions to prevent adjacency. The optimal approach uses frequency counting with alternating placement - count frequencies, sort by frequency, then fill even positions first followed by odd positions. Time: O(n log k), Space: O(n).

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Try All Permutations	O(n! × n)	O(n)	Generate all possible arrangements until finding one with no adjacent duplicates
Frequency Count with Alternating Placement	O(n log k)	O(n)	Count frequencies, place most frequent elements in even positions first
Priority Queue (Max Heap)	O(n log k)	O(k)	Use max heap to always pick the most frequent remaining element that won't create adjacent duplicates

Brute Force - Try All Permutations — Algorithm Steps

Step 1: Generate all permutations of the input array
Step 2: For each permutation, check if adjacent elements are different
Step 3: Return the first valid permutation found

Visualization

Tap to expand

Step-by-Step Walkthrough

Generate Permutations

Create all possible arrangements

Check Adjacent Elements

Verify no two adjacent elements are equal

Return Valid Arrangement

First valid permutation is the answer

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int isValid(int* arr, int size) {
    for (int i = 0; i < size - 1; i++) {
        if (arr[i] == arr[i + 1]) return 0;
    }
    return 1;
}

void swap(int* a, int* b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

int permute(int* arr, int start, int size) {
    if (start >= size) {
        return isValid(arr, size);
    }
    
    for (int i = start; i < size; i++) {
        swap(&arr[start], &arr[i]);
        if (permute(arr, start + 1, size)) return 1;
        swap(&arr[start], &arr[i]);
    }
    return 0;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    line[strcspn(line, "\n")] = 0;
    
    int barcodes[1000];
    int size = 0;
    
    char* token = strtok(line + 1, ",]");
    while (token != NULL) {
        barcodes[size++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    permute(barcodes, 0, size);
    
    printf("[");
    for (int i = 0; i < size; i++) {
        printf("%d", barcodes[i]);
        if (i < size - 1) printf(",");
    }
    printf("]\n");
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n! × n)

Generate n! permutations, check each one takes O(n) time

⚠ Quadratic Growth

Space Complexity

O(n)

Store one permutation at a time plus recursion stack

⚡ Linearithmic Space

32.0K Views

Medium Frequency

~15 min Avg. Time

847 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Try All Permutations — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler