Leetcode 1603: Design Parking System
You are tasked with designing a parking system for a parking lot that has three types of parking spaces: large, medium, and small. Each type of parking space has a fixed number of available slots. Your goal is to implement the
ParkingSystem class that supports the operations of initializing the parking system and parking a car based on its type.Problem
Approach
Steps
Complexity
Input: The input consists of an array of operations and their respective arguments. The first operation is the initialization of the ParkingSystem object, followed by multiple addCar operations to park the cars.
Example: ["ParkingSystem", "addCar", "addCar", "addCar", "addCar"]
[[2, 1, 3], [1], [2], [3], [1]]
Constraints:
• 0 <= big, medium, small <= 1000
• carType is 1, 2, or 3
• At most 1000 calls will be made to addCar
Output: The output is an array of results for each addCar operation. The result is `true` if the car is successfully parked, or `false` if no space is available for the car type.
Example: [null, true, true, false, false]
Constraints:
• Each call to addCar must return a boolean indicating whether the car was parked.
Goal: The goal is to manage the parking slots based on the car type and check if there is an available parking space before allowing a car to park.
Steps:
• 1. Initialize the ParkingSystem with the available slots for each type of parking space.
• 2. For each `addCar` operation, check if the corresponding parking space is available.
• 3. If available, park the car and update the respective slot count.
• 4. If not available, return `false`.
Goal: The solution must efficiently handle parking operations and ensure that car parking is managed based on the available slots.
Steps:
• The number of slots for each type of parking space can range from 0 to 1000.
• The `addCar` function is called at most 1000 times.
Assumptions:
• The system is initialized correctly with the provided number of slots for each type.
• All `addCar` operations will be valid (i.e., they will only try to park a car type that is supported).
• Input: ["ParkingSystem", "addCar", "addCar", "addCar", "addCar"]
[[2, 1, 3], [1], [2], [3], [1]]
• Explanation: In this example, we start with 2 large slots, 1 medium slot, and 3 small slots. The first car parks successfully, followed by the second car. The third car cannot park because there are no small slots, and the fourth car cannot park because there are no large slots available.
Approach: The approach involves managing available parking spaces and handling `addCar` operations efficiently based on the number of available slots for each car type.
Observations:
• We need to track the number of available parking spaces for each type of car.
• Each `addCar` operation should check if the corresponding space is available.
• The parking system should handle car parking requests sequentially, and update the parking slots count after each successful operation.
Steps:
• 1. Store the number of available slots for each parking type.
• 2. For each car parking request, check if the corresponding parking type has available slots.
• 3. Decrease the count of available slots for the corresponding type if the car is successfully parked.
Empty Inputs:
• The input may have no `addCar` operations after initialization.
Large Inputs:
• The system should handle up to 1000 `addCar` operations efficiently.
Special Values:
• All slots could be empty at the start.
Constraints:
• Ensure that the number of available slots is properly updated after each operation.
int bm, mm, sm;
int bc, mc, sc;
ParkingSystem(int big, int medium, int small) {
bm = big;
mm = medium;
sm = small;
bc = 0;
mc = 0;
sc = 0;
}
bool addCar(int ct) {
switch(ct) {
case 1:
if(bc < bm) {
bc++;
return true;
}
break;
case 2:
if(mc < mm) {
mc++;
return true;
}
break;
case 3:
if(sc < sm) {
sc++;
return true;
}
break;
}
return false;
}
};
/**
* Your ParkingSystem object will be instantiated and called as such:
* ParkingSystem* obj = new ParkingSystem(big, medium, small);
* bool param_1 = obj->addCar(carType);
1 : Variable Declaration
int bm, mm, sm;
These variables represent the capacity for big, medium, and small parking spots, respectively.
2 : Variable Declaration
int bc, mc, sc;
These variables track the current number of parked cars for big, medium, and small spots, respectively.
3 : Constructor
ParkingSystem(int big, int medium, int small) {
Constructor to initialize the ParkingSystem with the given capacities for big, medium, and small parking spots.
4 : Assignment
bm = big;
Assign the provided 'big' parking capacity to the 'bm' variable.
5 : Assignment
mm = medium;
Assign the provided 'medium' parking capacity to the 'mm' variable.
6 : Assignment
sm = small;
Assign the provided 'small' parking capacity to the 'sm' variable.
7 : Initialization
bc = 0;
Initialize the 'bc' variable, which tracks the number of big cars, to 0.
8 : Initialization
mc = 0;
Initialize the 'mc' variable, which tracks the number of medium cars, to 0.
9 : Initialization
sc = 0;
Initialize the 'sc' variable, which tracks the number of small cars, to 0.
10 : Method Definition
bool addCar(int ct) {
Method to add a car to the parking system. The car type (ct) determines the parking category.
11 : Switch Statement
switch(ct) {
The switch statement is used to handle the car type and decide which parking lot to check and update.
12 : Case 1 - Big Car
case 1:
Handle the case where the car type is 1, representing a big car.
13 : Condition Check
if(bc < bm) {
Check if the number of big cars is less than the big parking capacity.
14 : Increment
bc++;
If there is space available, increment the count of big cars.
15 : Return
return true;
Return 'true' indicating that the car has been successfully parked.
16 : End Switch
break;
Break out of the switch statement.
17 : Case 2 - Medium Car
case 2:
Handle the case where the car type is 2, representing a medium car.
18 : Condition Check
if(mc < mm) {
Check if the number of medium cars is less than the medium parking capacity.
19 : Increment
mc++;
If there is space available, increment the count of medium cars.
20 : Return
return true;
Return 'true' indicating that the car has been successfully parked.
21 : End Switch
break;
Break out of the switch statement.
22 : Case 3 - Small Car
case 3:
Handle the case where the car type is 3, representing a small car.
23 : Condition Check
if(sc < sm) {
Check if the number of small cars is less than the small parking capacity.
24 : Increment
sc++;
If there is space available, increment the count of small cars.
25 : Return
return true;
Return 'true' indicating that the car has been successfully parked.
26 : End Switch
break;
Break out of the switch statement.
27 : Return False
return false;
Return 'false' if no parking space is available for the requested car type.
Best Case: O(1)
Average Case: O(1)
Worst Case: O(1)
Description: The time complexity is constant for each operation, as it only involves checking the number of available parking spaces for a specific car type.
Best Case: O(1)
Worst Case: O(1)
Description: The space complexity is constant, as we only store a fixed number of parking slot counts.
| LeetCode Solutions Library / DSA Sheets / Course Catalog |
|---|
comments powered by Disqus