Problem Description

You need to design a parking system for a parking lot that has three different sizes of parking spaces: big, medium, and small. Each size has a fixed number of available slots.

The system should support two operations:

1. Initialize the parking system with the number of slots for each size:

   • ParkingSystem(int big, int medium, int small): Creates a parking system with the specified number of big, medium, and small parking spaces.

2. Add a car to the parking lot:

   • addCar(int carType): Attempts to park a car of a given type.
   • Car types are represented by integers: 1 for big, 2 for medium, and 3 for small.
   • A car can only park in a space that matches its size exactly (a big car needs a big space, etc.).
   • Returns true if there's an available space for the car type and the car is successfully parked (reducing the available count by 1).
   • Returns false if no space is available for that car type.

The solution uses an array cnt where index 1, 2, and 3 store the available counts for big, medium, and small spaces respectively. When a car arrives, the system checks if there's space available for that car type. If yes, it decrements the count and returns true; otherwise, it returns false.

Intuition

The key insight is that this is a simple resource management problem. We need to track how many parking spaces of each type are available and update these counts as cars arrive.

Since we have exactly three types of parking spaces and cars can only park in their matching space type, we can think of this as having three independent counters. Each car type maps directly to its corresponding parking space type (1→big, 2→medium, 3→small).

The natural approach is to use an array to store these counts. We can leverage the fact that car types are already represented as integers (1, 2, 3), so we can use them directly as array indices. This eliminates the need for any conditional logic or mapping between car types and space types.

When a car arrives, we simply need to:

1. Check if the counter for that car type is greater than 0 (space available)
2. If yes, decrement the counter and return true
3. If no, return false

Using an array with index 0 unused and indices 1, 2, 3 corresponding to big, medium, and small makes the code extremely clean - we can directly use carType as the index without any transformation. This gives us O(1) time complexity for parking operations and O(1) space complexity (since we only need to store 3 counts).

Solution Approach

The implementation uses a simulation approach with an array-based data structure to track parking space availability.

Data Structure:

• We use an array cnt of length 4 to store the number of available parking spaces
• cnt[0] is unused (set to 0)
• cnt[1] stores the number of available big parking spaces
• cnt[2] stores the number of available medium parking spaces
• cnt[3] stores the number of available small parking spaces

Initialization (__init__ method):

def __init__(self, big: int, medium: int, small: int):
    self.cnt = [0, big, medium, small]

We create the array with index 0 set to 0 (unused), and indices 1, 2, 3 initialized with the given counts for big, medium, and small spaces respectively. This clever indexing allows us to use the carType value directly as an array index.

Adding a Car (addCar method):

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

The algorithm follows these steps:

1. Check if there's an available space by accessing self.cnt[carType]
2. If self.cnt[carType] == 0, no space is available, so return False
3. Otherwise, decrement the count by 1 to mark one space as occupied
4. Return True to indicate successful parking

Time and Space Complexity:

• Time Complexity: O(1) for both initialization and addCar operations, as we're only accessing and updating array elements
• Space Complexity: O(1) as we only store a fixed-size array of 4 elements regardless of input size

This simulation approach is optimal because it directly models the real-world scenario with minimal overhead and provides constant-time operations for all parking system functions.

Example Walkthrough

Let's walk through a concrete example to illustrate how the parking system works:

Initial Setup:

parkingSystem = ParkingSystem(1, 2, 1)

This creates a parking lot with:

• 1 big parking space
• 2 medium parking spaces
• 1 small parking space

Internally, our array cnt is initialized as: [0, 1, 2, 1]

• cnt[0] = 0 (unused)
• cnt[1] = 1 (big spaces)
• cnt[2] = 2 (medium spaces)
• cnt[3] = 1 (small spaces)

Operation 1: Park a big car

parkingSystem.addCar(1)  # Returns True

• We check cnt[1] which equals 1 (space available)
• Decrement cnt[1] by 1: cnt[1] = 0
• Array becomes: [0, 0, 2, 1]
• Return True (successfully parked)

Operation 2: Park a medium car

parkingSystem.addCar(2)  # Returns True

