1603. Design Parking System - Explanation

Description

Implement ParkingSystem to track available parking spaces of three sizes.

ParkingSystem(big, medium, small) creates a lot with the given number of spaces for each size.
addCar(carType) parks one car and returns true if a matching space is available; otherwise it returns false and leaves availability unchanged.

Car types 1, 2, and 3 mean big, medium, and small. A car must use its own size of space, even if another size has free spaces. Cars do not leave. The operation list starts with the constructor; its output is null.

Example 1:

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

Output: [null,false,true,false,true]

Explanation: The big car cannot park. The first medium car uses the only medium space, so the next medium car fails. The small car uses the available small space.

Example 2:

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

Output: [null,false,true,true,false]

Explanation: A small car cannot use either big space and is rejected. The next two big cars park successfully; the third big car finds both spaces occupied.

Example 3:

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

Output: [null,false,false,false]

Explanation: The constructor creates no spaces. Every parking attempt returns false. The constructor itself contributes null to the output.

Constraints:

0 <= big, medium, small <= 1000
carType is 1, 2, or 3.
At most 1000 calls are made to addCar per object.

Topics

Company Tags

Please upgrade to NeetCode Pro to view company tags.

Prerequisites

Before attempting this problem, you should be comfortable with:

Arrays - Using arrays to store and access data by index
Index Mapping - Converting between 1-indexed input and 0-indexed arrays

1. Array - I

Intuition

A parking lot has a fixed number of spaces for each car size (big, medium, small). We can represent the available slots using an array of three integers. Since car types are numbered 1, 2, and 3, we map them to array indices 0, 1, and 2 by subtracting 1. When a car arrives, we check if there is room for its type. If so, we decrement the count and allow parking; otherwise, we reject it.

Algorithm

Initialization: Store the slot counts for big, medium, and small in an array spaces at indices 0, 1, and 2.
addCar(carType): Check if spaces[carType - 1] > 0. If yes, decrement that slot count and return true. Otherwise, return false.

class ParkingSystem:

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

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

public class ParkingSystem {
    private int[] spaces;

    public ParkingSystem(int big, int medium, int small) {
        spaces = new int[]{big, medium, small};
    }

    public boolean addCar(int carType) {
        if (spaces[carType - 1] > 0) {
            spaces[carType - 1]--;
            return true;
        }
        return false;
    }
}

class ParkingSystem {
    int spaces[3];

public:
    ParkingSystem(int big, int medium, int small) {
        spaces[0] = big;
        spaces[1] = medium;
        spaces[2] = small;
    }

    bool addCar(int carType) {
        if (spaces[carType - 1] > 0) {
            spaces[carType - 1]--;
            return true;
        }
        return false;
    }
};

class ParkingSystem {
    /**
     * @constructor
     * @param {number} big
     * @param {number} medium
     * @param {number} small
     */
    constructor(big, medium, small) {
        this.spaces = [big, medium, small];
    }

    /**
     * @param {number} carType
     * @return {boolean}
     */
    addCar(carType) {
        if (this.spaces[carType - 1] > 0) {
            this.spaces[carType - 1]--;
            return true;
        }
        return false;
    }
}

public class ParkingSystem {
    private int[] spaces;

    public ParkingSystem(int big, int medium, int small) {
        spaces = new int[] { big, medium, small };
    }

    public bool AddCar(int carType) {
        if (spaces[carType - 1] > 0) {
            spaces[carType - 1]--;
            return true;
        }
        return false;
    }
}

type ParkingSystem struct {
    spaces []int
}

func Constructor(big int, medium int, small int) ParkingSystem {
    return ParkingSystem{spaces: []int{big, medium, small}}
}

func (this *ParkingSystem) AddCar(carType int) bool {
    if this.spaces[carType-1] > 0 {
        this.spaces[carType-1]--
        return true
    }
    return false
}

class ParkingSystem(big: Int, medium: Int, small: Int) {
    private val spaces = intArrayOf(big, medium, small)

    fun addCar(carType: Int): Boolean {
        if (spaces[carType - 1] > 0) {
            spaces[carType - 1]--
            return true
        }
        return false
    }
}

class ParkingSystem {
    private var spaces: [Int]

    init(_ big: Int, _ medium: Int, _ small: Int) {
        spaces = [big, medium, small]
    }

    func addCar(_ carType: Int) -> Bool {
        if spaces[carType - 1] > 0 {
            spaces[carType - 1] -= 1
            return true
        }
        return false
    }
}

struct ParkingSystem {
    spaces: [i32; 3],
}

impl ParkingSystem {
    fn new(big: i32, medium: i32, small: i32) -> Self {
        ParkingSystem {
            spaces: [big, medium, small],
        }
    }

