Loading page…
Practice problem · medium
A chat app has a quick-chat button. A user taps it and picks how many people the chat should have, counting themselves. Users tap one after another.
As soon as enough waiting users have asked for the same size, those users are put into a chat and it starts. A user whose size never fills stays waiting and is not in any chat.
You report the chats in the order they started.
Write form_chats(sizes).
sizes[i] is the chat size requested by the user at position i. Users tap in order of position.s reaches s, those s users form a chat. Those users are no longer waiting, and the next user who asks for s starts a new group.Input: sizes = [2, 1, 2, 3, 3]
Output: [[1], [0, 2]]The trace keeps, for each size, the list of waiting users who asked for it. When a list reaches its own size, it becomes a chat and is cleared.
| j | Size asked | Waiting for that size | Chat started |
|---|---|---|---|
| 0 | 2 | [0] | none |
| 1 | 1 | [1] | [1] (a chat of 1 is full at once) |
| 2 | 2 | [0, 2] | [0, 2] |
| 3 | 3 | [3] | none |
| 4 | 3 | [3, 4] | none |
Users 3 and 4 wanted a chat of 3 and only two of them arrived, so they stay waiting and are left out.
Input: sizes = [2, 2, 2, 2, 2]
Output: [[0, 1], [2, 3]]Users 0 and 1 form a chat. The list is cleared, so users 2 and 3 form the next chat. User 4 waits alone.
Input: sizes = [3, 1, 3, 3, 1]
Output: [[1], [0, 2, 3], [4]]The chat of one at position 1 starts first. The chat of three with users 0, 2 and 3 starts when user 3 taps. User 4 then starts a chat of one.
1 ≤ sizes.length ≤ 100,000 (users in one session)1 ≤ sizes[i] ≤ 100,000 (requested chat size)Looking back over all earlier users each time a user taps costs about n × n / 2 steps. At n = 100,000 that is about 5 × 10^9, far over the budget of about 10^8 simple steps a second. A map from each size to its waiting list finds the right group in one step, so one pass costs about n steps. The sizes go up to 100,000, so the map is the natural table: most sizes never appear.
form_chats · runs in your browserCoding is easiest on a laptop. On a phone, read, trace and try small edits.