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

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

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

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

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.

Forward-Only Parking on a One-Way Street

Hints

1. A car never moves backward, so a car that prefers spot p can only ever end up in one of the spots p through n - 1.
2. Example 2 shows a car can fail even though a lower-numbered spot is still empty, so having no more cars than spots is not enough on its own.
3. With up to 10^5 cars, walking forward one spot at a time for every car can get slow when many cars prefer nearby spots.

Approach

Let m = len(preferences). Count how many cars prefer each spot, then scan the spots from n - 1 down to 0 while keeping a running total s(j) = number of cars whose preferred spot is at least j. Return False as soon as s(j) > n - j for some j; if the scan finishes, return True.

Necessity: a car never moves backward, so a car preferring spot p can only park in spots p..n-1. All s(j) cars preferring a spot >= j must therefore fit into the n - j spots j..n-1; if s(j) > n - j, at least one of them fails.

Edge cases: an empty preferences list gives s(j) = 0 everywhere and returns True; more cars than spots gives s(0) = m > n and returns False; two cars preferring n - 1 give s(n - 1) = 2 > 1 and return False; a car can fail while lower spots are empty (Example 2), which the check captures because s(j) never counts cars preferring spots below j. Every running total is at most 10^5, so 32-bit integers suffice in every language.

• Time complexity: O(n + m)
• Space complexity: O(n)