Skip to main content
Talentd

Time Taken to Cross the Door - Solution & Explanation

HardPremiumFree on FleetCodeArrayQueueSimulation16 min readAsked at: Amazon, Salesforce, Google
Practice this problem

Problem Statement

There are n persons numbered from 0 to n - 1 and a door. Each person can enter or exit through the door once, taking one second.

You are given a non-decreasing integer array arrival of size n, where arrival[i] is the arrival time of the ith person at the door. You are also given an array state of size n, where state[i] is 0 if person i wants to enter through the door or 1 if they want to exit through the door.

If two or more persons want to use the door at the same time, they follow the following rules:

  • If the door was not used in the previous second, then the person who wants to exit goes first.
  • If the door was used in the previous second for entering, the person who wants to enter goes first.
  • If the door was used in the previous second for exiting, the person who wants to exit goes first.
  • If multiple persons want to go in the same direction, the person with the smallest index goes first.

Return an array answer of size n where answer[i] is the second at which the ith person crosses the door.

Note that:

  • Only one person can cross the door at each second.
  • A person may arrive at the door and wait without entering or exiting to follow the mentioned rules.

 

Example 1:

Input: arrival = [0,1,1,2,4], state = [0,1,0,0,1]
Output: [0,3,1,2,4]
Explanation: At each second we have the following:
- At t = 0: Person 0 is the only one who wants to enter, so they just enter through the door.
- At t = 1: Person 1 wants to exit, and person 2 wants to enter. Since the door was used the previous second for entering, person 2 enters.
- At t = 2: Person 1 still wants to exit, and person 3 wants to enter. Since the door was used the previous second for entering, person 3 enters.
- At t = 3: Person 1 is the only one who wants to exit, so they just exit through the door.
- At t = 4: Person 4 is the only one who wants to exit, so they just exit through the door.

Example 2:

Input: arrival = [0,0,0], state = [1,0,1]
Output: [0,2,1]
Explanation: At each second we have the following:
- At t = 0: Person 1 wants to enter while persons 0 and 2 want to exit. Since the door was not used in the previous second, the persons who want to exit get to go first. Since person 0 has a smaller index, they exit first.
- At t = 1: Person 1 wants to enter, and person 2 wants to exit. Since the door was used in the previous second for exiting, person 2 exits.
- At t = 2: Person 1 is the only one who wants to enter, so they just enter through the door.

 

Constraints:

  • n == arrival.length == state.length
  • 1 <= n <= 105
  • 0 <= arrival[i] <= n
  • arrival is sorted in non-decreasing order.
  • state[i] is either 0 or 1.

Approach Overview

Problem Overview: You are given two arrays arrival and state. Each person reaches a single door at a specific second and either wants to enter (0) or exit (1). Only one person can use the door per second, and the direction priority depends on how the door was used in the previous second. The task is to compute the exact time each person crosses the door.

Approach 1: Direct Timeline Simulation (Brute Force) (Time: O(T + n), Space: O(n))

A straightforward method simulates every second from time 0 until all people cross the door. At each second, scan the list of people who have already arrived and determine who is waiting to enter or exit. Apply the priority rule based on the previous second’s door usage. While this approach models the problem clearly, repeatedly scanning waiting people is inefficient when many seconds pass without events. The complexity depends on the total simulated time T, which may exceed n significantly.

Approach 2: Queue + Simulation (Optimal) (Time: O(n), Space: O(n))

Maintain two queues: one for people waiting to enter and another for people waiting to exit. Iterate through time while pushing newly arrived people into their respective queues. At each second, decide which queue gets access to the door using the rules: if the door was unused last second, exiting people get priority; otherwise the previous direction keeps priority. If the preferred queue is empty, serve the other queue. When both queues are empty, jump the simulation time directly to the next arrival to avoid idle iteration.

