⚡Flashcard Drill➔
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

  1. Track the penalty incrementally rather than recomputing prefix and suffix counts.
  2. Start with the penalty of closing before hour 0: it equals the total number of 'Y'.
  3. Moving the closing hour past index i changes the penalty by -1 if customers[i] == 'Y' (one fewer 'Y' remains after) and +1 otherwise (one more 'N' is now included).
  4. 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 i instead of i + 1: the hour refers to the number of hours open, so closing after index i means hour i + 1.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔

🧩 Related Arrays & Hashing Problems