Grumpy Bookstore Owner LeetCode solution in C++

1
/*
2
    https://leetcode.com/problems/grumpy-bookstore-owner/
3

4
    TC: O(N)
5
    SC: O(1)
6

7
    Looking at the problem, main thing to find is the window where the minutes
8
   should be used so that the owner is not grumpy and max customers in that
9
   window can be satisifed.
10

11
    Find the window with most no. of satisfied customers given the owner was
12
   originally grumpy but now has become not grumpy. Since the owner can only be
13
   not grumpy for minutes duration, this sets our window size as well. So with
14
   'minutes' window size, find the max window.
15

16
    Then add the max window value with the normal satisfied customers.
17
*/
18
class Solution {
19
 public:
20
  int maxSatisfied(vector<int> &customers, vector<int> &grumpy, int minutes) {
21
    // Tracks the max window where being not grumpy will add most customers and
22
    // current grumpy window customers
23
    int max_grumpy_window = 0, grumpy_window = 0;
24
    int curr = 0, n = customers.size();
25
    // Total satisifed customers when owner is not grumpy
26
    int satisfied_cx = 0;
27
    // net effective duration of not being grumpy
28
    minutes = min(minutes, n);
29

30
    // process the 1st window
31
    while (curr < minutes) {
32
      satisfied_cx += (!grumpy[curr] ? customers[curr] : 0);
33
      grumpy_window += (grumpy[curr] ? customers[curr] : 0);
34
      ++curr;
35
    }
36

37
    max_grumpy_window = max(max_grumpy_window, grumpy_window);
38
    // process the remaining windows
39
    while (curr < n) {
40
      // Remove the 1st element of last window
41
      grumpy_window -= (grumpy[curr - minutes] ? customers[curr - minutes] : 0);
42
      // Add the latest element of current window
43
      grumpy_window += (grumpy[curr] ? customers[curr] : 0);
44
      max_grumpy_window = max(max_grumpy_window, grumpy_window);
45

46
      satisfied_cx += (!grumpy[curr] ? customers[curr] : 0);
47
      ++curr;
48
    }
49

50
    return satisfied_cx + max_grumpy_window;
51
  }
52
};