4116. Assign Umbrella on Rainy Days
DifficultyEasy
Description
You are given a binary array rain of length n, where rain[i] == 1 means it rains on day i, and rain[i] == 0 means it does not.
Alice and Bob share a single umbrella over these n days. On each day i:
- Alice needs the umbrella on day
iifrain[i] == rain[i + 1] == 1for0 <= i < n - 1. - Bob needs the umbrella if
rain[i] == 1. - At most one of them can receive the umbrella.
- If only one person needs it, that person receives it.
- If both need it, it goes to whoever has received it fewer times so far. If they are tied, it goes to Alice.
- If neither needs it, no one receives it.
A person's count increases only on a day they receive the umbrella. Initially, both counts are 0.
Return a string array answer of length n, where answer[i] is "Alice", "Bob", or "None", denoting who receives the umbrella on day i.
A binary array is an array that contains only 0 and 1.
Example 1:
Input: rain = [1,1,0,1,1]
Output: ["Alice","Bob","None","Alice","Bob"]
Explanation:
- Day 0:
rain[0] == 1andrain[1] == 1, so both need it. Counts are tied, so Alice receives it. - Day 1:
rain[1] == 1, so Bob needs it, butrain[2] == 0, so Alice does not need it. Therefore Bob receives it. - Day 2: No rain, so no one receives it.
- Day 3:
rain[3] == 1andrain[4] == 1, so both need it. Counts are tied at 1, so Alice receives it. - Day 4: Last day, so only Bob needs it, and he receives it.
- Therefore,
answer = ["Alice", "Bob", "None", "Alice", "Bob"].
Example 2:
Input: rain = [0,1,0,1]
Output: ["None","Bob","None","Bob"]
Explanation:
- It never rains on two consecutive days, so Alice never needs the umbrella.
- Bob receives it on days 1 and 3, and no one receives it on days 0 and 2.
- Therefore,
answer = ["None", "Bob", "None", "Bob"].
Constraints:
1 <= n == rain.length <= 100rain[i]is either 0 or 1.
Solutions
Solution 1: Simulation
Thinking
\(n\) is at most \(100\), so the owner of the umbrella can be decided day by day. A count increases only when that person actually receives the umbrella, and a tie is broken by the counts so far, so the days must be scanned from left to right.
Alice needs the umbrella exactly when the current day and the next day both rain. The current day is already rainy, so Bob needs it too, and Alice never needs it by herself.
The counters \(a\) and \(b\) are enough. The decision uses the counts before either one increases, and whether the next day rains decides if Alice enters that comparison.
Let \(a\) and \(b\) be the number of times Alice and Bob have already received the umbrella. Both start at \(0\). Scan \(\textit{rain}\) from left to right.
On day \(i\), \(\textit{rain}[i]=0\) means nobody needs the umbrella, and the answer is \(\text{None}\). If \(\textit{rain}[i]=1\), Bob needs it. Alice also needs it when \(i<n-1\) and \(\textit{rain}[i+1]=1\). Then Alice receives it when \(a\le b\), and \(a\) increases by one; otherwise Bob receives it, and \(b\) increases by one. If the next day is dry, or day \(i\) is the last day, only Bob needs the umbrella, so that same branch records Bob.
The time complexity is \(O(n)\), and the space complexity is \(O(1)\).
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 | |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 | |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 | |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 | |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 | |