Campus Bikes II - Practice Coding Problems

Campus Bikes II - Problem

On a campus represented as a 2D grid, there are n workers and m bikes, with n ≤ m. Each worker and bike is a 2D coordinate on this grid.

We need to assign one unique bike to each worker such that the sum of the Manhattan distances between each worker and their assigned bike is minimized.

Return the minimum possible sum of Manhattan distances between each worker and their assigned bike.

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

Input & Output

Example 1 — Basic Case

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

› Output: 6

💡 Note: Assign worker at (0,0) to bike at (1,2) with distance 3, and worker at (2,1) to bike at (3,3) with distance 3. Total distance = 3 + 3 = 6.

Example 2 — Multiple Options

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

› Output: 4

💡 Note: Optimal assignment: worker (0,0)→bike (1,0) distance 1, worker (1,1)→bike (2,2) distance 2, worker (2,0)→bike (2,1) distance 1. Total = 1+2+1 = 4.

Example 3 — Same Position

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

› Output: 0

💡 Note: Worker at (0,0) gets assigned to bike at (0,0) with Manhattan distance 0.

Constraints

1 ≤ workers.length ≤ bikes.length ≤ 12
workers[i].length == bikes[j].length == 2
0 ≤ workers[i][0], workers[i][1], bikes[j][0], bikes[j][1] < 1000

Visualization

Tap to expand

Understanding the Visualization

Input

Workers at positions [[0,0],[2,1]] and bikes at [[1,2],[3,3]]

Process

Find optimal assignment minimizing total Manhattan distance

Output

Minimum possible sum of distances = 6

Key Takeaway

🎯 Key Insight: Use bitmasks to efficiently track bike assignments and memoization to avoid redundant computation

Asked in

G Google 15 f Facebook 12 U Uber 8

The key insight is to use bitmasks to represent which bikes are already assigned and apply dynamic programming with memoization to avoid recomputing subproblems. The optimal approach uses DP with bitmask: Time: O(n × 2^m × m), Space: O(n × 2^m).

Common Approaches

Approach	Time	Space	Notes
✓ Dynamic Programming with Bitmask	O(n × 2^m × m)	O(n × 2^m)	Use bitmask to represent used bikes and memoize subproblems to avoid recomputation
Backtracking with Pruning	O(m!/(m-n)!)	O(n)	Build assignments recursively with early termination when current path exceeds best solution
Brute Force - Try All Permutations	O(m!/(m-n)!)	O(n)	Generate all possible ways to assign bikes to workers and find minimum sum

Dynamic Programming with Bitmask — Algorithm Steps

Use bitmask to represent which bikes are used
For each worker-mask state, try all available bikes
Memoize results to avoid recomputing same states
Return minimum cost for all workers assigned

Visualization

Tap to expand

Step-by-Step Walkthrough

States

Each state is (worker_index, bike_bitmask)

Transitions

Try assigning each available bike

Memoize

Store results to avoid recomputing states

Code -

solution.c — C

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

#define MAX_STATES 100000

typedef struct {
    int workerIdx;
    int bikeMask;
    int result;
} MemoEntry;

MemoEntry memo[MAX_STATES];
int memoSize = 0;
int workers[10][2], bikes[10][2];
int numWorkers, numBikes;

int manhattanDistance(int workerIdx, int bikeIdx) {
    return abs(workers[workerIdx][0] - bikes[bikeIdx][0]) + 
           abs(workers[workerIdx][1] - bikes[bikeIdx][1]);
}

int findMemo(int workerIdx, int bikeMask) {
    for (int i = 0; i < memoSize; i++) {
        if (memo[i].workerIdx == workerIdx && memo[i].bikeMask == bikeMask) {
            return memo[i].result;
        }
    }
    return -1;
}

void addMemo(int workerIdx, int bikeMask, int result) {
    memo[memoSize].workerIdx = workerIdx;
    memo[memoSize].bikeMask = bikeMask;
    memo[memoSize].result = result;
    memoSize++;
}

int dp(int workerIdx, int bikeMask) {
    if (workerIdx == numWorkers) {
        return 0;
    }
    
    int cached = findMemo(workerIdx, bikeMask);
    if (cached != -1) {
        return cached;
    }
    
    int minCost = INT_MAX;
    for (int bikeIdx = 0; bikeIdx < numBikes; bikeIdx++) {
        if (!(bikeMask & (1 << bikeIdx))) {
            int cost = manhattanDistance(workerIdx, bikeIdx);
            int newMask = bikeMask | (1 << bikeIdx);
            int totalCost = cost + dp(workerIdx + 1, newMask);
            if (totalCost < minCost) {
                minCost = totalCost;
            }
        }
    }
    
    addMemo(workerIdx, bikeMask, minCost);
    return minCost;
}

int solution() {
    memoSize = 0;
    return dp(0, 0);
}

int main() {
    // Simplified for demonstration
    numWorkers = 2;
    numBikes = 2;
    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;
    
    int result = solution();
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n × 2^m × m)

n workers × 2^m possible bike masks × m bikes to try per state

✓ Linear Growth

Space Complexity

O(n × 2^m)

Memoization table stores result for each (worker, bike_mask) combination

⚡ Linearithmic Space

23.5K Views

Medium Frequency

~25 min Avg. Time

890 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

Dynamic Programming with Bitmask — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler