MediumNo. 1054
Distant Barcodes — LeetCode 1054 Python Solution
- Pattern
- Heap / Priority Queue
- Topics
- Greedy, Array, Hash Table, Counting, Sorting, Heap (Priority Queue)
- Reading time
- 2 min
- Source
- leetcode.com
The problem
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.
Example
- Input
- barcodes = [1,1,1,2,2,2]
- Output
- [2,1,2,1,2,1]
Python solution
class Solution:
def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]:
cnt = Counter(barcodes)
barcodes.sort(key=lambda x: (-cnt[x], x))
n = len(barcodes)
ans = [0] * len(barcodes)
ans[::2] = barcodes[: (n + 1) // 2]
ans[1::2] = barcodes[(n + 1) // 2 :]
return ansComplexity
- Time
- O(n × log n)
- Space · auxiliary
- O(M)
Pattern: Heap / Priority Queue
Keep only the best k elements, or always pull the smallest, in log time. LeetCode 1054. Distant Barcodes is filed here because LeetCode tags it Heap (Priority Queue), which is the vocabulary this hub collects.
The heap / priority queue guide has the Python template for the pattern and the 163 LeetCode problems that use it.
Related problems
| No. | Problem | Difficulty |
|---|---|---|
| 0621 | Task Scheduler | Medium |
| 0347 | Top K Frequent Elements | Medium |
| 0632 | Smallest Range Covering Elements from K Lists | Hard |
| 0692 | Top K Frequent Words | Medium |
| 0767 | Reorganize String | Medium |
| 1090 | Largest Values From Labels | Medium |
Frequently asked questions
- How hard is LeetCode 1054. Distant Barcodes?
LeetCode 1054. Distant Barcodes is rated Medium on LeetCode.
- What is the time complexity of LeetCode 1054. Distant Barcodes?
The Python solution on this page runs in O(n × log n).
- What is the space complexity of LeetCode 1054. Distant Barcodes?
The Python solution on this page uses O(M) auxiliary space.
- What topics does LeetCode 1054. Distant Barcodes cover?
LeetCode 1054. Distant Barcodes is tagged Greedy, Array, Hash Table, Counting, Sorting and Heap (Priority Queue) on LeetCode.