This design avoids repeated scans by storing waiting people in FIFO order. Each person enters and leaves a queue exactly once, so the simulation runs in linear time. The logic closely mirrors how operating systems simulate resource scheduling and is a common pattern in queue-based scheduling problems.

Recommended for interviews: The queue-based simulation is the expected solution. It processes each person once, runs in O(n) time, and cleanly models direction priority using a single variable tracking the last door usage. Interviewers often look for this pattern when testing understanding of array-driven events and simulation logic.

Solution

We define two queues, where q[0] stores the indices of people who want to enter, and q[1] stores the indices of people who want to exit.

We maintain a variable t to represent the current time, and a variable st to represent the current state of the door. When st = 1, it means the door is not in use or someone exited in the previous second. When st = 0, it means someone entered in the previous second. Initially, t = 0 and st = 1.

We traverse the array arrival. For each person, if the current time t is less than or equal to the time the person arrives at the door arrival[i], we add the person's index to the corresponding queue q[state[i]].

Then we check if both queues q[0] and q[1] are not empty. If both are not empty, we dequeue the front element from the queue q[st] and assign the current time t to the person's passing time. If only one queue is not empty, we update the value of st based on which queue is not empty, then dequeue the front element from that queue and assign the current time t to the person's passing time. If both queues are empty, we update the value of st to 1, indicating the door is not in use.

Next, we increment the time t by 1 and continue traversing the array arrival until all people have passed through the door.

The time complexity is O(n), and the space complexity is O(n). Here, n represents the length of the array arrival.

Code

PythonJavaC++GoTypeScriptRust

Python

Java

C++

Go

TypeScript

Rust

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Direct Timeline SimulationO(T + n)O(n)Useful for understanding the door priority rules before optimizing
Queue + SimulationO(n)O(n)Best general solution; processes arrivals once and models the door with two queues

Video Solution

Time Taken to Cross the Door - LeetCode Premium • LeetCode Україна • 1,837 views views

Watch 2 more video solutions →

Frequently Asked Questions

Is Time Taken to Cross the Door easy or hard?
The problem is labeled Hard because of the detailed simulation rules and direction priority conditions. The algorithm itself is linear once the queue strategy is recognized, but implementing the edge cases correctly requires careful reasoning.
Time Taken to Cross the Door Python/Java solution
Most implementations use two queues and simulate time. Python solutions often use collections.deque, while Java solutions use ArrayDeque or LinkedList. The same algorithm works in C++, Go, and TypeScript with standard queue structures.
How to solve Time Taken to Cross the Door in O(n)?
Maintain two queues for entering and exiting people and simulate the door second by second. Add newly arrived people to their respective queues and track the direction used in the previous second. Use that value to determine which queue gets priority. Each person is processed once, producing an O(n) time solution.
What is the best approach for Time Taken to Cross the Door?
The most efficient approach uses two queues and a simulation of time. One queue stores people waiting to enter and the other stores people waiting to exit. At each second, the algorithm chooses which queue gets access based on the previous door usage rule. This solution runs in O(n) time and O(n) space.
Is Time Taken to Cross the Door asked at Google/Amazon/Meta?
Door scheduling and event simulation problems appear frequently in interviews at companies like Amazon, Google, and Meta. While this exact problem may vary, the pattern of queue-based simulation and priority rules is commonly tested in system modeling questions.
What data structure is used in Time Taken to Cross the Door?
The core data structure is a queue. Two FIFO queues track people waiting to enter and exit, preserving arrival order. Additional variables track the current time and the direction used in the previous second to enforce priority rules.
What is the time complexity of Time Taken to Cross the Door?
The optimal queue-based simulation runs in O(n) time because each person is added to and removed from a queue exactly once. Space complexity is O(n) to store the queues and the result array. A naive simulation that scans waiting people every second can degrade to O(T + n) where T is the simulated timeline.

Ready to solve this problem?

Practice Time Taken to Cross the Door with our built-in code editor and test cases.

Practice on FleetCode
Previous

The Latest Time to Catch a Bus