LeetCode Entry
1052. Grumpy Bookstore Owner
Max customers sum after make consecutive minutes non-grumpy window
1052. Grumpy Bookstore Owner medium
blog post
substack
youtube
Join me on Telegram
https://t.me/leetcode_daily_unstoppable/646
Problem TLDR
Max customers sum after make consecutive minutes non-grumpy #medium #sliding_window
Intuition
It was hard.
First understand the problem: we can take all the 0-grumpy minutes, but 1-grumpy can only be in minutes, and must be choosen.
Let’s explore the example:
// 1 2 3 4 5 6 7 8 9 m=2
// 1 1 0 1 1 0 1 1 1
// * * * * * *
// * *
//
// 2 4 1 4 1 m=2
// 1 0 1 0 1
// * *
// * *
The sliding window must be from the 1-grumpy days to choose the maximum and ignore all 0-grumpy days, because they are always be taken.
Approach
Keep 0-grumpy and 1 grumpy sums in separate variables.
Complexity
-
Time complexity: \(O(n)\)
-
Space complexity: \(O(1)\)
Code
fun maxSatisfied(customers: IntArray, grumpy: IntArray, minutes: Int): Int {
var sum = 0; var max = 0; var other = 0; var j = 0
for ((i, c) in customers.withIndex()) {
sum += c * grumpy[i]
other += c * (1 - grumpy[i])
while (j <= i - minutes) sum -= customers[j] * grumpy[j++]
max = max(max, sum)
}
return max + other
}
pub fn max_satisfied(customers: Vec<i32>, grumpy: Vec<i32>, minutes: i32) -> i32 {
let (mut j, mut sum, mut other, mut max) = (0, 0, 0, 0);
for i in 0..grumpy.len() {
other += customers[i] * (1 - grumpy[i]);
sum += customers[i] * grumpy[i];
while j as i32 <= i as i32 - minutes { sum -= customers[j] * grumpy[j]; j += 1 }
max = max.max(sum)
}; max + other
}