NeetCode #174LC-2534HardArrays & Hashing
← Back to All Problems#174 · #2534 · Time Taken to Cross the Door(通过门的时间)
📌 Problem Statement & Constraints
There are
n people who want to cross a door. arrival[i] is the arrival time and state[i] is 0 for entering, 1 for exiting. Each person takes 1 second to cross, one at a time. Priority rule: if people are waiting on both sides, the side that used the door most recently goes next (exiting has priority if nobody has used the door yet). Return the time each person crosses. Constraints: 1 <= n <= 10^5; arrival is non-decreasing.💡 Core Algorithmic Approaches
- Simulate second by second with two queues, one per direction.
- At each second, admit everyone whose arrival time is at most the current second into their respective queue.
- If both queues are non-empty, the
lastflag (1 for exit, 0 for enter, initialised to 1) decides who goes. - If only one queue is non-empty, that side goes and the
lastflag is updated. If nobody is waiting, jump the clock to the next arrival -- this jump is essential for performance.
💻 Benchmark Python3 Implementation
class Solution:
def timeTaken(self, arrival: List[int], state: List[int]) -> List[int]:
from collections import deque
n = len(arrival)
enter, exit_ = deque(), deque()
res = [0] * n
i = 0
t = 0
last = 1 # nobody used the door -> exit priority
while i < n or enter or exit_:
while i < n and arrival[i] <= t:
(exit_ if state[i] == 1 else enter).append(i)
i += 1
if not enter and not exit_:
t = arrival[i] # jump to the next arrival
continue
if enter and exit_:
if last == 1:
res[exit_.popleft()] = t
else:
res[enter.popleft()] = t
last = 0
elif exit_:
res[exit_.popleft()] = t
last = 1
else:
res[enter.popleft()] = t
last = 0
t += 1
return res⚡ Complexity Deep Dive
⏱️ Time Complexity
O(n + max time): each person is enqueued and dequeued once, and the clock jump keeps the idle iterations to O(n).
💾 Space Complexity
O(n) for the two queues and the result.
⚠️ Interview Pitfalls & Follow-ups
- Forgetting to update
lastin the both-queues case when the exit side goes: it stays 1, which is correct, but the enter branch must set it to 0. - Initialising
lastto 0: nobody has used the door yet, so the rule gives exit priority, i.e.last = 1. - Not jumping the clock: when nobody is waiting, incrementing
tby one each iteration would be O(max arrival) which can be 10^9. - Admitting arrivals with
arrival[i] < tinstead of<= t: someone arriving exactly at the current second can still cross now.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.