MediumNo. 1057LeetCode Premium
Campus Bikes — LeetCode 1057 Python Solution
- Pattern
- Heap / Priority Queue
- Topics
- Array, Sorting, Heap (Priority Queue)
- Reading time
- 3 min
- Source
- leetcode.com
The problem
On a campus represented on the X-Y plane, there are n workers and m bikes, with n <= m. You are given an array workers of length n where workers[i] = [xi, yi] is the position of the ith worker.
Example
- Input
- workers = [[0,0],[2,1]], bikes = [[1,2],[3,3]]
- Output
- [1,0]
- Explanation
- Worker 1 grabs Bike 0 as they are closest (without ties), and Worker 0 is assigned Bike 1. So the output is [1, 0].
Python solution
class Solution:
def assignBikes(
self, workers: List[List[int]], bikes: List[List[int]]
) -> List[int]:
n, m = len(workers), len(bikes)
arr = []
for i, j in product(range(n), range(m)):
dist = abs(workers[i][0] - bikes[j][0]) + abs(workers[i][1] - bikes[j][1])
arr.append((dist, i, j))
arr.sort()
vis1 = [False] * n
vis2 = [False] * m
ans = [0] * n
for _, i, j in arr:
if not vis1[i] and not vis2[j]:
vis1[i] = vis2[j] = True
ans[i] = j
return ansComplexity
- Time
- O(n log n)
- Space · auxiliary
- O(n)
Pattern: Heap / Priority Queue
Keep only the best k elements, or always pull the smallest, in log time. LeetCode 1057. Campus Bikes is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Heap (Priority Queue).
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 |
|---|---|---|
| 0215 | Kth Largest Element in an Array | Medium |
| 0218 | The Skyline Problem | Hard |
| 0506 | Relative Ranks | Easy |
| 0912 | Sort an Array | Medium |
| 0973 | K Closest Points to Origin | Medium |
| 1094 | Car Pooling | Medium |
Frequently asked questions
- How hard is LeetCode 1057. Campus Bikes?
LeetCode 1057. Campus Bikes is rated Medium on LeetCode.
- What is the time complexity of LeetCode 1057. Campus Bikes?
The Python solution on this page runs in O(n log n).
- What is the space complexity of LeetCode 1057. Campus Bikes?
The Python solution on this page uses O(n) auxiliary space.
- What topics does LeetCode 1057. Campus Bikes cover?
LeetCode 1057. Campus Bikes is tagged Array, Sorting and Heap (Priority Queue) on LeetCode.
- Is LeetCode 1057. Campus Bikes a premium problem?
Yes. LeetCode 1057. Campus Bikes is a LeetCode Premium problem, so the full statement and test cases require a paid LeetCode subscription.