NeetCode #140LC-2483MediumArrays & Hashing
← Back to All Problems#140 · #2483 · Minimum Penalty for a Shop(商店的最少代价)
📌 Problem Statement & Constraints
A shop owner wants to choose an hour
i to close, so that the penalty is minimised. The penalty is the number of 'N' customers before or at hour i plus the number of 'Y' customers after hour i. Given the string customers, return the earliest hour that minimises the penalty. Constraints: 1 <= customers.length <= 10^5.💡 Core Algorithmic Approaches
- Track the penalty incrementally rather than recomputing prefix and suffix counts.
- Start with the penalty of closing before hour 0: it equals the total number of
'Y'. - Moving the closing hour past index
ichanges the penalty by-1ifcustomers[i] == 'Y'(one fewer'Y'remains after) and+1otherwise (one more'N'is now included). - Record the first index achieving the minimum, which gives the earliest hour on ties.
💻 Benchmark Python3 Implementation
class Solution:
def bestClosingTime(self, customers: str) -> int:
penalty = customers.count("Y") # penalty of closing before hour 0
best = penalty
res = 0
for i, ch in enumerate(customers):
penalty += -1 if ch == "Y" else 1 # moving the closing hour past i
if penalty < best: # strict '<' keeps the earliest hour
best = penalty
res = i + 1
return res⚡ Complexity Deep Dive
⏱️ Time Complexity
O(n): one pass after counting the Ys.
💾 Space Complexity
O(1): two counters.
⚠️ Interview Pitfalls & Follow-ups
- Using
<=when updating the best: that would keep the latest hour on ties, but the problem asks for the earliest. - Forgetting the initial state (closing before hour 0): it is a valid choice and must be considered.
- Recomputing prefix and suffix arrays for every candidate hour: O(n^2). The incremental update is O(1) per step.
- Returning the index
iinstead ofi + 1: the hour refers to the number of hours open, so closing after indeximeans houri + 1.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.