# leetcode 2483, minimum penalty for a shop

unknown
c_cpp
a year ago
1.3 kB
9
Indexable
Never
```// AMAN JAIN MCA 1st YEAR 2nd SEM

// time O(N), space O(N)
// Approach: Prefix/Suffix Sum
class Solution {
public:
int bestClosingTime(string customers) {
int totalYes = 0, totalNo = 0, N = customers.size();
int prefixNoCustomer[N], suffixYesCustomer[N], earliestHour = 0, minPenalty = INT_MAX;
for(int i = 0; i < N; ++i) {
prefixNoCustomer[i] = totalNo;
totalNo = customers[i] == 'N' ? totalNo + 1 : totalNo;
suffixYesCustomer[N - i - 1] = totalYes;
totalYes = customers[N - i - 1] == 'Y' ? totalYes + 1 : totalYes;
}
for(int i = N - 1; i >= 0; --i) { // traverse in reverse because we want earliest hour
int currentPenalty = customers[i] == 'Y' ? 1 : 0;
int totalPenalty = prefixNoCustomer[i] + suffixYesCustomer[i] + currentPenalty;
if(totalPenalty <= minPenalty) {
minPenalty = totalPenalty;
earliestHour = i;
}
}
// if every index is 'Y', then the optimal approach is to
// keep the shop open all the time and close it at Nth hour.
// (totalNo < minPenalty ? N : earliestHour) handles that case
return totalNo < minPenalty ? N : earliestHour;
}
};```