LeetCode 1603 - Design Parking System

Difficulty: 🟢 Easy
Topics: Design, Simulation, Counting

Solution

Problem Understanding

This problem asks us to design a very small parking lot management system. The parking lot contains exactly three types of parking spaces:

Big parking spaces
Medium parking spaces
Small parking spaces

The constructor receives the number of available spaces for each type. After initialization, cars arrive one at a time, and for every arriving car we must determine whether there is still an available parking slot of the required size.

The important restriction is that a car can only park in a slot of the exact same type. A big car cannot use a medium or small slot, and similarly for the other types.

The addCar(carType) function represents a new car entering the parking lot:

carType = 1 means a big car
carType = 2 means a medium car
carType = 3 means a small car

The function should:

Return true if a slot of that type is available, and reserve one slot
Return false if no slot of that type remains

The constraints are very small:

Each parking count is at most 1000
At most 1000 calls to addCar will occur

These limits tell us that performance is not a major concern. Even a simple implementation will easily fit within time limits. However, the problem is fundamentally a design and state management problem, so the cleanest solution is preferred.

Several edge cases are important:

A parking type may start with 0 spaces
Multiple cars of the same type may arrive consecutively
Once a parking type becomes full, every future request of that type must return false
The problem guarantees that carType is always valid, meaning it will only be 1, 2, or 3

Because the input is guaranteed to be valid, we do not need additional error handling for invalid car types.

Approaches

Brute Force Approach

A brute force approach would explicitly represent every parking slot individually.

For example, we could maintain three arrays:

One array for big slots
One array for medium slots
One array for small slots

Each slot could store whether it is occupied. Whenever a new car arrives, we would scan through the corresponding array searching for the first unused slot.

If we find an empty slot:

Mark it as occupied
Return true

Otherwise:

Return false

This approach is correct because it directly simulates the parking lot at the slot level. Every parked car consumes exactly one slot.

However, this solution is unnecessarily expensive. Each addCar call may need to scan through up to 1000 slots. The problem does not require tracking individual parking positions, only whether capacity remains.

Optimal Approach

The key observation is that we do not care which exact parking slot is used. We only care how many remaining slots exist for each parking type.

Instead of storing every slot individually, we can simply maintain three counters:

Remaining big spaces
Remaining medium spaces
Remaining small spaces

When a car arrives:

Check whether the corresponding counter is greater than zero
If yes, decrement the counter and return true
Otherwise return false

This works because parking a car only changes the number of remaining spaces. The exact slot identity is irrelevant.

This reduces the operation to constant time.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n) per operation	O(n)	Explicitly stores and scans parking slots
Optimal	O(1) per operation	O(1)	Stores only remaining counts

Algorithm Walkthrough

Optimal Algorithm

Initialize the parking system with the number of available spaces for each type.

We store the counts in a data structure indexed by car type. Since car types are 1, 2, and 3, we can map them directly to counts. 2. When addCar(carType) is called, check the remaining count for that type.

If the count is zero, there is no available space, so we return False. 3. If the count is greater than zero, decrement it by one.

This simulates reserving a parking space for the arriving car. 4. Return True after successfully parking the car.

The reason this works efficiently is that the state of the system is completely determined by the remaining counts. No additional tracking is necessary.

Why it works

The algorithm maintains the invariant that each counter always equals the number of remaining available spaces for that car type.

Initially, the counters are set correctly by the constructor. Every successful parking operation decreases the corresponding count by exactly one, matching the consumption of a parking slot. Failed operations do not modify the counters.

Because the counters always reflect the exact number of remaining spaces, checking whether a car can park is always correct.

Python Solution

class ParkingSystem:

    def __init__(self, big: int, medium: int, small: int):
        self.slots = {
            1: big,
            2: medium,
            3: small
        }

    def addCar(self, carType: int) -> bool:
        if self.slots[carType] == 0:
            return False

        self.slots[carType] -= 1
        return True

# Your ParkingSystem object will be instantiated and called as such:
# obj = ParkingSystem(big, medium, small)
# param_1 = obj.addCar(carType)

The constructor initializes a dictionary called slots. The keys correspond directly to the car types defined in the problem:

1 for big
2 for medium
3 for small

The values store the number of remaining spaces.

Inside addCar, the implementation first checks whether the requested parking type has any remaining capacity. If the value is zero, the parking lot is full for that type, so the function immediately returns False.

Otherwise, the method decrements the remaining count and returns True.

The implementation is compact because the problem only requires counting remaining spaces rather than tracking individual parking positions.

Go Solution

type ParkingSystem struct {
    slots [4]int
}

func Constructor(big int, medium int, small int) ParkingSystem {
    ps := ParkingSystem{}

    ps.slots[1] = big
    ps.slots[2] = medium
    ps.slots[3] = small

    return ps
}

