Design Parking System
Design Parking System is a easy design data structures problem solved with the hash map + array pattern.
The best approach, optimal (free-spot counters), runs in O(1) per addCar time and O(1) space.
Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (list of parked cars) up.
Problem
A parking lot has three kinds of spots: big, medium and small, with a fixed number of each. Design a ParkingSystem class:
ParkingSystem(int big, int medium, int small)sets the number of spots of each kind.boolean addCar(int carType)tries to park a car.carTypeis1for big,2for medium and3for small. A car may only use a spot of its own kind. If such a spot is free, the car takes it and the method returnstrue; otherwise it returnsfalse.
Cars never leave once they are parked.
Examples
Example 1
- Input
ParkingSystem(2, 0, 1), addCar(1), addCar(3), addCar(1), addCar(1), addCar(2), addCar(3)- Output
true, true, true, false, false, false- Why
- Two big spots fill up after two big cars; there are no medium spots; the single small spot is taken by the first small car.
Example 2
- Input
ParkingSystem(0, 1, 0), addCar(2), addCar(2), addCar(1)- Output
true, false, false- Why
- One medium spot, used by the first medium car. Cars only park in spots of their own size.
Constraints
0 <= big, medium, small <= 1000carTypeis1,2or3.- At most
1000calls toaddCar.
Solve it here
Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
Run checks the testcases above (2 examples, or your own). Submit also runs 9 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.
| Approach | Time | Space |
|---|---|---|
| Brute force (list of parked cars) | O(q) per addCar | O(q) |
| Optimal (free-spot counters) | O(1) per addCar | O(1) |
1Brute force (list of parked cars)
O(q) per addCarCounting scans every car parked so far (q calls in total).O(q)The list stores one entry per parked car.Remember every car that was parked. To decide whether a new car fits, count how many parked cars share its type and compare with that type's capacity.
- Store the three capacities and an empty list of parked car types.
- addCar: count list entries equal to carType.
- If the count is below the capacity, append carType and return true; otherwise return false.
class ParkingSystem {
private final int[] cap;
private final List<Integer> parked = new ArrayList<>();
public ParkingSystem(int big, int medium, int small) {
cap = new int[] { big, medium, small };
}
public boolean addCar(int carType) {
int used = 0;
for (int t : parked) if (t == carType) used++;
if (used >= cap[carType - 1]) return false;
parked.add(carType);
return true;
}
}class ParkingSystem:
def __init__(self, big: int, medium: int, small: int):
self.cap = [big, medium, small]
self.parked = []
def addCar(self, carType: int) -> bool:
used = sum(1 for t in self.parked if t == carType)
if used >= self.cap[carType - 1]:
return False
self.parked.append(carType)
return Trueclass ParkingSystem {
int cap[3];
vector<int> parked;
public:
ParkingSystem(int big, int medium, int small) {
cap[0] = big;
cap[1] = medium;
cap[2] = small;
}
bool addCar(int carType) {
int used = 0;
for (int t : parked) if (t == carType) used++;
if (used >= cap[carType - 1]) return false;
parked.push_back(carType);
return true;
}
};class ParkingSystem {
constructor(big, medium, small) {
this.cap = [big, medium, small];
this.parked = [];
}
addCar(carType) {
let used = 0;
for (const t of this.parked) if (t === carType) used++;
if (used >= this.cap[carType - 1]) return false;
this.parked.push(carType);
return true;
}
}2Optimal (free-spot counters)
O(1) per addCarOne array read and one write.O(1)Three counters.Keep the number of free spots for each size in an array. A car parks if its counter is positive, which decrements the counter.
- Constructor:
free = [big, medium, small]. - addCar: if
free[carType - 1] == 0return false. - Otherwise decrement it and return true.
class ParkingSystem {
private final int[] free;
public ParkingSystem(int big, int medium, int small) {
free = new int[] { big, medium, small };
}
public boolean addCar(int carType) {
if (free[carType - 1] == 0) return false;
free[carType - 1]--;
return true;
}
}class ParkingSystem:
def __init__(self, big: int, medium: int, small: int):
self.free = [big, medium, small]
def addCar(self, carType: int) -> bool:
if self.free[carType - 1] == 0:
return False
self.free[carType - 1] -= 1
return Trueclass ParkingSystem {
int freeSpots[3];
public:
ParkingSystem(int big, int medium, int small) {
freeSpots[0] = big;
freeSpots[1] = medium;
freeSpots[2] = small;
}
bool addCar(int carType) {
if (freeSpots[carType - 1] == 0) return false;
freeSpots[carType - 1]--;
return true;
}
};class ParkingSystem {
constructor(big, medium, small) {
this.free = [big, medium, small];
}
addCar(carType) {
if (this.free[carType - 1] === 0) return false;
this.free[carType - 1]--;
return true;
}
}Edge cases to test
- A size with zero spots from the start
- Filling a size exactly to capacity, then one more car
- Cars of one size never use spots of another size
Hints
Hint 1
You only need to know how many free spots of each size remain.
Hint 2
Store the three counters in an array indexed by carType - 1.
FAQ
What is the best time complexity for Design Parking System?
Optimal (free-spot counters) runs in O(1) per addCar time and O(1) extra space. One array read and one write.
Which pattern does Design Parking System use?
It is a design data structures problem that uses the hash map + array pattern. Other problems with the same pattern: Insert Delete GetRandom O(1), Logger Rate Limiter, Insert Delete GetRandom O(1) - Duplicates allowed.
Is there a brute force solution for Design Parking System?
Yes. Brute force (list of parked cars) takes O(q) per addCar time and O(q) space. Remember every car that was parked.
Which edge cases should I test for Design Parking System?
A size with zero spots from the start; Filling a size exactly to capacity, then one more car; Cars of one size never use spots of another size.