Minimum Number of Chairs in a Waiting Room solution and explanation
9 more videos on this problem
Day 45/100 |Learning DSA👨💻Que:[Leetcode3168:Min no of chairs in waiting room]#dsa #datastructureHalfCoder · 0:12 · 2K views
3168. Minimum Number of Chairs in a Waiting Room (Leetcode Easy)Programming Live with Larry · 2:56 · 340 views
3168. Minimum Number of Chairs in a Waiting Room | LeetCode Weekly #400 | Easy | DSAso-um-ya · 4:34 · 255 views
Minimum Number of Chairs in a Waiting Room | LeetCode weekly-contest-400Developer Coder · 3:10 · 246 views
LeetCode 3168 | Minimum Number of Chairs in a Waiting Room | Easy | Weekly Contest 400 | JavaAlgo Horizon · 2:50 · 187 views
100307 Minimum Number of Chairs in a Waiting Room | leetcode || contest 400 || solved ||Ssquare · 1:12 · 177 views
Leetcode 3168 | Minimum Number of Chairs in a Waiting Room | Detailed Explanation and Solution ✅✅✅ErDelhiBoy · 8:09 · 169 views
3168. Minimum Number of Chairs in a Waiting Room | Weekly Contest 400 - 1st Problem | SimulationTech Courses · 3:19 · 161 views
Lesson 623/№3168. Minimum Number of Chairs in a Waiting Room / LeetcodeYersham · 10:24 · 134 views
3168. Minimum Number of Chairs in a Waiting Room | Easy | LeetCode | Array | StringLeet's Code · 5:45 · 124 views
The problem
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.
def minChairs(s):
current = maxChairs = 0
for c in s:
if c == 'E':
current += 1
maxChairs = max(maxChairs, current)
elif c == 'L':
current -= 1
return maxChairs
s = "ELELEEL"
print(minChairs(s))public class Main {
public static int minChairs(String s) {
int current = 0, maxChairs = 0;
for (char c : s.toCharArray()) {
if (c == 'E') {
current++;
maxChairs = Math.max(maxChairs, current);
} else if (c == 'L') {
current--;
}
}
return maxChairs;
}
public static void main(String[] args) {
String s = "ELELEEL";
System.out.println(minChairs(s));
}
}#include <iostream>
#include <string>
using namespace std;
int minChairs(string s) {
int current = 0, maxChairs = 0;
for (char c : s) {
if (c == 'E') {
current++;
maxChairs = max(maxChairs, current);
} else if (c == 'L') {
current--;
}
}
return maxChairs;
}
int main() {
string s = "ELELEEL";
cout << minChairs(s) << endl;
return 0;
}function minChairs(s) {
let current = 0, maxChairs = 0;
for (let c of s) {
if (c === 'E') {
current++;
maxChairs = Math.max(maxChairs, current);
} else if (c === 'L') {
current--;
}
}
return maxChairs;
}
const s = "ELELEEL";
console.log(minChairs(s));#include <stdio.h>
#include <string.h>
int minChairs(char* s) {
int current = 0, maxChairs = 0;
int len = strlen(s);
for (int i = 0; i < len; i++) {
if (s[i] == 'E') {
current++;
if (current > maxChairs) {
maxChairs = current;
}
} else if (s[i] == 'L') {
current--;
}
}
return maxChairs;
}
int main() {
char s[] = "ELELEEL";
printf("%d\n", minChairs(s));
return 0;
}using System;
class Program {
public static int MinChairs(string s) {
int current = 0, maxChairs = 0;
foreach (char c in s) {
if (c == 'E') {
current++;
maxChairs = Math.Max(maxChairs, current);
} else if (c == 'L') {
current--;
}
}
return maxChairs;
}
static void Main() {
string s = "ELELEEL";
Console.WriteLine(MinChairs(s));
}
}The Python code maintains a running count of room occupants and stores the maximum faced at any time. Utilizing Python's in-built max(), we update the maximum chair tally required.
Time Complexity: O(n)
Space Complexity: O(1)
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.
def minChairs(s):
current = maxChairs = 0
for c in s:
current += 1 if c == 'E' else -1
maxChairs = max(maxChairs, current)
return maxChairs
s = "ELELEEL"
print(minChairs(s))public class Main {
public static int minChairs(String s) {
int current = 0, maxChairs = 0;
for (int i = 0; i < s.length(); i++) {
current += (s.charAt(i) == 'E' ? 1 : -1);
maxChairs = Math.max(maxChairs, current);
}
return maxChairs;
}
public static void main(String[] args) {
String s = "ELELEEL";
System.out.println(minChairs(s));
}
}#include <iostream>
#include <string>
using namespace std;
int minChairs(string s) {
int current = 0, maxChairs = 0;
for (char c : s) {
current += (c == 'E') - (c == 'L');
maxChairs = max(maxChairs, current);
}
return maxChairs;
}
int main() {
string s = "ELELEEL";
cout << minChairs(s) << endl;
return 0;
}function minChairs(s) {
let current = 0, maxChairs = 0;
for (let i = 0; i < s.length; i++) {
current += s[i] === 'E' ? 1 : -1;
maxChairs = Math.max(maxChairs, current);
}
return maxChairs;
}
const s = "ELELEEL";
console.log(minChairs(s));#include <stdio.h>
#include <string.h>
int minChairs(char* s) {
int current = 0, maxChairs = 0;
for (int i = 0; s[i] != '\0'; i++) {
current += (s[i] == 'E') - (s[i] == 'L');
if (current > maxChairs) {
maxChairs = current;
}
}
return maxChairs;
}
int main() {
char s[] = "ELELEEL";
printf("%d\n", minChairs(s));
return 0;
}using System;
class Program {
public static int MinChairs(string s) {
int current = 0, maxChairs = 0;
for (int i = 0; i < s.Length; i++) {
current += s[i] == 'E' ? 1 : -1;
maxChairs = Math.Max(maxChairs, current);
}
return maxChairs;
}
static void Main() {
string s = "ELELEEL";
Console.WriteLine(MinChairs(s));
}
}Python keeps things succinct, using inline conditional checking via the else clause to adjust "current" on the fly, bolstered by max() keeps track of high-points.
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).
function minimumChairs(s: string): number {
let [cnt, left] = [0, 0];
for (const c of s) {
if (c === 'E') {
if (left > 0) {
--left;
} else {
++cnt;
}
} else {
++left;
}
}
return cnt;
}func minimumChairs(s string) int {
cnt, left := 0, 0
for _, c := range s {
if c == 'E' {
if left > 0 {
left--
} else {
cnt++
}
} else {
left++
}
}
return cnt
}Complexity comparison
| Approach | Complexity |
|---|---|
| Approach 1: Simulate Each Event Using Two Counters | Time Complexity: O(n) Space Complexity: O(1) |
| Approach 2: Optimized with Incremental Update | Time Complexity: O(n) Space Complexity: O(1) |
| Simulation | – |
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 |
Frequently asked questions
Is Minimum Number of Chairs in a Waiting Room easy or hard?
Minimum Number of Chairs in a Waiting Room is classified as an Easy problem. The core idea is recognizing that the answer equals the peak number of people simultaneously present, which can be computed with a simple linear scan.
Minimum Number of Chairs in a Waiting Room Python/Java solution
In both Python and Java, iterate through the string and maintain two variables: current_people and max_chairs. Update current_people based on the event character and update max_chairs whenever the current count increases. The logic is identical across languages and runs in O(n) time with constant space.
How to solve Minimum Number of Chairs in a Waiting Room in O(n)?
Traverse the event string and maintain a running count of people currently in the waiting room. Increase the count when a person enters and decrease it when someone leaves. Track the maximum value reached during this scan. That maximum represents the minimum number of chairs required.
What is the best approach for Minimum Number of Chairs in a Waiting Room?
The best approach is a single-pass simulation that tracks the current number of people in the room and the maximum occupancy observed. Increment the counter when someone enters and decrement when someone leaves. The highest value reached during traversal represents the minimum number of chairs needed. This runs in O(n) time and O(1) space.
Is Minimum Number of Chairs in a Waiting Room asked at Google/Amazon/Meta?
This style of problem appears frequently in interviews at companies like Amazon, Google, and Meta because it tests event simulation and tracking concurrent counts. Variants also appear in problems involving meeting rooms, peak load tracking, and concurrency analysis.
What data structure is used in Minimum Number of Chairs in a Waiting Room?
The solution primarily uses simple integer counters while scanning a string. No complex data structure is required because the problem reduces to tracking a running total and the maximum value during iteration.
What is the time complexity of Minimum Number of Chairs in a Waiting Room?
The optimal solution runs in O(n) time because the event string is scanned exactly once. Each character triggers a constant-time update to the current occupancy counter. Space complexity is O(1) since only a few integer variables are required.