func (this *ParkingSystem) AddCar(carType int) bool {
    if this.slots[carType] == 0 {
        return false
    }

    this.slots[carType]--
    return true
}

/**
 * Your ParkingSystem object will be instantiated and called as such:
 * obj := Constructor(big, medium, small);
 * param_1 := obj.AddCar(carType);
 */

The Go solution uses a fixed-size array instead of a map. Since the valid car types are only 1, 2, and 3, an array is simple and efficient.

The array has size 4 so that indices 1, 2, and 3 can be used directly without offset calculations.

Unlike Python dictionaries, Go arrays require fixed sizes and explicit indexing, but otherwise the logic is identical.

There are no overflow concerns because the counts are very small and only decrease from their initial values.

Worked Examples

Example 1

Input:

["ParkingSystem", "addCar", "addCar", "addCar", "addCar"]
[[1, 1, 0], [1], [2], [3], [1]]

Initialization

big = 1
medium = 1
small = 0

Internal state:

Car Type	Remaining Spaces
1 (big)	1
2 (medium)	1
3 (small)	0

Operation 1

addCar(1)

Before operation:

Type	Remaining
1	1
2	1
3	0

Since one big slot is available:

Decrement big count from 1 to 0
Return true

After operation:

Type	Remaining
1	0
2	1
3	0

Operation 2

addCar(2)

Before operation:

Type	Remaining
1	0
2	1
3	0

A medium slot is available:

Decrement medium count from 1 to 0
Return true

After operation:

Type	Remaining
1	0
2	0
3	0

Operation 3

addCar(3)

Before operation:

Type	Remaining
1	0
2	0
3	0

No small slots remain:

Return false

State does not change.

Operation 4

addCar(1)

Before operation:

Type	Remaining
1	0
2	0
3	0

No big slots remain:

Return false

Final output:

[null, true, true, false, false]

Complexity Analysis

Measure	Complexity	Explanation
Time	O(1)	Each operation performs only a few constant-time checks and updates
Space	O(1)	Only three counters are stored regardless of input size

The complexity is constant because the number of parking types is fixed at three. No loops or dynamically growing data structures are used.

Test Cases

# Provided example
ps = ParkingSystem(1, 1, 0)
assert ps.addCar(1) is True   # Big slot available
assert ps.addCar(2) is True   # Medium slot available
assert ps.addCar(3) is False  # No small slots
assert ps.addCar(1) is False  # Big slot already occupied

# All zero capacity
ps = ParkingSystem(0, 0, 0)
assert ps.addCar(1) is False  # No big slots
assert ps.addCar(2) is False  # No medium slots
assert ps.addCar(3) is False  # No small slots

# Single slot for each type
ps = ParkingSystem(1, 1, 1)
assert ps.addCar(1) is True   # First big car parks
assert ps.addCar(2) is True   # First medium car parks
assert ps.addCar(3) is True   # First small car parks
assert ps.addCar(1) is False  # Big full
assert ps.addCar(2) is False  # Medium full
assert ps.addCar(3) is False  # Small full

# Large capacities
ps = ParkingSystem(1000, 1000, 1000)

for _ in range(1000):
    assert ps.addCar(1) is True  # Fill all big slots

assert ps.addCar(1) is False     # Big parking full

# Uneven capacities
ps = ParkingSystem(2, 0, 1)

assert ps.addCar(1) is True   # First big car
assert ps.addCar(1) is True   # Second big car
assert ps.addCar(1) is False  # No more big slots

assert ps.addCar(2) is False  # Medium capacity is zero

assert ps.addCar(3) is True   # One small slot available
assert ps.addCar(3) is False  # Small parking full

Test	Why
Example case	Verifies correctness against the official example
All zero capacity	Ensures parking fails immediately when no slots exist
Single slot for each type	Verifies transition from available to full
Large capacities	Confirms repeated operations work correctly
Uneven capacities	Tests independent tracking of each parking type

Edge Cases

Zero Initial Capacity

A parking type may start with zero available spaces. This is a common source of bugs if the implementation assumes every type has at least one slot.

For example:

ParkingSystem(0, 1, 2)

In this situation, every addCar(1) call must immediately return false.

The implementation handles this naturally because it checks whether the remaining count is zero before decrementing.

Repeated Requests After Full Capacity

Another important edge case occurs when a parking type becomes full and additional requests continue arriving.

For example:

ParkingSystem(1, 0, 0)

The first addCar(1) succeeds, but every later addCar(1) must fail.

A buggy implementation might accidentally allow negative counts or continue decrementing below zero. Our solution prevents this by returning early whenever the count reaches zero.

Independent Parking Categories

Each parking type must be tracked independently.

For example:

ParkingSystem(1, 1, 1)

Parking a big car must not affect medium or small availability.

The implementation handles this correctly because each car type has its own dedicated counter. Updating one counter does not modify the others.