Min Penalty Shop LeetCode 2483 Guide

LeetCode 2483 Minimum Penalty for a Shop gives you a string customers of length n where each character is either 'Y' (a customer arrives that hour) or 'N' (no customer arrives). The shop can close at any hour j from 0 to n inclusive, where j=0 means closing before any hour and j=n means staying open all day.

The penalty for closing at hour j is the number of 'N' characters in the first j characters (open hours with no customers — wasted time being open) plus the number of 'Y' characters in the remaining characters at positions j through n-1 (customers who arrive after closing — missed business).

Your goal is to find the earliest closing hour j that minimizes the total penalty. If multiple hours tie for the minimum penalty, return the smallest j.

The penalty at closing hour j decomposes naturally into two parts: the prefix penalty (N's in the open portion) and the suffix penalty (Y's in the closed portion). Formally, penalty(j) = countN(0, j-1) + countY(j, n-1). The total changes predictably as j slides from 0 to n.

At j=0 the shop closes immediately, so the prefix penalty is 0 (no open hours) and the suffix penalty equals the total number of Y's in the entire string — every customer is missed. This gives you the starting penalty for the scan.

As j moves right by one position, the character at the previous position (customers[j-1]) transitions from the suffix (closed portion) to the prefix (open portion). If that character is 'Y', it leaves the suffix (suffix penalty decreases by 1). If it is 'N', it enters the prefix (prefix penalty increases by 1). The net change per step is either -1 or +1.

The algorithm is a single left-to-right scan. Initialize penalty to the total count of Y's in the string (this is penalty at j=0). Initialize minPenalty to this value and bestJ to 0. Then iterate j from 0 to n-1, processing customers[j] at each step.

For each character: if customers[j] is 'Y', decrement penalty by 1 (this customer moves from the closed portion to the open portion — served instead of missed); if customers[j] is 'N', increment penalty by 1 (this hour moves from the closed portion to the open portion — wasted open time added). After updating, if penalty is strictly less than minPenalty, update minPenalty and bestJ to j+1.

The strict less-than comparison (not less-than-or-equal) ensures you capture the earliest j with the minimum penalty, which satisfies the problem's tiebreaking requirement. After the loop, return bestJ.

Moving the closing time right by one hour means that hour transitions from being in the closed portion to the open portion. If the hour had a customer (Y), being open for it is neutral — one Y leaves the suffix (missed-customer penalty drops by 1). If the hour had no customer (N), being open for it is bad — one N enters the prefix (wasted-time penalty rises by 1).

This is exactly a prefix sum of +1 for each N and -1 for each Y in the string. The running sum starting from 0 at j=0 gives the delta from the initial penalty. The minimum of the running sum over all j from 0 to n tells you the optimal closing time — the point where the accumulated Y-serving benefit is maximized relative to the N-wasting cost.

Because we initialized penalty to totalY (the absolute penalty at j=0) rather than tracking deltas, the running value is already the actual total penalty at each j. There is no offset to subtract. The algorithm is correct by construction.

Example: customers = "YYNY". Total Y's = 3, so initial penalty at j=0 is 3. bestJ = 0, minPenalty = 3. Now scan left to right.

j=0, customers[0]='Y': penalty = 3-1 = 2. Since 2 < 3, minPenalty = 2, bestJ = 1. j=1, customers[1]='Y': penalty = 2-1 = 1. Since 1 < 2, minPenalty = 1, bestJ = 2. j=2, customers[2]='N': penalty = 1+1 = 2. 2 is not < 1, no update. j=3, customers[3]='Y': penalty = 2-1 = 1. 1 is not < 1 (not strictly less), no update. bestJ stays at 2.

The answer is 2 — close after hour 1 (0-indexed). Verification: open hours are customers[0..1] = "YY" — 0 N's; closed hours are customers[2..3] = "NY" — 1 Y. Total penalty = 0 + 1 = 1. Correct. The tie at j=4 (penalty also 1) is correctly ignored because bestJ=2 was found first.

Python: totalY = customers.count('Y'); penalty = minPenalty = totalY; bestJ = 0; for j, c in enumerate(customers): penalty -= 1 if c == 'Y' else -1; if penalty < minPenalty: minPenalty = penalty; bestJ = j + 1; return bestJ. Time complexity O(n), space O(1). The count() call is O(n) and the loop is O(n) — total is O(n).

Java: int totalY = 0; for (char c : customers.toCharArray()) if (c == 'Y') totalY++; int penalty = totalY, minPenalty = totalY, bestJ = 0; for (int j = 0; j < customers.length(); j++) { if (customers.charAt(j) == 'Y') penalty--; else penalty++; if (penalty < minPenalty) { minPenalty = penalty; bestJ = j + 1; } } return bestJ. Identical logic, same O(n) time O(1) space.

Both implementations require exactly two passes over the string: one to count Y's (or one combined pass if you precompute the prefix Y count) and one sliding scan. An alternative single-pass approach precomputes totalY in a prefix array, but the two-pass version with count() is simpler and equally efficient.

Minimum Penalty for a Shop belongs to the prefix sum optimization family — problems where a sliding window or prefix accumulation reveals the optimal point in a single pass. Find Pivot Index (LeetCode 724) similarly finds a balance point where prefix sum equals suffix sum. Highest Altitude (LeetCode 1732) tracks the running maximum of a prefix sum. All three share the same O(n) time, O(1) space blueprint.

The penalty optimization pattern generalizes to any problem where a cost decomposes into a prefix contribution and a suffix contribution that each change by ±1 as a boundary slides. Minimum Cost to Make Array Equal (LeetCode 2448) and Minimum Number of Operations to Make Array Continuous use similar sliding decomposition ideas.

For interview preparation, recognize that any problem asking for an optimal split point where moving the split right changes the objective by a fixed amount is a candidate for this technique. Once you spot the +1/-1 change per step, the sliding scan with a tracked minimum writes itself.