Minimum Number of Chairs in a Waiting Room

Minimum Number of Chairs in a Waiting Room - Problem

String Simulation Easy

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.

Input & Output

Example 1 — Basic Mixed Events

$ Input: s = "EELELL"

› Output: 2

💡 Note: Events: Enter, Enter (2 chairs), Leave (1 chair), Enter (2 chairs), Leave, Leave (0 chairs). Maximum chairs needed: 2

Example 2 — Only Entries

$ Input: s = "EEE"

› Output: 3

💡 Note: Three people enter consecutively with no one leaving. Need 3 chairs total.

Example 3 — Alternating Pattern

$ Input: s = "ELEL"

› Output: 1

💡 Note: Enter (1 chair), Leave (0 chairs), Enter (1 chair), Leave (0 chairs). Only 1 chair needed maximum.

Constraints

1 ≤ s.length ≤ 50
s consists only of uppercase English letters 'E' and 'L'
s represents a valid sequence of events

Visualization

Tap to expand

Understanding the Visualization

Input Events

String of E (enter) and L (leave) events

Track Occupancy

Maintain current count and maximum seen

Peak Value

Return the maximum occupancy encountered

Key Takeaway

🎯 Key Insight: The minimum chairs needed equals the maximum number of people present simultaneously

Asked in

a Amazon 15 G Google 12

The key insight is to track the current occupancy and remember the peak. We simulate the events by incrementing a counter for each entry and decrementing for each exit, keeping track of the maximum value seen. Time: O(n), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Simulation with Current Count	O(n)	O(1)	Track current occupancy and maximum chairs needed in one pass
Single Pass with Counter	O(n)	O(1)	Optimized approach using running counter to track occupancy

Simulation with Current Count — Algorithm Steps

Initialize current count = 0 and max count = 0
For each character: if 'E' increment current, if 'L' decrement current
Update max count whenever current count increases
Return max count

Visualization

Tap to expand

Step-by-Step Walkthrough

Initialize

Start with current=0, max=0

Process Events

For each E: increment current, update max. For each L: decrement current

Result

Return the maximum occupancy seen

Code -

solution.c — C

#include <stdio.h>
#include <string.h>

int solution(char* s) {
    int currentChairs = 0;
    int maxChairs = 0;
    int len = strlen(s);
    
    for (int i = 0; i < len; i++) {
        if (s[i] == 'E') {
            currentChairs++;
            if (currentChairs > maxChairs) {
                maxChairs = currentChairs;
            }
        } else if (s[i] == 'L') {
            currentChairs--;
        }
    }
    
    return maxChairs;
}

int main() {
    char s[1001];
    fgets(s, sizeof(s), stdin);
    s[strcspn(s, "\n")] = 0;
    
    int result = solution(s);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Single pass through the string of length n

✓ Linear Growth

Space Complexity

O(1)

Only using two integer variables regardless of input size

✓ Linear Space

30.3K Views

Medium Frequency

~8 min Avg. Time

890 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Simulation with Current Count — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler