Skip to main content
Talentd

Design Bus Seat Booking System - Solution & Explanation

Medium17 min read
Practice this problem

Problem Statement

You are asked to design a seat booking system for a bus.

The bus has n rows. Each row has four seats labeled "A", "B", "C", and "D".

Seats "A" and "D" are window seats; seats "B" and "C" are middle seats. In each row, seat "A" is adjacent to seat "B", and seat "D" is adjacent to seat "C".

Booking rules:

  • Booking a middle seat ("B" or "C") always takes 1 second.
  • Booking a window seat ("A" or "D") takes 1 second if its adjacent middle seat is not booked, or 3 seconds (an extra delay of 2 seconds) if its adjacent middle seat is already booked.

A seat is identified by a string such as "A1" or "D20" (one letter from A to D followed by its row number).

Implement the BusBooking class:

  • BusBooking(int n): Initializes the system with n empty rows.
  • void toggle(string seat): Books seat if it is free, or frees it if it is already booked.
  • int getTotalTime(): Returns the total time (in seconds) taken to book all currently booked seats, where the seats are booked in the order their toggle calls were made. If no seats are currently booked, return 0.
  • int getMinTime(): Returns the smallest possible total time (in seconds) to book all currently booked seats, over every possible order of booking them. If no seats are currently booked, return 0.

Note: The time cost of a seat is fixed at the moment it is booked, based on the seats booked at that time. Booking or freeing other seats afterward does not change the cost of a seat that is already booked.

 

Example 1:

Input:
["BusBooking", "toggle", "toggle", "getTotalTime", "getMinTime", "toggle", "toggle", "getTotalTime", "getMinTime"]
[[20], ["B3"], ["A3"], [], [], ["C3"], ["D3"], [], []]

Output:
[null, null, null, 4, 2, null, null, 8, 4]

Explanation

BusBooking busBooking = new BusBooking(20); // start with 20 empty rows
busBooking.toggle("B3"); // book "B3", a middle seat, which costs 1 second. Total time is now 1.
busBooking.toggle("A3"); // book "A3", a window seat. Its adjacent middle "B3" is already booked, so it costs 3 seconds. Total time is now 1 + 3 = 4.
busBooking.getTotalTime(); // return 4, since in toggle order "B3" costs 1 and "A3" costs 3.
busBooking.getMinTime(); // return 2. Booking "A3" before "B3" avoids the delay, so 2 seats takes 2 second to book.
busBooking.toggle("C3"); // book "C3", a middle seat, which costs 1 second. Total time is now 1 + 4 = 5.
busBooking.toggle("D3"); // book "D3", a window seat. Its adjacent middle "C3" is already booked, so it costs 3 seconds. Total time is now 5 + 3 = 8.
busBooking.getTotalTime(); // return 8, since in toggle order the seat costs are 1, 3, 1, 3.
busBooking.getMinTime(); // return 4. With the best possible booking order, no delay is added, so the 4 booked seats take 4 * 1 = 4 seconds.

Example 2:

Input:
["BusBooking", "toggle", "toggle", "getTotalTime", "toggle", "toggle", "toggle", "getTotalTime", "getMinTime"]
[[10], ["C7"], ["D7"], [], ["D7"], ["C7"], ["D7"], [], []]

Output:
[null, null, null, 4, null, null, null, 1, 1]

Explanation

BusBooking busBooking = new BusBooking(10); // start with 10 empty rows
busBooking.toggle("C7"); // book "C7", a middle seat, which costs 1 second. Total time is now 1.
busBooking.toggle("D7"); // book "D7", a window seat. Its adjacent middle "C7" is already booked, so it costs 3 seconds. Total time is now 1 + 3 = 4.
busBooking.getTotalTime(); // return 4, since in toggle order "C7" costs 1 and "D7" costs 3.
busBooking.toggle("D7"); // "D7" is already booked, so free it. This removes its cost of 3. Total time is now 4 - 3 = 1.
busBooking.toggle("C7"); // "C7" is already booked, so free it. This removes its cost of 1. Total time is now 1 - 1 = 0, and row 7 is empty.
busBooking.toggle("D7"); // book "D7" again, a window seat. Its adjacent middle "C7" is not booked this time, so it costs only 1 second. Total time is now 0 + 1 = 1.
busBooking.getTotalTime(); // return 1, since only "D7" is booked and it cost 1 this time.
busBooking.getMinTime(); // return 1. With the best possible booking order, the 1 booked seat takes 1 * 1 = 1 second.

 

Constraints:

  • 1 <= n <= 105ā€‹ā€‹ā€‹ā€‹ā€‹ā€‹ā€‹
  • seat[0] is one of 'A', 'B', 'C', 'D'.
  • The remaining characters of seat form an integer row with 1 <= row <= n.
  • The total number of calls to toggle, getTotalTime, and getMinTime does not exceed 105.

Approach Overview

Problem Overview: You manage a bus with numbered seats. Reserving returns the smallest-numbered free seat and marks it taken. Cancelling a specific seat makes it free again. Every operation has to be fast, and the reserve operation always has to find the smallest free seat.

Approach 1: Linear Scan over a Boolean Array (O(n) per reserve, O(n) space)

