Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/1052.html

1052. Grumpy Bookstore Owner (Medium)

Today, the bookstore owner has a store open for customers.length minutes.  Every minute, some number of customers (customers[i]) enter the store, and all those customers leave after the end of that minute.

On some minutes, the bookstore owner is grumpy.  If the bookstore owner is grumpy on the i-th minute, grumpy[i] = 1, otherwise grumpy[i] = 0.  When the bookstore owner is grumpy, the customers of that minute are not satisfied, otherwise they are satisfied.

The bookstore owner knows a secret technique to keep themselves not grumpy for X minutes straight, but can only use it once.

Return the maximum number of customers that can be satisfied throughout the day.

 

Example 1:

Input: customers = [1,0,1,2,1,1,7,5], grumpy = [0,1,0,1,0,1,0,1], X = 3
Output: 16
Explanation: The bookstore owner keeps themselves not grumpy for the last 3 minutes. 
The maximum number of customers that can be satisfied = 1 + 1 + 1 + 1 + 7 + 5 = 16.

 

Note:

  • 1 <= X <= customers.length == grumpy.length <= 20000
  • 0 <= customers[i] <= 1000
  • 0 <= grumpy[i] <= 1

Related Topics:
Array, Sliding Window

Solution 1. Sliding Window

// OJ: https://leetcode.com/problems/grumpy-bookstore-owner/
// Time: O(N)
// Space: O(1)
class Solution {
public:
    int maxSatisfied(vector<int>& customers, vector<int>& grumpy, int X) {
        int ans = 0, sum = 0;
        for (int i = 0; i < customers.size(); ++i) sum += grumpy[i] == 0 ? customers[i] : 0;
        for (int i = 0; i < customers.size(); ++i) {
            if (grumpy[i] == 1) sum += customers[i];
            if (i >= X && grumpy[i - X] == 1) sum -= customers[i - X];
            if (i >= X - 1) ans = max(ans, sum);
        }
        return ans;
    }
};
  • class Solution {
        public int maxSatisfied(int[] customers, int[] grumpy, int X) {
            int satisfied = 0;
            int length = customers.length;
            for (int i = 0; i < length; i++) {
                if (grumpy[i] == 0)
                    satisfied += customers[i];
            }
            int unsatisfiedWindow = 0;
            for (int i = 0; i < X; i++) {
                if (grumpy[i] == 1)
                    unsatisfiedWindow += customers[i];
            }
            int maxUnsatisfiedWindow = unsatisfiedWindow;
            for (int i = X; i < length; i++) {
                int prevIndex = i - X;
                if (grumpy[prevIndex] == 1)
                    unsatisfiedWindow -= customers[prevIndex];
                if (grumpy[i] == 1)
                    unsatisfiedWindow += customers[i];
                maxUnsatisfiedWindow = Math.max(maxUnsatisfiedWindow, unsatisfiedWindow);
            }
            return satisfied + maxUnsatisfiedWindow;
        }
    }
    
    ############
    
    class Solution {
        public int maxSatisfied(int[] customers, int[] grumpy, int minutes) {
            int s = 0, cs = 0;
            int n = customers.length;
            for (int i = 0; i < n; ++i) {
                s += customers[i] * grumpy[i];
                cs += customers[i];
            }
            int t = 0, ans = 0;
            for (int i = 0; i < n; ++i) {
                t += customers[i] * grumpy[i];
                int j = i - minutes + 1;
                if (j >= 0) {
                    ans = Math.max(ans, cs - (s - t));
                    t -= customers[j] * grumpy[j];
                }
            }
            return ans;
        }
    }
    
  • // OJ: https://leetcode.com/problems/grumpy-bookstore-owner/
    // Time: O(N)
    // Space: O(1)
    class Solution {
    public:
        int maxSatisfied(vector<int>& customers, vector<int>& grumpy, int X) {
            int ans = 0, sum = 0;
            for (int i = 0; i < customers.size(); ++i) sum += grumpy[i] == 0 ? customers[i] : 0;
            for (int i = 0; i < customers.size(); ++i) {
                if (grumpy[i] == 1) sum += customers[i];
                if (i >= X && grumpy[i - X] == 1) sum -= customers[i - X];
                if (i >= X - 1) ans = max(ans, sum);
            }
            return ans;
        }
    };
    
  • class Solution:
        def maxSatisfied(
            self, customers: List[int], grumpy: List[int], minutes: int
        ) -> int:
            s = sum(a * b for a, b in zip(customers, grumpy))
            cs = sum(customers)
            t = ans = 0
            for i, (a, b) in enumerate(zip(customers, grumpy), 1):
                t += a * b
                if (j := i - minutes) >= 0:
                    ans = max(ans, cs - (s - t))
                    t -= customers[j] * grumpy[j]
            return ans
    
    ############
    
    # 1052. Grumpy Bookstore Owner
    # https://leetcode.com/problems/grumpy-bookstore-owner/
    
    class Solution:
        def maxSatisfied(self, customers: List[int], grumpy: List[int], minutes: int) -> int:
            n = len(customers)
            A = [i for i in range(n) if grumpy[i] == 1]
    
            res = customers[A[0]] if A else 0
            if A:
                curr, start = customers[A[0]], 0
                for index in A[1:]:
                    if index - A[start] < minutes:
                        curr += customers[index]
                    else:
                        while index - A[start] >= minutes:
                            curr -= customers[A[start]]
                            start += 1
                        curr += customers[index]
    
                    res = max(res, curr)
            
            return res + sum(customers[i] for i in range(n) if grumpy[i] == 0)
    
    
  • func maxSatisfied(customers []int, grumpy []int, minutes int) int {
    	s, cs := 0, 0
    	for i, c := range customers {
    		s += c * grumpy[i]
    		cs += c
    	}
    	t, ans := 0, 0
    	for i, c := range customers {
    		t += c * grumpy[i]
    		j := i - minutes + 1
    		if j >= 0 {
    			ans = max(ans, cs-(s-t))
    			t -= customers[j] * grumpy[j]
    		}
    	}
    	return ans
    }
    
    func max(a, b int) int {
    	if a > b {
    		return a
    	}
    	return b
    }
    
  • impl Solution {
        pub fn max_satisfied(customers: Vec<i32>, grumpy: Vec<i32>, minutes: i32) -> i32 {
            let k = minutes as usize;
            let n = customers.len();
    
            let mut sum = 0;
            for i in 0..k {
                if grumpy[i] == 1 {
                    sum += customers[i];
                }
            }
            let mut max = sum;
            for i in k..n {
                if grumpy[i - k] == 1 {
                    sum -= customers[i - k];
                }
                if grumpy[i] == 1 {
                    sum += customers[i];
                }
                max = max.max(sum);
            }
    
            sum = 0;
            for i in 0..n {
                if grumpy[i] == 0 {
                    sum += customers[i];
                }
            }
            sum + max
        }
    }
    
    

All Problems

All Solutions