{x}
blog image

Design Parking System

Design a parking system for a parking lot. The parking lot has three kinds of parking spaces: big, medium, and small, with a fixed number of slots for each size.

Implement the ParkingSystem class:

  • ParkingSystem(int big, int medium, int small) Initializes object of the ParkingSystem class. The number of slots for each parking space are given as part of the constructor.
  • bool addCar(int carType) Checks whether there is a parking space of carType for the car that wants to get into the parking lot. carType can be of three kinds: big, medium, or small, which are represented by 1, 2, and 3 respectively. A car can only park in a parking space of its carType. If there is no space available, return false, else park the car in that size space and return true.

 

Example 1:

Input
["ParkingSystem", "addCar", "addCar", "addCar", "addCar"]
[[1, 1, 0], [1], [2], [3], [1]]
Output
[null, true, true, false, false]

Explanation
ParkingSystem parkingSystem = new ParkingSystem(1, 1, 0);
parkingSystem.addCar(1); // return true because there is 1 available slot for a big car
parkingSystem.addCar(2); // return true because there is 1 available slot for a medium car
parkingSystem.addCar(3); // return false because there is no available slot for a small car
parkingSystem.addCar(1); // return false because there is no available slot for a big car. It is already occupied.

 

Constraints:

  • 0 <= big, medium, small <= 1000
  • carType is 1, 2, or 3
  • At most 1000 calls will be made to addCar

Solution Explanation

This problem involves designing a parking system that tracks the availability of parking spaces of three different sizes: big, medium, and small. The solution uses an array to efficiently manage the counts of available spaces for each car type.

Approach:

The core idea is to store the number of available slots for each car type in an array. The ParkingSystem class uses a simple array cnt to maintain these counts. The index 0 is unused, while indices 1, 2, and 3 correspond to big, medium, and small cars, respectively. When a car wants to park (addCar method), the system checks if there's an available slot of the corresponding type. If yes, it decrements the count and returns true; otherwise, it returns false.

Code Explanation (Python as an Example):

class ParkingSystem:
    def __init__(self, big: int, medium: int, small: int):
        self.cnt = [0, big, medium, small] # Initialize the array with counts. Index 0 is unused.
 
    def addCar(self, carType: int) -> bool:
        if self.cnt[carType] == 0: # Check if there are available slots for this car type
            return False
        self.cnt[carType] -= 1 # Decrement the count if a slot is available.
        return True

The other languages follow a similar structure; they all use an integer array or equivalent data structure to track the available spaces for each car type.

Time and Space Complexity Analysis:

  • Time Complexity:

    • __init__ (constructor): O(1) - Constant time to initialize the array.
    • addCar: O(1) - Constant time to check and update the count in the array.

  • Space Complexity:

    • O(1) - Constant space is used to store the array cnt. The size of the array is fixed regardless of the input.

Advantages of this approach:

  • Efficiency: Using an array provides direct access to the counts for each car type, resulting in constant-time operations for both initialization and adding cars. This makes the solution very efficient, especially when handling a large number of addCar calls.
  • Simplicity: The code is concise and easy to understand.

Other possible approaches (less efficient):

While this array-based approach is the most efficient, other data structures could be used, but they would likely lead to higher time complexity. For example, using a dictionary (hash map) would introduce a small overhead for key lookups. More complex data structures would be unnecessarily complicated for this simple problem.