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