Design Parking System

Easy Design Data Structures Hash Map + Array Original on LeetCode

Reported atSpotifyTesla

Design Parking System is a easy design data structures problem solved with the hash map + array pattern. The best approach, optimal (free-spot counters), runs in O(1) per addCar time and O(1) space. Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (list of parked cars) up.

Problem

A parking lot has three kinds of spots: big, medium and small, with a fixed number of each. Design a ParkingSystem class:

  • ParkingSystem(int big, int medium, int small) sets the number of spots of each kind.
  • boolean addCar(int carType) tries to park a car. carType is 1 for big, 2 for medium and 3 for small. A car may only use a spot of its own kind. If such a spot is free, the car takes it and the method returns true; otherwise it returns false.

Cars never leave once they are parked.

Examples

Example 1

Input
ParkingSystem(2, 0, 1), addCar(1), addCar(3), addCar(1), addCar(1), addCar(2), addCar(3)
Output
true, true, true, false, false, false
Why
Two big spots fill up after two big cars; there are no medium spots; the single small spot is taken by the first small car.

Example 2

Input
ParkingSystem(0, 1, 0), addCar(2), addCar(2), addCar(1)
Output
true, false, false
Why
One medium spot, used by the first medium car. Cars only park in spots of their own size.

Constraints

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

Solve it here

Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.

00:00
Testcase

Run checks the testcases above (2 examples, or your own). Submit also runs 9 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.

ApproachTimeSpace
Brute force (list of parked cars)O(q) per addCarO(q)
Optimal (free-spot counters)O(1) per addCarO(1)

1Brute force (list of parked cars)

TimeO(q) per addCarCounting scans every car parked so far (q calls in total).
SpaceO(q)The list stores one entry per parked car.

Remember every car that was parked. To decide whether a new car fits, count how many parked cars share its type and compare with that type's capacity.

  1. Store the three capacities and an empty list of parked car types.
  2. addCar: count list entries equal to carType.
  3. If the count is below the capacity, append carType and return true; otherwise return false.
class ParkingSystem {
    private final int[] cap;
    private final List<Integer> parked = new ArrayList<>();

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

    public boolean addCar(int carType) {
        int used = 0;
        for (int t : parked) if (t == carType) used++;
        if (used >= cap[carType - 1]) return false;
        parked.add(carType);
        return true;
    }
}

2Optimal (free-spot counters)

TimeO(1) per addCarOne array read and one write.
SpaceO(1)Three counters.

Keep the number of free spots for each size in an array. A car parks if its counter is positive, which decrements the counter.

  1. Constructor: free = [big, medium, small].
  2. addCar: if free[carType - 1] == 0 return false.
  3. Otherwise decrement it and return true.
class ParkingSystem {
    private final int[] free;

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

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

Edge cases to test

  • A size with zero spots from the start
  • Filling a size exactly to capacity, then one more car
  • Cars of one size never use spots of another size

Hints

Hint 1

You only need to know how many free spots of each size remain.

Hint 2

Store the three counters in an array indexed by carType - 1.

FAQ

What is the best time complexity for Design Parking System?

Optimal (free-spot counters) runs in O(1) per addCar time and O(1) extra space. One array read and one write.

Which pattern does Design Parking System use?

It is a design data structures problem that uses the hash map + array pattern. Other problems with the same pattern: Insert Delete GetRandom O(1), Logger Rate Limiter, Insert Delete GetRandom O(1) - Duplicates allowed.

Is there a brute force solution for Design Parking System?

Yes. Brute force (list of parked cars) takes O(q) per addCar time and O(q) space. Remember every car that was parked.

Which edge cases should I test for Design Parking System?

A size with zero spots from the start; Filling a size exactly to capacity, then one more car; Cars of one size never use spots of another size.