Scale Engineer

Minimum Number of Chairs in a Waiting Room

Easy
#2814Time: O(N^2), where N is the length of the string `s`. The outer loop runs up to N+1 times, and the inner simulation loop also runs up to N times.Space: O(1), as we only use a few variables to keep track of the state during simulation.1 company
Data structures
String
Companies
Expedia

Prompt

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 <= 50
  • s consists only of the letters 'E' and 'L'.
  • s represents a valid sequence of entries and exits.

Approaches

2 approaches with complexity analysis and trade-offs.

This approach involves testing every possible number of chairs, from 0 up to the total number of events. For each potential number of chairs, we simulate the entire sequence of events to see if that number is sufficient. The first number of chairs that successfully accommodates everyone is the minimum required.

Algorithm

  • Iterate through the number of chairs k from 0 to s.length().
  • For each k, start a simulation:
    • Initialize currentPeople = 0.
    • Set a flag isSufficient = true.
    • Iterate through each event c in the string s.
    • If c == 'E', increment currentPeople.
    • If c == 'L', decrement currentPeople.
    • If currentPeople > k at any point, this k is not enough. Set isSufficient = false and break the inner loop.
  • If the simulation completes and isSufficient is still true, then k is the minimum number of chairs required. Return k.

Walkthrough

We can determine the minimum number of chairs by trying out each possible value, let's call it k, starting from 0. The maximum possible number of chairs we could ever need is the length of the string s, which happens if every event is an entry ('E').

For each k, we simulate the process by maintaining a counter for the currentPeople in the room. If at any point currentPeople exceeds k, it means k chairs are not enough, so we stop this simulation and try the next value, k+1. If we successfully process the entire string s without currentPeople ever exceeding k, it means k chairs are sufficient. Since we are checking k in increasing order, the first k that works is our answer.

class Solution {    public int minimumChairs(String s) {        int n = s.length();        for (int k = 0; k <= n; k++) { // Test if k chairs are sufficient            int currentPeople = 0;            boolean possible = true;            for (char event : s.toCharArray()) {                if (event == 'E') {                    currentPeople++;                } else {                    currentPeople--;                }                if (currentPeople > k) {                    possible = false;                    break;                }            }            if (possible) {                return k; // Found the minimum k            }        }        return n; // Fallback, though a solution should always be found earlier    }}

Complexity

Time

O(N^2), where N is the length of the string `s`. The outer loop runs up to N+1 times, and the inner simulation loop also runs up to N times.

Space

O(1), as we only use a few variables to keep track of the state during simulation.

Trade-offs

Pros

  • Conceptually simple and easy to understand.

  • Directly models the problem statement of finding the minimum k such that a condition holds.

Cons

  • Inefficient due to nested loops, leading to a quadratic time complexity.

  • Performs redundant calculations by re-simulating the event sequence for each potential answer.

Solutions

class Solution:    def minimumChairs(self, s: str) -> int: cnt = left = 0 for c in s: if c == "E": if left: left -= 1 else: cnt += 1 else: left += 1 return cnt

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem