# PROBLEM LINK:

Contest - Division 3

Contest - Division 2

Contest - Division 1

# DIFFICULTY:

CAKEWALK

# PROBLEM:

There is an empty bus with M seats. There are N passengers. Given a list of length Q, the order in which the passengers entered and exited the bus. Determine if the list is consistent (passengers leave only after they board the bus; the number of passengers don’t exceed M at any given time).

# EXPLANATION:

Maintain an array that holds the boarding status of the N passengers (1 if the passenger is on the bus and 0 otherwise) . All values are initially 0. Also maintain a variable cnt, representing the number of passengers on the bus. cnt is initially 0.

Now, iterate over the list. For each + move, verify if the boarding status of the passenger is 0 (otherwise the list is inconsistent). Similarly, for each - move, verify if the boarding status of the passenger is 1.

Lastly, update the values of the boarding status and cnt (add 1 for + move, subtract 1 for - move) and verify if cnt \le M.

If at any time, the verification doesn’t hold, the list is inconsistent. Else it is consistent.

# TIME COMPLEXITY:

For each test case, Q operations are done (one for each entry in the list).

Thus, the time complexity is O(Q) per test case.

# SOLUTIONS:

Editorialist’s solution can be found here.

*Experimental:* For evaluation purposes, please rate the editorial (1 being poor and 5 excellent)

- 1
- 2
- 3
- 4
- 5

0 voters