Minimum Penalty for a Shop

Minimum Penalty for a Shop

What is this problem about?

The Minimum Penalty for a Shop problem gives you a string representing customer visits — 'Y' when a customer comes and 'N' when no one comes. You choose a closing hour, and the penalty is the number of customers who arrive when the shop is closed plus the number of empty hours when the shop is open. The Minimum Penalty for a Shop interview question asks you to find the closing hour that minimizes this penalty. It's a clean prefix sum problem dressed in a business scenario.

Why is this asked in interviews?

Microsoft, Stripe, Google, and Bloomberg ask this because it tests the ability to translate a word problem into an efficient algorithmic solution. Brute force O(n²) is obvious but too slow; the elegant O(n) solution using prefix sums is what distinguishes strong candidates. The string and prefix sum interview pattern is directly applicable here, and the problem rewards clear problem decomposition.

Algorithmic pattern used

The core pattern is prefix sum with sweep. Precompute:

• prefixY[i] = number of 'Y's in the first i hours (penalty for closing before those customers).
• suffixN[i] = number of 'N's from hour i to end (penalty for staying open during empty hours).

For each possible closing time h (0 to n), penalty = prefixY[h] + suffixN[h]. Sweep once to find the minimum. Total time: O(n).

Example explanation

Customer log: "YNYY". If you close at hour 0: penalty = 0 (no open time) + count('Y' missed) = 3. If you close at hour 2: penalty = count('N' in hours 0-1) + count('Y' after hour 2) = 1 + 2 = 3. If you close at hour 4 (stay all day): penalty = count('N' all day) = 1. Minimum penalty is 1 at closing hour 4.

Common mistakes candidates make

• Miscounting when the shop closes "at" vs "after" a given hour.
• Recomputing counts from scratch for each closing time instead of using prefix sums.
• Off-by-one in indexing the prefix array vs. the string characters.
• Not considering closing at hour 0 or hour n as valid options.

Interview preparation tip

This is a strong warm-up problem for prefix sum interview patterns. Practice writing the recurrence for prefix arrays cleanly before diving into code. The key shift in thinking is recognizing that "penalty at each time point" can be decomposed into two independent prefix computations. Problems like this appear disguised as scheduling, resource allocation, or traffic modeling scenarios — the underlying math is always a sweep-line or prefix sum.