array and hashmap greedy December 28, 2022

Minimum penalty for a shop

Time O(n) Space O(1) Open original problem

We will count the number of penaly and then iterate over the customers, canculate the minimum penalty for each customer and add it to the total penalty.

class Solution:
    def bestClosingTime(self, customers: str) -> int:
        n = len(customers)
        penalty = customers.count('Y')

        if penalty == n: 
            return n

        minPenalty, res = n, 0
        for idx, value in enumerate(customers):
            if minPenalty > penalty:
                minPenalty = penalty
                res = idx
            if value == 'Y':
                penalty -= 1
            else:
                penalty += 1

        if minPenalty > penalty: 
            return n

        return res

Time complexity: O(n)
Space complexity: O(1)