Teaching Kids Programming – Minimum Number of Chairs in the Room (Max Prefix Sum)

Teaching Kids Programming: Videos on Data Structures and Algorithms

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.

Hints:
Iterate from left to right over the string and keep track of the number of people in the waiting room using a variable that you will increment on every occurrence of ‘E’ and decrement on every occurrence of ‘L’.
The answer is the maximum number of people in the waiting room at any instance.

Minimum Number of Chairs in a Waiting Room

We can use a counter `current` to represent the number of the people in the room. When we have a “E”, we increment the counter, while we have a “L” we decrement it. And in the meantime, we maintain another counter `ans` which represents the min number of chairs required. This will be the max values of the `current` at all times.

1
2
3
4
5
6
7
8
9
10
11

class Solution:
    def minimumChairs(self, s: str) -> int:
        ans = 0
        cur = 0
        for i in s:
            if i == "E":
                cur += 1
                ans = max(cur, ans)
            else:
                cur -= 1
        return ans

class Solution:
    def minimumChairs(self, s: str) -> int:
        ans = 0
        cur = 0
        for i in s:
            if i == "E":
                cur += 1
                ans = max(cur, ans)
            else:
                cur -= 1
        return ans

The time complexity is O(N) where N is the size of the string. The space complexity is O(1) constant.

Calculate Prefix Sum (accumulate)

We can compute the prefix sum array, using the accumulate, and then get the maximum value. The time/space complexity is O(N). We need to compute and store the prefix sum in an array.

1
2
3

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

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

We convert the original string into a binary array like [1, 0, 1, 0, 0 ..] where 1 is “E” and 0 is “L”. Then the current counter (above) is the prefix sum equivalently.

–EOF (The Ultimate Computing & Technology Blog) —