2534. Time Taken to Cross the Door
Problem Explanation
In this problem, there are n
persons who want to enter or exit through a door. Each person can enter or exit through the door once, taking one second. We 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. Also, there is 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.
The main goal is to find an array answer
of size n
where answer[i]
is the second at which the i
th person crosses the door, considering various rules regarding entering and exiting the door.
Example Walkthrough
Consider the example:
arrival = [0, 1, 1, 2, 4]
state = [0, 1, 0, 0, 1]
The expected output is [0, 3, 1, 2, 4]
.
Here's how we can process each second:
- 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.
Therefore, the answer is [0, 3, 1, 2, 4]
.
Solution Approach
We can use two pointers approach for solving this problem. First, we can create two lists, one for the entering persons and one for the exiting persons, and initialize pointers at the beginning of those lists. Next, we can iterate until both pointers reach the end of their respective lists. Finally, we can follow the rules stated in the problem description for entering and exiting persons and update the answer array accordingly.
Python Solution
1class Solution:
2 def timeTaken(self, arrival: List[int], state: List[int]) -> List[int]:
3 n = len(arrival)
4 answer = [0] * n
5 enter = []
6 exit = []
7
8 # Separate entering and exiting persons
9 for i in range(n):
10 if state[i] == 0:
11 enter.append(i)
12 else:
13 exit.append(i)
14
15 enter_ptr = 0
16 exit_ptr = 0
17 prev_action = -1
18 time = 0
19
20 # Iterate until both pointers reach the end
21 while enter_ptr < len(enter) or exit_ptr < len(exit):
22 # Check rules for entering and exiting persons
23 if (enter_ptr < len(enter) and exit_ptr < len(exit) and
24 arrival[enter[enter_ptr]] <= time and arrival[exit[exit_ptr]] <= time):
25 if prev_action == 0:
26 answer[enter[enter_ptr]] = time
27 enter_ptr += 1
28 prev_action = 0
29 else:
30 answer[exit[exit_ptr]] = time
31 exit_ptr += 1
32 prev_action = 1
33 elif enter_ptr < len(enter) and arrival[enter[enter_ptr]] <= time:
34 answer[enter[enter_ptr]] = time
35 enter_ptr += 1
36 prev_action = 0
37 elif exit_ptr < len(exit) and arrival[exit[exit_ptr]] <= time:
38 answer[exit[exit_ptr]] = time
39 exit_ptr += 1
40 prev_action = 1
41 else:
42 prev_action = -1
43
44 time += 1
45
46 return answer
*Note: Solutions for Java, JavaScript, C++, and C# are beyond the scope of this prompt, but following the same approach mentioned above, we can create solutions for those languages as well.*JavaScript Solution
1class Solution {
2 timeTaken(arrival, state) {
3 const n = arrival.length;
4 const answer = Array(n).fill(0);
5 const enter = [];
6 const exit = [];
7
8 // Separate entering and exiting persons
9 for (let i = 0; i < n; i++) {
10 if (state[i] === 0) {
11 enter.push(i);
12 } else {
13 exit.push(i);
14 }
15 }
16
17 let enter_ptr = 0;
18 let exit_ptr = 0;
19 let prev_action = -1;
20 let time = 0;
21
22 // Iterate until both pointers reach the end
23 while (enter_ptr < enter.length || exit_ptr < exit.length) {
24 // Check rules for entering and exiting persons
25 if (enter_ptr < enter.length && exit_ptr < exit.length &&
26 arrival[enter[enter_ptr]] <= time && arrival[exit[exit_ptr]] <= time) {
27 if (prev_action === 0) {
28 answer[enter[enter_ptr]] = time;
29 enter_ptr++;
30 prev_action = 0;
31 } else {
32 answer[exit[exit_ptr]] = time;
33 exit_ptr++;
34 prev_action = 1;
35 }
36 } else if (enter_ptr < enter.length && arrival[enter[enter_ptr]] <= time) {
37 answer[enter[enter_ptr]] = time;
38 enter_ptr++;
39 prev_action = 0;
40 } else if (exit_ptr < exit.length && arrival[exit[exit_ptr]] <= time) {
41 answer[exit[exit_ptr]] = time;
42 exit_ptr++;
43 prev_action = 1;
44 } else {
45 prev_action = -1;
46 }
47
48 time++;
49 }
50
51 return answer;
52 }
53}
Java Solution
1import java.util.*;
2
3class Solution {
4 public int[] timeTaken(int[] arrival, int[] state) {
5 int n = arrival.length;
6 int[] answer = new int[n];
7 List<Integer> enter = new ArrayList<>();
8 List<Integer> exit = new ArrayList<>();
9
10 // Separate entering and exiting persons
11 for (int i = 0; i < n; i++) {
12 if (state[i] == 0) {
13 enter.add(i);
14 } else {
15 exit.add(i);
16 }
17 }
18
19 int enter_ptr = 0;
20 int exit_ptr = 0;
21 int prev_action = -1;
22 int time = 0;
23
24 // Iterate until both pointers reach the end
25 while (enter_ptr < enter.size() || exit_ptr < exit.size()) {
26 // Check rules for entering and exiting persons
27 if (enter_ptr < enter.size() && exit_ptr < exit.size() &&
28 arrival[enter.get(enter_ptr)] <= time && arrival[exit.get(exit_ptr)] <= time) {
29 if (prev_action == 0) {
30 answer[enter.get(enter_ptr)] = time;
31 enter_ptr++;
32 prev_action = 0;
33 } else {
34 answer[exit.get(exit_ptr)] = time;
35 exit_ptr++;
36 prev_action = 1;
37 }
38 } else if (enter_ptr < enter.size() && arrival[enter.get(enter_ptr)] <= time) {
39 answer[enter.get(enter_ptr)] = time;
40 enter_ptr++;
41 prev_action = 0;
42 } else if (exit_ptr < exit.size() && arrival[exit.get(exit_ptr)] <= time) {
43 answer[exit.get(exit_ptr)] = time;
44 exit_ptr++;
45 prev_action = 1;
46 } else {
47 prev_action = -1;
48 }
49
50 time++;
51 }
52
53 return answer;
54 }
55}
These solutions follow the same approach mentioned above and can be used for the respective programming languages.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorWhich two pointer techniques do you use to check if a string is a palindrome?
Recommended Readings
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Runtime Overview When learning about algorithms and data structures you'll frequently encounter the term time complexity This concept is fundamental in computer science and offers insights into how long an algorithm takes to complete given a certain input size What is Time Complexity Time complexity represents the amount of time