Decide whether every car can park given preferred spots and forward-only overflow

A one-way street has `n` parking spots in a row, numbered `0` to `n - 1` in the direction of travel. Cars arrive one at a time, in the order given by `preferences`, and car `i` prefers spot `preferences[i]`. Each car tries its preferred spot first and can only move forward from there. Decide whether every car manages to park. ### Function Signature ```python def can_all_park(n: int, preferences: list[int]) -> bool: ``` ### Rules - All spots start empty, and a parked car never moves. - An arriving car drives to its preferred spot. If that spot is empty, the car parks there. - Otherwise, the car continues forward and parks in the first empty spot with a larger index. - A car never moves backward. If there is no empty spot at or after its preferred spot, the car fails to park. - Return `True` if every car parks and `False` if at least one car fails. An empty `preferences` list returns `True`. ### Constraints - `1 <= n <= 10^5` - `0 <= len(preferences) <= 10^5` - `0 <= preferences[i] <= n - 1` - All values fit in a 32-bit signed integer. ### Examples **Example 1** ```text Input: n = 3, preferences = [0, 0, 1] Output: True ``` Car 0 parks in spot 0. Car 1 finds spot 0 taken and parks in spot 1. Car 2 finds spot 1 taken and parks in spot 2. **Example 2** ```text Input: n = 3, preferences = [1, 1, 2] Output: False ``` Car 0 parks in spot 1, and car 1 moves forward to spot 2. Car 2 finds spot 2 taken and has no spot after it, so it fails even though spot 0 is empty. **Example 3** ```text Input: n = 4, preferences = [2, 0] Output: True ``` Car 0 parks in spot 2 and car 1 parks in spot 0; spots 1 and 3 stay empty.