Campus Bikes - Practice Coding Problems

Campus Bikes - 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. You are also given an array bikes of length m where bikes[j] = [xj, yj] is the position of the jth bike.

Assign a bike to each worker using the following rules:

1. Among all available (worker, bike) pairs, choose the one with the shortest Manhattan distance
2. If there are ties, choose the pair with the smallest worker index
3. If there are still ties, choose the pair with the smallest bike index
4. Repeat until all workers have bikes

Return an array answer where answer[i] is the index of the bike assigned to the ith worker.

The Manhattan distance between two points p1 and p2 is: |p1.x - p2.x| + |p1.y - p2.y|

Input & Output

Example 1 — Basic Assignment

$ Input: workers = [[0,0],[2,1]], bikes = [[1,2],[3,3],[2,1]]

› Output: [1,2]

💡 Note: Worker 0 at (0,0): distances to bikes are [3,6,3]. Worker 1 at (2,1): distances are [3,3,1]. Closest pair is (worker 1, bike 2) with distance 1, so assign worker 1 → bike 2. Next closest available is (worker 0, bike 1) with distance 6, so worker 0 → bike 1.

Example 2 — Tie-breaking by Worker Index

$ Input: workers = [[0,0],[1,1],[2,0]], bikes = [[1,0],[2,2],[2,1]]

› Output: [0,2,1]

💡 Note: Multiple pairs have distance 2. When tied, we choose smaller worker index first, then smaller bike index. Worker 0 gets bike 0 (distance 1), worker 1 gets bike 2 (distance 1), worker 2 gets bike 1 (distance 2).

Example 3 — Single Worker

$ Input: workers = [[0,0]], bikes = [[1,1],[2,2],[3,3]]

› Output: [0]

💡 Note: Only one worker at (0,0). Distances to bikes are [2,4,6]. Closest bike is at index 0 with distance 2, so assign worker 0 → bike 0.

Constraints

n == workers.length
m == bikes.length
1 ≤ n ≤ m ≤ 1000
workers[i].length == bikes[j].length == 2
0 ≤ workers[i][0], workers[i][1], bikes[j][0], bikes[j][1] < 1000
All worker and bike locations are unique

Visualization

Tap to expand

Understanding the Visualization

Input

Workers and bikes at specific coordinates

Calculate Distances

Find Manhattan distance between all pairs

Greedy Assignment

Assign based on distance and tie-breaking rules

Key Takeaway

🎯 Key Insight: Greedy assignment with proper tie-breaking (distance → worker → bike) ensures optimal solution

Asked in

G Google 45 a Amazon 38 f Facebook 32 🍎 Apple 28

The key insight is to use greedy assignment with proper tie-breaking rules. Generate all worker-bike distance pairs, sort by distance/worker/bike priority, then assign greedily. Best approach is brute force sorting for simplicity or priority queue for memory efficiency. Time: O(nm log(nm)), Space: O(nm).

Common Approaches

Approach	Time	Space	Notes
✓ Priority Queue Optimization	O(nm log(nm))	O(nm)	Use min-heap to efficiently get the next best assignment without sorting all pairs
Brute Force - All Combinations	O(nm log(nm))	O(nm)	Calculate all worker-bike distances and sort to find optimal assignments

Priority Queue Optimization — Algorithm Steps

Initialize heap with all pairs from first unassigned worker
Pop minimum distance pair and assign if both are available
Add new pairs to heap as workers get assigned

Visualization

Tap to expand

Step-by-Step Walkthrough

Initialize Heap

Start with pairs from first worker

Pop & Assign

Get minimum distance pair, assign if available

Add Next Worker

Dynamically add pairs for next worker

Code -

solution.c — C

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

typedef struct {
    int dist, worker, bike;
} Pair;

typedef struct {
    Pair* data;
    int size;
    int capacity;
} MinHeap;

MinHeap* createHeap(int capacity) {
    MinHeap* heap = malloc(sizeof(MinHeap));
    heap->data = malloc(capacity * sizeof(Pair));
    heap->size = 0;
    heap->capacity = capacity;
    return heap;
}

void heapifyUp(MinHeap* heap, int idx) {
    while (idx > 0) {
        int parent = (idx - 1) / 2;
        Pair* curr = &heap->data[idx];
        Pair* par = &heap->data[parent];
        
        int cmp = (curr->dist != par->dist) ? (curr->dist - par->dist) :
                  (curr->worker != par->worker) ? (curr->worker - par->worker) :
                  (curr->bike - par->bike);
        
        if (cmp >= 0) break;
        
        Pair temp = *curr;
        *curr = *par;
        *par = temp;
        idx = parent;
    }
}