Keep a boolean array where index i tells you whether seat i is booked. On reserve, iterate from seat 1 upward and return the first index that is free. Cancel is a single write to the array, so it runs in O(1). This is simple and correct, but reserve gets slow when most seats are booked, because you scan the same prefix over and over. Use it only as a baseline to explain the bottleneck.

Approach 2: Min-Heap with Lazy Deletion (O(log n) per operation, O(n) space)

Store all free seats in a min-heap. Reserve calls heappop to get the smallest free seat in O(log n). Cancel pushes the seat back into the heap in O(log n). To prevent duplicates, keep a hash set of currently free seats so you can reject a cancel for a seat that is already free. The key insight is that the heap gives you the minimum for free, so you never scan. Prefer this approach when the number of seats is large and reserve is the dominant call.

Approach 3: Ordered Set or Segment Tree (O(log n) per operation, O(n) space)

A balanced BST or a segment tree over seat indices also gives O(log n) for both operations. The segment tree stores the count of free seats in each range, so reserve descends toward the leftmost leaf with a free seat. This avoids duplicate handling and works well if you later add range queries, such as counting free seats between two numbers. It takes more code than the heap, so reach for it only when you need those extra queries.

Recommended for interviews: Start with the linear scan to show you understand the state. Then move to the min-heap with a hash set. The brute force shows you can model the problem. The heap solution shows you can pick the right data structure for the operation that matters most. Mention the segment tree as an alternative if the interviewer asks for range queries. Review the heap topic and design topic if the lazy deletion pattern is new to you.

Solution

Thinking

Both the number of rows and the number of calls can reach 10^5, so replaying the whole booking history on every query exceeds the limit.

A window seat costs an extra 2 seconds only when its adjacent middle seat is already booked, and that cost is fixed at the moment toggle books it. getTotalTime is the sum of the costs recorded for the seats that are still occupied.

getMinTime may reorder the booking of those seats. A middle seat always costs 1 second; booking a window seat before its adjacent middle seat avoids the extra 2 seconds. The minimum time is therefore the number of seats currently booked. Store each seat's cost from the moment it was booked, keep the total and the occupancy count separately, and every operation is O(1).

Each row is stored as an array of length 4. A cell value of 0 means the seat is free; otherwise it is the number of seconds fixed when that seat was booked. The variable tot keeps the sum of these costs, and a counter keeps the number of seats currently booked.

When toggle sees a booked seat, subtract its stored cost from tot, decrease the counter, and clear the cell. When the seat is free, a middle seat \texttt{B} or \texttt{C} costs 1 second. A window seat \texttt{A} or \texttt{D} costs 3 seconds if its adjacent middle seat is already booked, and 1 second otherwise. Write that cost into the array and update both tot and the counter.

getTotalTime returns tot, and getMinTime returns the number of booked seats.

Each operation takes O(1) time, and the space complexity is O(n), where n is the number of rows.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor ā†’

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Linear scan over boolean arrayReserve O(n), Cancel O(1)O(n)Small bus, or as a baseline before optimizing
Min-heap with hash setReserve O(log n), Cancel O(log n)O(n)General case, frequent reserve calls
Segment tree or ordered setO(log n) per operationO(n)When you also need range queries over free seats

Video Solutions (4)

LeetCode | Weekly Contest 523 Q3 | Design Bus Seat Booking System | C++

CodeSprint16:50117 views
Video 1 of 4

Frequently Asked Questions

Design Bus Seat Booking System Python solution?
In Python, use the heapq module for the min-heap and a set for free seats. Initialize the heap with a list of seat numbers, which is already a valid heap in sorted order. Reserve pops until it finds a seat present in the set, and cancel pushes the seat back if it is not already free.
Is Design Bus Seat Booking System easy or hard?
It is a medium-difficulty design problem with a 42.6 percent acceptance rate on FleetCode. The logic is short, but the difficulty comes from choosing the right data structure and handling duplicate cancels correctly. Once you know the heap with lazy deletion pattern, the implementation takes under 30 lines.
How to solve Design Bus Seat Booking System in O(log n)?
Use a min-heap initialized with seat numbers 1 through n, and a hash set that mirrors the free seats. On reserve, pop from the heap until you find a seat that is still in the set, then remove it from the set. On cancel, if the seat is not in the set, add it to the set and push it onto the heap.
What is the best approach for Design Bus Seat Booking System?
The best approach is a min-heap of free seats paired with a hash set that tracks which seats are currently free. Reserve pops the smallest seat in O(log n), and cancel pushes it back in O(log n). This avoids scanning the whole seat array on every reserve.
What data structure is used in Design Bus Seat Booking System?
The optimal solution uses a min-heap to return the smallest free seat efficiently and a hash set to track which seats are free. A segment tree or balanced BST is an alternative when you need range queries on seat availability.
What is the time complexity of Design Bus Seat Booking System?
The optimal solution runs reserve and cancel in O(log n) time each, where n is the number of seats. Space complexity is O(n) to store the seat state. The naive linear scan runs reserve in O(n) time, which is too slow when most seats are booked.
Is Design Bus Seat Booking System asked at Google, Amazon, or Meta?
This problem is tagged as General on FleetCode, so it does not map to a specific company list. Design-style problems like this appear in onsite and take-home rounds at many large tech companies. Practice the heap and hash set pattern, since it transfers to other seat and resource allocation questions.

Ready to solve this problem?

Practice Design Bus Seat Booking System with our built-in code editor and test cases.

Practice on FleetCode