Minimum Number of Chairs in a Waiting Room - Solution & Explanation
Problem Statement
You are given a string s. Simulate events at each second i:
- If
s[i] == 'E', a person enters the waiting room and takes one of the chairs in it. - If
s[i] == 'L', a person leaves the waiting room, freeing up a chair.
Return the minimum number of chairs needed so that a chair is available for every person who enters the waiting room given that it is initially empty.
Example 1:
Input: s = "EEEEEEE"
Output: 7
Explanation:
After each second, a person enters the waiting room and no person leaves it. Therefore, a minimum of 7 chairs is needed.
Example 2:
Input: s = "ELELEEL"
Output: 2
Explanation:
Let's consider that there are 2 chairs in the waiting room. The table below shows the state of the waiting room at each second.
| Second | Event | People in the Waiting Room | Available Chairs |
|---|---|---|---|
| 0 | Enter | 1 | 1 |
| 1 | Leave | 0 | 2 |
| 2 | Enter | 1 | 1 |
| 3 | Leave | 0 | 2 |
| 4 | Enter | 1 | 1 |
| 5 | Enter | 2 | 0 |
| 6 | Leave | 1 | 1 |
Example 3:
Input: s = "ELEELEELLL"
Output: 3
Explanation:
Let's consider that there are 3 chairs in the waiting room. The table below shows the state of the waiting room at each second.
| Second | Event | People in the Waiting Room | Available Chairs |
|---|---|---|---|
| 0 | Enter | 1 | 2 |
| 1 | Leave | 0 | 3 |
| 2 | Enter | 1 | 2 |
| 3 | Enter | 2 | 1 |
| 4 | Leave | 1 | 2 |
| 5 | Enter | 2 | 1 |
| 6 | Enter | 3 | 0 |
| 7 | Leave | 2 | 1 |
| 8 | Leave | 1 | 2 |
| 9 | Leave | 0 | 3 |
Constraints:
1 <= s.length <= 50sconsists only of the letters'E'and'L'.srepresents a valid sequence of entries and exits.
Approach Overview
Problem Overview: You receive a string representing events in a waiting room. Each character indicates whether a person enters or leaves. The task is to compute the minimum number of chairs required so that every person who enters always has a seat available.
Approach 1: Simulate Each Event Using Two Counters (O(n) time, O(1) space)
This method directly simulates the waiting room activity using counters. Iterate through the string and update the number of people currently sitting whenever someone enters or leaves. When an entry occurs, increase the current occupancy and update the maximum occupancy seen so far. When a person leaves, decrease the counter. The maximum occupancy at any point equals the minimum number of chairs required. This approach models the system exactly as described and is easy to reason about when dealing with string-based event logs and simple simulation problems.
Approach 2: Optimized with Incremental Update (O(n) time, O(1) space)
The optimized version tracks only two values: the current number of occupied chairs and the maximum observed occupancy. Traverse the event string once. Increment the current count for each entry event and decrement it for each exit event. After every increment, compare the value with the stored maximum and update if needed. This eliminates extra bookkeeping and keeps the logic tight: a single pass, constant memory, and only two integer updates per step. It works because the peak occupancy during the traversal directly determines the minimum chairs required.
Recommended for interviews: The incremental update approach is what most interviewers expect. It shows that you recognize the problem as a running maximum of concurrent users rather than a complex simulation. Implementing the direct simulation first demonstrates clear understanding, but the optimized version highlights strong problem decomposition and familiarity with linear scans in simulation and string processing tasks.
Approach 1: Approach 1: Simulate Each Event Using Two Counters
This approach uses two counters: one to track the current number of people in the waiting room, and another to track the maximum number of people encountered at any time. The maximum count is the answer because it represents the peak number of people needing chairs simultaneously.
Iterate through the string s, updating the current count based on whether a person enters or leaves. Update the maximum count tracked if the current count surpasses it.
In the C implementation, a loop traverses the input string. The current number of people in the waiting room is incremented or decremented based on who's entering ('E') or leaving ('L'). The variable maxChairs records the peak value the current variable achieves, which is the answer.
Complexity
Time Complexity: O(n), where n is the length of the string s. We process each character once.
Space Complexity: O(1), as we use a constant amount of extra space.
Approach 2: Approach 2: Optimized with Incremental Update
This approach optimizes the process to only update when necessary, maintaining a counter for current occupancy and the peak. The additional detail is that it may stop early if peak optimizations suffice based on constraints and input variations.
C solution adapts to calculating the increment or decrement inline with no explicit branches for a marginal performance gain. It uses boolean arithmetic to decide the increase/decrease of the occupancy counter.
Complexity
Time Complexity: O(n)
Space Complexity: O(1)
Approach 3: Simulation
We use a variable cnt to record the current number of chairs needed, and a variable left to record the current number of remaining empty chairs. We traverse the string s. If the current character is 'E', then if there are remaining empty chairs, we directly use one empty chair, otherwise we need to add a chair; if the current character is 'L', then the number of remaining empty chairs increases by one.
After the traversal, we return cnt.
The time complexity is O(n), where n is the length of the string s. The space complexity is O(1).
Code
Python
Java
C++
Go
TypeScript
Complexity Comparison
| Approach | Complexity |
|---|---|
| Approach 1: Simulate Each Event Using Two Counters | Time Complexity: O(n), where n is the length of the string Space Complexity: O(1), as we use a constant amount of extra space. |
| Approach 2: Optimized with Incremental Update | Time Complexity: O(n) Space Complexity: O(1) |
| Simulation | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Simulate Each Event Using Two Counters | O(n) | O(1) | Best when implementing the problem exactly as described for clarity or learning simulation patterns |
| Optimized Incremental Update | O(n) | O(1) | Preferred approach in interviews; minimal logic and directly tracks peak occupancy |
Video Solution
Day 45/100 |Learning DSA👨💻Que:[Leetcode3168:Min no of chairs in waiting room]#dsa #datastructure • HalfCoder • 2,431 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Minimum Number of Chairs in a Waiting Room easy or hard?
Minimum Number of Chairs in a Waiting Room Python/Java solution
How to solve Minimum Number of Chairs in a Waiting Room in O(n)?
What is the best approach for Minimum Number of Chairs in a Waiting Room?
Is Minimum Number of Chairs in a Waiting Room asked at Google/Amazon/Meta?
What data structure is used in Minimum Number of Chairs in a Waiting Room?
What is the time complexity of Minimum Number of Chairs in a Waiting Room?
Ready to solve this problem?
Practice Minimum Number of Chairs in a Waiting Room with our built-in code editor and test cases.
Practice on FleetCode