void heapifyDown(MinHeap* heap, int idx) {
    while (2 * idx + 1 < heap->size) {
        int left = 2 * idx + 1;
        int right = 2 * idx + 2;
        int minChild = left;
        
        if (right < heap->size) {
            Pair* leftP = &heap->data[left];
            Pair* rightP = &heap->data[right];
            int cmp = (leftP->dist != rightP->dist) ? (leftP->dist - rightP->dist) :
                      (leftP->worker != rightP->worker) ? (leftP->worker - rightP->worker) :
                      (leftP->bike - rightP->bike);
            if (cmp > 0) minChild = right;
        }
        
        Pair* curr = &heap->data[idx];
        Pair* child = &heap->data[minChild];
        int cmp = (curr->dist != child->dist) ? (curr->dist - child->dist) :
                  (curr->worker != child->worker) ? (curr->worker - child->worker) :
                  (curr->bike - child->bike);
        
        if (cmp <= 0) break;
        
        Pair temp = *curr;
        *curr = *child;
        *child = temp;
        idx = minChild;
    }
}

void push(MinHeap* heap, Pair p) {
    if (heap->size >= heap->capacity) return;
    heap->data[heap->size] = p;
    heapifyUp(heap, heap->size);
    heap->size++;
}

Pair pop(MinHeap* heap) {
    Pair min = heap->data[0];
    heap->data[0] = heap->data[--heap->size];
    heapifyDown(heap, 0);
    return min;
}

int* solution(int** workers, int workersSize, int** bikes, int bikesSize, int* returnSize) {
    *returnSize = workersSize;
    MinHeap* heap = createHeap(workersSize * bikesSize);
    
    // Add all pairs from worker 0 initially
    for (int j = 0; j < bikesSize; j++) {
        int dist = abs(workers[0][0] - bikes[j][0]) + abs(workers[0][1] - bikes[j][1]);
        push(heap, (Pair){dist, 0, j});
    }
    
    int* result = malloc(workersSize * sizeof(int));
    int* usedBikes = calloc(bikesSize, sizeof(int));
    
    for (int i = 0; i < workersSize; i++) {
        result[i] = -1;
    }
    
    int nextWorkerToAdd = 1;
    
    while (heap->size > 0) {
        Pair curr = pop(heap);
        
        if (result[curr.worker] != -1 || usedBikes[curr.bike]) {
            continue;
        }
        
        result[curr.worker] = curr.bike;
        usedBikes[curr.bike] = 1;
        
        if (nextWorkerToAdd < workersSize) {
            for (int j = 0; j < bikesSize; j++) {
                if (!usedBikes[j]) {
                    int newDist = abs(workers[nextWorkerToAdd][0] - bikes[j][0]) + abs(workers[nextWorkerToAdd][1] - bikes[j][1]);
                    push(heap, (Pair){newDist, nextWorkerToAdd, j});
                }
            }
            nextWorkerToAdd++;
        }
    }
    
    free(heap->data);
    free(heap);
    free(usedBikes);
    return result;
}

int main() {
    // Simplified parsing for demo
    int workersSize = 2, bikesSize = 3;
    int** workers = malloc(workersSize * sizeof(int*));
    int** bikes = malloc(bikesSize * sizeof(int*));
    
    for (int i = 0; i < workersSize; i++) {
        workers[i] = malloc(2 * sizeof(int));
    }
    for (int i = 0; i < bikesSize; i++) {
        bikes[i] = malloc(2 * sizeof(int));
    }
    
    workers[0][0] = 0; workers[0][1] = 0;
    workers[1][0] = 2; workers[1][1] = 1;
    bikes[0][0] = 1; bikes[0][1] = 2;
    bikes[1][0] = 3; bikes[1][1] = 3;
    bikes[2][0] = 2; bikes[2][1] = 1;
    
    int returnSize;
    int* result = solution(workers, workersSize, bikes, bikesSize, &returnSize);
    
    printf("[");
    for (int i = 0; i < returnSize; i++) {
        if (i > 0) printf(",");
        printf("%d", result[i]);
    }
    printf("]\n");
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(nm log(nm))

Still need to process up to nm pairs through heap operations

⚡ Linearithmic

Space Complexity

O(nm)

Heap can grow to store nm pairs in worst case

⚡ Linearithmic Space

78.5K Views

Medium Frequency

~25 min Avg. Time

1.5K 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

Priority Queue Optimization — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler