Distant Barcodes

Distant Barcodes is a Medium Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Greedy Patterns pattern, in the Task Scheduling (Frequency Based) subpattern.

Problem statement

In a warehouse, there is a row of barcodes, where the ith 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.

Example 1: Input: barcodes = [1,1,1,2,2,2] Output: [2,1,2,1,2,1]

Example 2: Input: barcodes = [1,1,1,1,2,2,3,3] Output: [1,3,1,3,1,2,1,2]

Constraints: 1 <= barcodes.length <= 10000 1 <= barcodes[i] <= 10000

Topics and companies

Topics: Heap, Sort.

Reported in interviews at Bloomberg.

How to practise Distant Barcodes on Thita.ai

Starter code is provided in C, C#, C++, dart, elixir, erlang, Go, Java, JavaScript, Kotlin, PHP, Python, python3, racket, Ruby, Rust, Scala, Swift and TypeScript. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(n) time and O(k) space.

Open Distant Barcodes in the code editor, or read the Distant Barcodes editorial for a worked solution with its approach and complexity analysis.

Where Distant Barcodes sits in the DSA pattern sheet

• Greedy Patterns pattern guide
• Task Scheduling (Frequency Based) subpattern
• The full DSA patterns sheet
• All coding practice problems

Problems related to Distant Barcodes

Other problems that use the same Task Scheduling (Frequency Based) and Greedy Patterns techniques:

• Task Scheduler — Medium, same subpattern
• Assign Cookies — Easy, same pattern
• Candy — Hard, same pattern
• Divide Intervals Into Minimum Number of Groups — Medium, same pattern
• Employee Free Time — Hard, same pattern
• Gas Station — Medium, same pattern