Validate alternating checkout/return logs

Given a chronological list of events logs of the form (timestamp, book_id, is_checkout) where is_checkout is True for a checkout and False for a return, implement a validator. For each book_id, the sequence must start with a checkout, alternate strictly between checkout and return, and must never contain a return before a checkout. The function should return True if all book_id sequences are valid and False otherwise. Specify the time and space complexity.

Validate Alternating Checkout/Return Logs

You are given a list of library event logs. Each log is a tuple (timestamp, book_id, is_checkout), where is_checkout is True for a checkout event and False for a return event.

The logs may arrive in any order, so you must first order them chronologically by timestamp. For each book_id, after ordering, the sequence of events must:

• Start with a checkout (a book cannot be returned before it has been checked out).
• Strictly alternate between checkout and return (checkout, return, checkout, return, ...).

Return True if every book_id's ordered sequence is valid, and False otherwise. An empty log list is considered valid.

Example (valid):

[(1, 'b1', True), (2, 'b1', False), (3, 'b1', True), (4, 'b1', False)]  ->  True

Example (invalid — starts with a return):

[(1, 'b1', False)]  ->  False

Example (invalid — two checkouts in a row for the same book):

[(1, 'b1', True), (2, 'b1', True)]  ->  False

Constraints

• 0 <= number of logs <= 10^5
• Each log is a tuple (timestamp, book_id, is_checkout).
• timestamps are unique integers; logs may be given in any order.
• book_id is a string; is_checkout is a boolean.
• An empty log list is valid (returns True).

Hints

1. Sort the logs by timestamp first, since they can arrive out of order.
2. Track, per book_id, whether the next expected event is a checkout or a return. The first expected event for any book is a checkout.
3. If any event does not match the expected type for its book, the whole input is invalid. A return before any checkout is just the special case where the very first expected event (checkout) is violated.