leetcode 2483, minimum penalty for a shop

mail@pastecode.io avatar
unknown
c_cpp
a year ago
1.3 kB
9
Indexable
// 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;
    }
};