• We check cnt[2] which equals 2 (space available)
• Decrement cnt[2] by 1: cnt[2] = 1
• Array becomes: [0, 0, 1, 1]
• Return True (successfully parked)

Operation 3: Park another big car

parkingSystem.addCar(1)  # Returns False

• We check cnt[1] which equals 0 (no space available)
• No changes to the array: [0, 0, 1, 1]
• Return False (parking failed - no big spaces left)

Operation 4: Park a small car

parkingSystem.addCar(3)  # Returns True

• We check cnt[3] which equals 1 (space available)
• Decrement cnt[3] by 1: cnt[3] = 0
• Array becomes: [0, 0, 1, 0]
• Return True (successfully parked)

Final State: After these operations, the parking lot has:

• 0 big spaces available (all occupied)
• 1 medium space available
• 0 small spaces available (all occupied)

The beauty of this approach is that the carType parameter (1, 2, or 3) directly corresponds to the array index, making the code elegant and efficient with no need for conditional statements or mappings.

Solution Implementation

Time and Space Complexity

Time Complexity: O(1)

The __init__ method performs a simple list initialization with 4 elements, which takes constant time O(1).

The addCar method performs:

• One array access to check if self.cnt[carType] == 0 - O(1)
• One array access and decrement operation self.cnt[carType] -= 1 - O(1)
• Return statement - O(1)

Since all operations in both methods are constant time operations, the overall time complexity is O(1).

Space Complexity: O(1)

The class uses a fixed-size list self.cnt with exactly 4 elements (index 0 plus the three parking spot types). Regardless of the input values for big, medium, and small, the space used remains constant at 4 integer values. The space does not grow with the input size, making the space complexity O(1).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Array Index Out of Bounds

One of the most common mistakes is not validating the carType parameter in the addCar method. If someone passes an invalid car type (like 0, 4, or negative numbers), the code will either crash with an IndexError or access incorrect array positions.

Problematic Code:

def addCar(self, carType: int) -> bool:
    # No validation - will crash if carType is not 1, 2, or 3
    if self.available_slots[carType] == 0:
        return False
    self.available_slots[carType] -= 1
    return True

Solution:

def addCar(self, carType: int) -> bool:
    # Validate car type first
    if carType < 1 or carType > 3:
        return False  # Invalid car type
  
    if self.available_slots[carType] == 0:
        return False
    self.available_slots[carType] -= 1
    return True

2. Using Dictionary Instead of Array (Over-engineering)

Some developers might use a dictionary thinking it's more readable, but this adds unnecessary overhead for such a simple problem with fixed car types.

Over-engineered Code:

def __init__(self, big: int, medium: int, small: int):
    # Using dictionary adds unnecessary complexity
    self.available_slots = {
        'big': big,
        'medium': medium,
        'small': small
    }
    self.type_map = {1: 'big', 2: 'medium', 3: 'small'}

def addCar(self, carType: int) -> bool:
    car_size = self.type_map.get(carType)
    if not car_size or self.available_slots[car_size] == 0:
        return False
    self.available_slots[car_size] -= 1
    return True

Better Approach: Stick with the simple array solution as shown in the original code.

3. Forgetting to Handle Thread Safety

In a real-world scenario with concurrent access, multiple threads might try to park cars simultaneously, leading to race conditions.

Problem Scenario: Two threads check available_slots[1] > 0 at the same time, both see it's 1, and both try to decrement, potentially resulting in negative values.

Solution for Thread Safety:

import threading

class ParkingSystem:
    def __init__(self, big: int, medium: int, small: int):
        self.available_slots = [0, big, medium, small]
        self.lock = threading.Lock()
  
    def addCar(self, carType: int) -> bool:
        with self.lock:
            if self.available_slots[carType] == 0:
                return False
            self.available_slots[carType] -= 1
            return True

4. Not Considering Negative Initial Values

The constructor doesn't validate if the initial parking space counts are non-negative.

Solution:

def __init__(self, big: int, medium: int, small: int):
    # Ensure non-negative values
    self.available_slots = [0, max(0, big), max(0, medium), max(0, small)]