    fn add_car(&mut self, car_type: i32) -> bool {
        if self.spaces[(car_type - 1) as usize] > 0 {
            self.spaces[(car_type - 1) as usize] -= 1;
            return true;
        }
        false
    }
}

Time & Space Complexity

Time complexity:
- $O(1)$ time for initialization.
- $O(1)$ time for each $addCar()$ function call.
Space complexity: $O(1)$

2. Array - II

Intuition

This is a more concise version of the array approach. Instead of checking before decrementing, we decrement first and then check if the result is non-negative. The logic works because if there were no available slots, the count becomes negative, which we use to indicate failure. This allows the check and update to happen in a single expression.

Algorithm

Initialization: Store the slot counts for big, medium, and small in an array spaces.
addCar(carType): Decrement spaces[carType - 1] and return true if the new value is greater than or equal to 0, otherwise return false.

class ParkingSystem:

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

    def addCar(self, carType: int) -> bool:
        self.spaces[carType - 1] -= 1
        return self.spaces[carType - 1] >= 0

public class ParkingSystem {
    int[] spaces;

    public ParkingSystem(int big, int medium, int small) {
        spaces = new int[]{big, medium, small};
    }

    public boolean addCar(int carType) {
        return spaces[carType - 1]-- > 0;
    }
}

class ParkingSystem {
    int spaces[3];

public:
    ParkingSystem(int big, int medium, int small) {
        spaces[0] = big, spaces[1] = medium, spaces[2] = small;
    }

    bool addCar(int carType) {
        return spaces[carType - 1]-- > 0;
    }
};

class ParkingSystem {
    /**
     * @constructor
     * @param {number} big
     * @param {number} medium
     * @param {number} small
     */
    constructor(big, medium, small) {
        this.spaces = [big, medium, small];
    }

    /**
     * @param {number} carType
     * @return {boolean}
     */
    addCar(carType) {
        return this.spaces[carType - 1]-- > 0;
    }
}

public class ParkingSystem {
    private int[] spaces;

    public ParkingSystem(int big, int medium, int small) {
        spaces = new int[] { big, medium, small };
    }

    public bool AddCar(int carType) {
        return spaces[carType - 1]-- > 0;
    }
}

type ParkingSystem struct {
    spaces []int
}

func Constructor(big int, medium int, small int) ParkingSystem {
    return ParkingSystem{spaces: []int{big, medium, small}}
}

func (this *ParkingSystem) AddCar(carType int) bool {
    this.spaces[carType-1]--
    return this.spaces[carType-1] >= 0
}

class ParkingSystem(big: Int, medium: Int, small: Int) {
    private val spaces = intArrayOf(big, medium, small)

    fun addCar(carType: Int): Boolean {
        spaces[carType - 1]--
        return spaces[carType - 1] >= 0
    }
}

class ParkingSystem {
    private var spaces: [Int]

    init(_ big: Int, _ medium: Int, _ small: Int) {
        spaces = [big, medium, small]
    }

    func addCar(_ carType: Int) -> Bool {
        spaces[carType - 1] -= 1
        return spaces[carType - 1] >= 0
    }
}

struct ParkingSystem {
    spaces: [i32; 3],
}

impl ParkingSystem {
    fn new(big: i32, medium: i32, small: i32) -> Self {
        ParkingSystem {
            spaces: [big, medium, small],
        }
    }

    fn add_car(&mut self, car_type: i32) -> bool {
        self.spaces[(car_type - 1) as usize] -= 1;
        self.spaces[(car_type - 1) as usize] >= 0
    }
}

Time & Space Complexity

Time complexity:
- $O(1)$ time for initialization.
- $O(1)$ time for each $addCar()$ function call.
Space complexity: $O(1)$

Common Pitfalls

Off-by-One Index Error

Car types are 1-indexed (1 = big, 2 = medium, 3 = small), but arrays are 0-indexed. Forgetting to subtract 1 causes an index out of bounds error.

# Wrong: carType is 1-indexed, causes IndexError for carType=3
self.spaces[carType] -= 1

# Correct: convert to 0-indexed
self.spaces[carType - 1] -= 1

Decrementing Before Checking Availability

When using the concise approach that decrements first, you must check the value before decrementing (using post-decrement) or check if the result is non-negative. Checking for > 0 after decrementing gives wrong results.

# Wrong: always decrements, even when no space available
self.spaces[carType - 1] -= 1
return self.spaces[carType - 1] > 0  # Returns False when it was 1

# Correct option 1: check first, then decrement
if self.spaces[carType - 1] > 0:
    self.spaces[carType - 1] -= 1
    return True
return False

# Correct option 2: decrement and check >= 0
self.spaces[carType - 1] -= 1
return self.spaces[carType - 1] >= 0