LeetCode 2534 - Time Taken to Cross the Door
This problem asks us to simulate how people pass through a single door over time while following a specific priority policy. Every person arrives at a certain second and wants to either enter or exit.
Difficulty: 🔴 Hard
Topics: Array, Queue, Simulation
Solution
Problem Understanding
This problem asks us to simulate how people pass through a single door over time while following a specific priority policy. Every person arrives at a certain second and wants to either enter or exit. Only one person may use the door per second, and when multiple people are waiting, the rules determine who gets priority.
The input contains two arrays:
-
arrival[i]represents the time when personireaches the door. -
state[i]represents the direction: -
0means the person wants to enter. -
1means the person wants to exit.
The arrays are aligned by index, meaning person i has arrival time arrival[i] and desired direction state[i].
The output is an array answer where answer[i] is the exact second when person i successfully crosses the door.
The important part of the problem is the priority logic. The door remembers what happened during the previous second:
- If the door was unused in the previous second, exiting people get priority.
- If the door was used for entering, entering people keep priority.
- If the door was used for exiting, exiting people keep priority.
- Within the same direction, smaller indices go first.
The constraints are large:
ncan be up to10^5- Arrival times are sorted in non-decreasing order
This immediately tells us that a quadratic simulation is too slow. We need a solution close to linear time.
Several edge cases are especially important:
- Multiple people arriving at the same time with different directions.
- Long idle gaps where nobody is waiting.
- Situations where one queue becomes empty while the other still contains people.
- Continuous sequences where the same direction repeatedly gets priority because the door keeps being used in that direction.
- Arrival times with many duplicates.
A naive implementation often fails when handling the transition between idle and active states, because the priority resets after an unused second.
Approaches
Brute Force Approach
A brute force simulation would examine every second independently and repeatedly scan all people to determine who is eligible to use the door.
At every second:
- Find all people who have arrived but not crossed yet.
- Separate them into entering and exiting groups.
- Apply the door rules.
- Select the next person.
This produces the correct answer because it directly follows the problem statement. However, the implementation repeatedly scans the entire array for every simulated second.
In the worst case, there may be up to O(n) simulated seconds, and each second may require an O(n) scan. That leads to O(n^2) time complexity, which is too slow for n = 10^5.
Optimal Approach
The key observation is that people arrive in sorted order, and once a person arrives, they simply wait in a queue corresponding to their direction.
This naturally suggests using two queues:
- One queue for entering people.
- One queue for exiting people.
We process time chronologically and continuously add newly arrived people into the appropriate queue. Then, at each second, we decide which queue gets priority based on the previous door usage.
The important insight is that we never need to rescan old people. Every person:
- Enters a queue once.
- Leaves a queue once.
That allows the simulation to run in linear time.
| Approach | Time Complexity | Space Complexity | Notes |
|---|---|---|---|
| Brute Force | O(n²) | O(n) | Repeatedly scans all waiting people at every second |
| Optimal | O(n) | O(n) | Uses two queues and chronological simulation |
Algorithm Walkthrough
- Initialize two queues:
enter_queuefor people wanting to enter.exit_queuefor people wanting to exit.
These queues preserve index order automatically because people are processed in arrival order.
2. Maintain a pointer i into the input arrays.
This pointer tracks which people have not yet been added into the waiting queues.
3. Maintain a variable current_time.
This represents the second currently being simulated.
4. Maintain another variable last_direction.
This stores how the door was used during the previous second:
0for entering1for exiting-1if the door was unused during the previous second
- At every time step, add all newly arrived people into their corresponding queues.
Since arrival is sorted, we can process arrivals efficiently using the pointer i.
6. If both queues are empty, the door is idle.
In this case:
- Set
last_direction = -1 - Jump
current_timedirectly to the next arrival time instead of incrementing one by one.
This optimization avoids wasting time simulating empty seconds. 7. Otherwise, determine which direction gets priority.
The rules are:
- If
last_direction == -1, exiting gets priority. - If
last_direction == 1, exiting keeps priority. - If
last_direction == 0, entering keeps priority.
- Select the front person from the chosen queue.
If the preferred queue is empty, use the other queue instead. 9. Record the crossing time for that person.
Store current_time into the result array.
10. Update last_direction to the direction used this second.
11. Increment current_time by one.
12. Continue until every person has crossed.
Why it works
The algorithm maintains an exact simulation of the system state at every second. The queues always contain precisely the people who have arrived but not yet crossed. Since the queues preserve arrival order and smaller indices naturally appear first, the tie-breaking rule within the same direction is automatically satisfied.
The last_direction variable correctly models the door memory from the previous second, which guarantees that the priority rules are applied exactly as specified.
Because every person is inserted and removed from a queue exactly once, the algorithm remains linear while still performing a faithful simulation.
Python Solution
from collections import deque
from typing import List
class Solution:
def timeTaken(self, arrival: List[int], state: List[int]) -> List[int]:
n = len(arrival)
enter_queue = deque()
exit_queue = deque()
answer = [0] * n
current_time = 0
i = 0
# -1 = unused last second
# 0 = enter used last second
# 1 = exit used last second
last_direction = -1
while i < n or enter_queue or exit_queue:
# If nobody is waiting, jump to next arrival time
if not enter_queue and not exit_queue and i < n:
current_time = max(current_time, arrival[i])
last_direction = -1
# Add everyone arriving at current_time
while i < n and arrival[i] <= current_time:
if state[i] == 0:
enter_queue.append(i)
else:
exit_queue.append(i)
i += 1
# Decide who uses the door
if exit_queue and (
last_direction == 1 or last_direction == -1 or not enter_queue
):
person = exit_queue.popleft()
answer[person] = current_time
last_direction = 1
else:
person = enter_queue.popleft()
answer[person] = current_time
last_direction = 0
current_time += 1
return answer
The implementation directly follows the simulation strategy.
Two deque structures are used because queue operations at both ends are efficient in Python. The variable i tracks which people have already been inserted into the waiting queues.
The most important optimization appears in the idle handling block:
if not enter_queue and not exit_queue and i < n:
current_time = max(current_time, arrival[i])
last_direction = -1
Instead of simulating every empty second, the algorithm jumps directly to the next arrival time. This is critical for maintaining linear complexity.
The decision logic closely mirrors the problem statement. Exiting people receive priority if:
- The previous usage was exiting.
- The door was idle previously.
- No entering people are waiting.
Otherwise, entering people use the door.
Every person is processed exactly once, making the implementation efficient and scalable.
Go Solution
func timeTaken(arrival []int, state []int) []int {
n := len(arrival)
enterQueue := make([]int, 0)
exitQueue := make([]int, 0)
answer := make([]int, n)
currentTime := 0
i := 0
// -1 = unused
// 0 = enter
// 1 = exit
lastDirection := -1
for i < n || len(enterQueue) > 0 || len(exitQueue) > 0 {
// Jump to next arrival if idle
if len(enterQueue) == 0 && len(exitQueue) == 0 && i < n {
if currentTime < arrival[i] {
currentTime = arrival[i]
}
lastDirection = -1
}
// Add all arrived people
for i < n && arrival[i] <= currentTime {
if state[i] == 0 {
enterQueue = append(enterQueue, i)
} else {
exitQueue = append(exitQueue, i)
}
i++
}
// Choose who crosses
if len(exitQueue) > 0 &&
(lastDirection == 1 ||
lastDirection == -1 ||
len(enterQueue) == 0) {
person := exitQueue[0]
exitQueue = exitQueue[1:]
answer[person] = currentTime
lastDirection = 1
} else {
person := enterQueue[0]
enterQueue = enterQueue[1:]
answer[person] = currentTime
lastDirection = 0
}
currentTime++
}
return answer
}
The Go implementation mirrors the Python logic closely. Since Go does not provide a built-in deque structure, slices are used as queues. Removing the front element is handled with:
queue = queue[1:]
This is efficient enough for this problem because each element is removed only once overall.
Integer overflow is not a concern because all values remain within standard 32-bit integer range.
Worked Examples
Example 1
arrival = [0,1,1,2,4]
state = [0,1,0,0,1]
Expected output:
[0,3,1,2,4]
| Time | Enter Queue | Exit Queue | Last Direction | Selected Person | Result |
|---|---|---|---|---|---|
| 0 | [0] | [] | idle | 0 enters | ans[0] = 0 |
| 1 | [2] | [1] | enter | 2 enters | ans[2] = 1 |
| 2 | [3] | [1] | enter | 3 enters | ans[3] = 2 |
| 3 | [] | [1] | enter | 1 exits | ans[1] = 3 |
| 4 | [] | [4] | exit | 4 exits | ans[4] = 4 |
Final answer:
[0,3,1,2,4]
Example 2
arrival = [0,0,0]
state = [1,0,1]
Expected output:
[0,2,1]
| Time | Enter Queue | Exit Queue | Last Direction | Selected Person | Result |
|---|---|---|---|---|---|
| 0 | [1] | [0,2] | idle | 0 exits | ans[0] = 0 |
| 1 | [1] | [2] | exit | 2 exits | ans[2] = 1 |
| 2 | [1] | [] | exit | 1 enters | ans[1] = 2 |
Final answer:
[0,2,1]
Complexity Analysis
| Measure | Complexity | Explanation |
|---|---|---|
| Time | O(n) | Each person enters and leaves a queue exactly once |
| Space | O(n) | Queues and result array may store all people |
The algorithm is linear because every person is processed a constant number of times. No rescanning occurs. The idle-time optimization also prevents unnecessary simulation of empty seconds.
The space complexity is linear because, in the worst case, all people may wait in queues simultaneously.
Test Cases
from typing import List
class Solution:
def timeTaken(self, arrival: List[int], state: List[int]) -> List[int]:
from collections import deque
n = len(arrival)
enter_queue = deque()
exit_queue = deque()
answer = [0] * n
current_time = 0
i = 0
last_direction = -1
while i < n or enter_queue or exit_queue:
if not enter_queue and not exit_queue and i < n:
current_time = max(current_time, arrival[i])
last_direction = -1
while i < n and arrival[i] <= current_time:
if state[i] == 0:
enter_queue.append(i)
else:
exit_queue.append(i)
i += 1
if exit_queue and (
last_direction == 1 or
last_direction == -1 or
not enter_queue
):
person = exit_queue.popleft()
answer[person] = current_time
last_direction = 1
else:
person = enter_queue.popleft()
answer[person] = current_time
last_direction = 0
current_time += 1
return answer
sol = Solution()
assert sol.timeTaken(
[0,1,1,2,4],
[0,1,0,0,1]
) == [0,3,1,2,4] # provided example 1
assert sol.timeTaken(
[0,0,0],
[1,0,1]
) == [0,2,1] # provided example 2
assert sol.timeTaken(
[0],
[0]
) == [0] # single entering person
assert sol.timeTaken(
[0],
[1]
) == [0] # single exiting person
assert sol.timeTaken(
[0,1,2],
[0,0,0]
) == [0,1,2] # all entering
assert sol.timeTaken(
[0,1,2],
[1,1,1]
) == [0,1,2] # all exiting
assert sol.timeTaken(
[0,0,0,0],
[0,1,0,1]
) == [2,0,3,1] # alternating priorities
assert sol.timeTaken(
[0,5],
[1,0]
) == [0,5] # large idle gap
assert sol.timeTaken(
[0,0,1,1],
[1,0,0,1]
) == [0,2,3,1] # switching direction priorities
assert sol.timeTaken(
[0,0,0,1,1,1],
[1,1,0,0,1,0]
) == [0,1,4,5,2,3] # dense mixed arrivals
| Test | Why |
|---|---|
[0,1,1,2,4] |
Validates the first official example |
[0,0,0] |
Validates the second official example |
| Single person entering | Smallest possible input |
| Single person exiting | Ensures exit-only handling works |
| All entering | Confirms continuous enter priority |
| All exiting | Confirms continuous exit priority |
| Simultaneous mixed arrivals | Tests tie-breaking rules |
| Large idle gap | Verifies idle reset behavior |
| Direction switching | Ensures previous-second memory works |
| Dense mixed arrivals | Stress test for queue interaction |
Edge Cases
One important edge case occurs when the door becomes idle for one or more seconds. The problem states that after an unused second, exiting people regain priority. Many incorrect implementations forget to reset the door state after idle periods. This implementation explicitly sets last_direction = -1 whenever both queues are empty, ensuring the rule is handled correctly.
Another tricky case happens when many people arrive simultaneously. Since the problem requires smaller indices to go first within the same direction, the queues must preserve insertion order exactly. Because arrivals are processed in sorted order and appended directly into FIFO queues, the implementation naturally satisfies this requirement.
A third important edge case occurs when one queue becomes empty while the other still contains waiting people. For example, if no entering people remain, exiting people must continue crossing regardless of previous direction priority. The implementation handles this by explicitly checking whether the preferred queue is empty before deciding which side crosses.
A final subtle case involves large gaps between arrival times. A naive second-by-second simulation may waste enormous amounts of time iterating through empty intervals. The implementation avoids this by jumping directly to the next arrival time whenever both queues are empty, preserving linear complexity even for sparse arrival schedules.