BUS - Editorial

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