Time Taken to Cross the Door - Practice Coding Problems

Time Taken to Cross the Door - Problem

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 i^th 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 these 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 i^th person crosses the door.

Note: 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.

Input & Output

Example 1 — Basic Priority Rules

$ Input: arrival = [0,1,1,2], state = [0,1,0,1]

› Output: [0,2,1,3]

💡 Note: Person 0 (enter) arrives at time 0, crosses at time 0. At time 1, persons 1 (exit) and 2 (enter) arrive. Since door unused last second, person 1 (exit) has priority and crosses at time 2. Person 2 (enter) crosses at time 1. Person 3 (exit) arrives at time 2 and crosses at time 3.

Example 2 — Same Direction Priority

$ Input: arrival = [0,0,0], state = [1,1,1]

› Output: [0,1,2]

💡 Note: All three people want to exit and arrive at time 0. Door is unused, so exit has priority. Person 0 goes first (lowest index), then 1, then 2.

Example 3 — Enter After Enter

$ Input: arrival = [0,1,2], state = [0,0,1]

› Output: [0,1,2]

💡 Note: Person 0 enters at time 0. Person 1 arrives at time 1 and wants to enter - since last action was enter, person 1 enters at time 1. Person 2 arrives at time 2 and exits at time 2.

Constraints

1 ≤ n ≤ 10⁵
0 ≤ arrival[i] ≤ 10⁵
arrival is sorted in non-decreasing order
state[i] is either 0 or 1

Visualization

Tap to expand

Understanding the Visualization

Input

People with arrival times and enter/exit states

Priority Rules

Apply door usage rules to determine order

Output

Array showing when each person crosses

Key Takeaway

🎯 Key Insight: Track door state and use priority rules to determine who crosses next

Asked in

G Google 45 a Amazon 38 M Microsoft 22

The key insight is to simulate door usage with priority rules: unused door favors exit, otherwise favor same direction as last action. Best approach uses queue-based simulation to efficiently manage people by direction. Time: O(n + T), Space: O(n)

Common Approaches

Approach	Time	Space	Notes
✓ Queue-Based Simulation	O(n + T)	O(n)	Use separate queues for entering and exiting people with efficient processing
Brute Force Simulation	O(n × T)	O(n)	Simulate each second, checking all people waiting at door

Queue-Based Simulation — Algorithm Steps

Step 1: Separate people into enter/exit queues based on arrival time
Step 2: At each time, add newly arrived people to appropriate queues
Step 3: Use priority rules to select from queues and process crossing

Visualization

Tap to expand

Step-by-Step Walkthrough

Queue Setup

Create separate queues for enter and exit

Add Arrivals

Add people to appropriate queue as they arrive

Process Priority

Use door state to select from correct queue

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

typedef struct {
    int* data;
    int front, rear, size, capacity;
} Queue;

Queue* createQueue(int capacity) {
    Queue* q = (Queue*)malloc(sizeof(Queue));
    q->data = (int*)malloc(capacity * sizeof(int));
    q->front = 0;
    q->rear = -1;
    q->size = 0;
    q->capacity = capacity;
    return q;
}

void enqueue(Queue* q, int val) {
    if (q->size < q->capacity) {
        q->rear = (q->rear + 1) % q->capacity;
        q->data[q->rear] = val;
        q->size++;
    }
}

int dequeue(Queue* q) {
    if (q->size > 0) {
        int val = q->data[q->front];
        q->front = (q->front + 1) % q->capacity;
        q->size--;
        return val;
    }
    return -1;
}

bool isEmpty(Queue* q) {
    return q->size == 0;
}

void freeQueue(Queue* q) {
    free(q->data);
    free(q);
}

int* solution(int* arrival, int arrivalSize, int* state, int stateSize, int* returnSize) {
    int n = arrivalSize;
    int* answer = (int*)calloc(n, sizeof(int));
    *returnSize = n;
    
    Queue* enterQueue = createQueue(n);
    Queue* exitQueue = createQueue(n);
    
    int currentTime = 0;
    int lastAction = -1; // -1: unused, 0: enter, 1: exit
    int personIdx = 0;
    
    while (personIdx < n || !isEmpty(enterQueue) || !isEmpty(exitQueue)) {
        // Add all people who arrive at currentTime
        while (personIdx < n && arrival[personIdx] <= currentTime) {
            if (state[personIdx] == 0) {
                enqueue(enterQueue, personIdx);
            } else {
                enqueue(exitQueue, personIdx);
            }
            personIdx++;
        }
        
        if (isEmpty(enterQueue) && isEmpty(exitQueue)) {
            currentTime++;
            continue;
        }
        
        // Apply priority rules
        int nextPerson = -1;
        if (lastAction == -1) { // Door unused, exit priority
            if (!isEmpty(exitQueue)) {
                nextPerson = dequeue(exitQueue);
            } else if (!isEmpty(enterQueue)) {
                nextPerson = dequeue(enterQueue);
            }
        } else if (lastAction == 0) { // Last was enter, enter priority
            if (!isEmpty(enterQueue)) {
                nextPerson = dequeue(enterQueue);
            } else if (!isEmpty(exitQueue)) {
                nextPerson = dequeue(exitQueue);
            }
        } else { // Last was exit, exit priority
            if (!isEmpty(exitQueue)) {
                nextPerson = dequeue(exitQueue);
            } else if (!isEmpty(enterQueue)) {
                nextPerson = dequeue(enterQueue);
            }
        }
        
        if (nextPerson != -1) {
            answer[nextPerson] = currentTime;
            lastAction = state[nextPerson];
        }
        
        currentTime++;
    }
    
    freeQueue(enterQueue);
    freeQueue(exitQueue);
    return answer;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    line[strcspn(line, "\n")] = 0;
    
    // Parse arrival array
    int arrival[1000];
    int arrivalSize = 0;
    char* token = strtok(line + 1, ",]");
    while (token != NULL) {
        arrival[arrivalSize++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    fgets(line, sizeof(line), stdin);
    line[strcspn(line, "\n")] = 0;
    
    // Parse state array
    int state[1000];
    int stateSize = 0;
    token = strtok(line + 1, ",]");
    while (token != NULL) {
        state[stateSize++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    int returnSize;
    int* result = solution(arrival, arrivalSize, state, stateSize, &returnSize);
    
    printf("[");
    for (int i = 0; i < returnSize; i++) {
        if (i > 0) printf(",");
        printf("%d", result[i]);
    }
    printf("]\n");
    
    free(result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n + T)

Each person is added/removed from queue once, plus T time steps where T is max crossing time

✓ Linear Growth

Space Complexity

O(n)

Two queues store up to n people total, plus result array

⚡ Linearithmic Space

28.5K Views

Medium Frequency

~25 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Queue-Based Simulation — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler