Minimum Penalty for a Shop solution and explanation
Google
9 more videos on this problem
Minimum Penalty for a Shop - Leetcode 2483 - PythonNeetCodeIO · 14:58 · 12K views
Minimum Penalty for a Shop | MULTIPLE APPROACHES | Dry Run | Leetcode 2483 | codestorywithMIKcodestorywithMIK · 55:28 · 9K views
Minimum Penalty for a Shop II Prefix Sums II Suffix Sums II Leetcode 2483Aryan Mittal · 16:47 · 2K views
Minimum Penalty for a Shop - Python - Leetcode 2483CheatCode Ninja · 6:55 · 900 views
Minimum Penalty for a Shop - Leetcode 2483 - PythonTechError · 5:21 · 801 views
Minimum Penalty for a Shop | Prefix Sum | Single Parse | Leetcode 2483Techdose · 29:49 · 690 views
Daily Leetcode #2096: Dec 26, 2025 - 2483. Minimum Penalty for a ShopProgramming Live with Larry · 8:00 · 597 views
Minimum Penalty for a Shop 🔥 | LeetCode 2483 | Prefix Sum + Greedy | Optimal Solution Study Placement · 17:09 · 581 views
2483. Minimum Penalty for a Shop (Leetcode Medium)Programming Live with Larry · 15:06 · 558 views
2483. Minimum Penalty for a Shop | Leetcode Daily - PythonLeetcode Daily · 8:23 · 453 views
The problem
You are given the customer visit log of a shop represented by a 0-indexed string customers consisting only of characters 'N' and 'Y':
- if the
ithcharacter is'Y', it means that customers come at theithhour - whereas
'N'indicates that no customers come at theithhour.
If the shop closes at the jth hour (0 <= j <= n), the penalty is calculated as follows:
- For every hour when the shop is open and no customers come, the penalty increases by
1. - For every hour when the shop is closed and customers come, the penalty increases by
1.
Return the earliest hour at which the shop must be closed to incur a minimum penalty.
Note that if a shop closes at the jth hour, it means the shop is closed at the hour j.
Example 1:
Input: customers = "YYNY" Output: 2 Explanation: - Closing the shop at the 0th hour incurs in 1+1+0+1 = 3 penalty. - Closing the shop at the 1st hour incurs in 0+1+0+1 = 2 penalty. - Closing the shop at the 2nd hour incurs in 0+0+0+1 = 1 penalty. - Closing the shop at the 3rd hour incurs in 0+0+1+1 = 2 penalty. - Closing the shop at the 4th hour incurs in 0+0+1+0 = 1 penalty. Closing the shop at 2nd or 4th hour gives a minimum penalty. Since 2 is earlier, the optimal closing time is 2.
Example 2:
Input: customers = "NNNNN" Output: 0 Explanation: It is best to close the shop at the 0th hour as no customers arrive.
Example 3:
Input: customers = "YYYY" Output: 4 Explanation: It is best to close the shop at the 4th hour as customers arrive at each hour.
Constraints:
1 <= customers.length <= 105customersconsists only of characters'Y'and'N'.
Approach overview
Problem Overview: You receive a customers string where 'Y' means a customer arrives that hour and 'N' means no one comes. If the shop stays open during an 'N', you incur a penalty. If the shop is closed during a 'Y', you also incur a penalty. The task is to choose the closing hour that produces the minimum total penalty.
Approach 1: Brute Force Simulation (O(n²) time, O(1) space)
Check every possible closing hour from 0 to n. For each candidate closing time, iterate through the string and compute the penalty: count 'N' while the shop is open and 'Y' while it is closed. This approach directly follows the problem definition but repeatedly scans the string for every hour. The nested iteration results in quadratic time, which becomes inefficient for large inputs.
Approach 2: Cumulative Sum / Prefix Penalty (O(n) time, O(n) space)
Precompute penalties using the idea of prefix sum. Build a prefix array that counts how many 'N' occur while the shop is open up to hour i. Build another suffix-like count for how many 'Y' occur after the closing hour. The penalty for closing at hour i becomes prefixN[i] + suffixY[i]. Iterate once to compute these values and track the minimum penalty and its earliest index. This converts repeated counting into constant-time lookups.
Approach 3: Sliding Window Penalty Tracking (O(n) time, O(1) space)
You can avoid extra arrays by updating the penalty dynamically while scanning the string. Start with the assumption that the shop closes at hour 0, meaning every 'Y' causes a penalty. While iterating from left to right, update the penalty: encountering 'Y' decreases penalty (the shop staying open avoids that penalty), while encountering 'N' increases penalty (open with no customers). Track the minimum penalty seen so far and the corresponding hour. This effectively behaves like a running prefix difference and is the most space‑efficient solution.
Recommended for interviews: The sliding window or cumulative prefix method is what interviewers typically expect. The brute force version demonstrates that you understand the penalty definition, but the optimized O(n) approach shows you recognize the prefix sum pattern and can convert repeated counting into incremental updates.
Approach 1: Cumulative Sum Approach
This approach involves preprocessing the input string to obtain counts of 'Y' before each hour and 'N' from each hour to the end. This allows us to quickly calculate the penalty for closing the shop at any given hour.
def minimum_penalty(customers):
n = len(customers)
y_prefix = [0] * (n + 1)
n_suffix = [0] * (n + 1)
for i in range(n):
y_prefix[i + 1] = y_prefix[i] + (1 if customers[i] == 'Y' else 0)
for i in range(n - 1, -1, -1):
n_suffix[i] = n_suffix[i + 1] + (1 if customers[i] == 'N' else 0)
min_penalty = n
min_hour = 0
for j in range(n + 1):
penalty = y_prefix[j] + n_suffix[j]
if penalty < min_penalty:
min_penalty = penalty
min_hour = j
return min_hour
# Example usage:
customers = "YYNY"
result = minimum_penalty(customers)
print(result) # Output: 2public class Main {
public static int minimumPenalty(String customers) {
int n = customers.length();
int[] y_prefix = new int[n + 1];
int[] n_suffix = new int[n + 1];
for (int i = 0; i < n; ++i) {
y_prefix[i + 1] = y_prefix[i] + (customers.charAt(i) == 'Y' ? 1 : 0);
}
for (int i = n - 1; i >= 0; --i) {
n_suffix[i] = n_suffix[i + 1] + (customers.charAt(i) == 'N' ? 1 : 0);
}
int min_penalty = n, min_hour = 0;
for (int j = 0; j <= n; ++j) {
int penalty = y_prefix[j] + n_suffix[j];
if (penalty < min_penalty) {
min_penalty = penalty;
min_hour = j;
}
}
return min_hour;
}
public static void main(String[] args) {
String customers = "YYNY";
int result = minimumPenalty(customers);
System.out.println(result);
}
}#include <iostream>
#include <vector>
using namespace std;
int minimumPenalty(string customers) {
int n = customers.size();
vector<int> y_prefix(n + 1, 0), n_suffix(n + 1, 0);
for (int i = 0; i < n; ++i) {
y_prefix[i + 1] = y_prefix[i] + (customers[i] == 'Y');
}
for (int i = n - 1; i >= 0; --i) {
n_suffix[i] = n_suffix[i + 1] + (customers[i] == 'N');
}
int min_penalty = n, min_hour = 0;
for (int j = 0; j <= n; ++j) {
int penalty = y_prefix[j] + n_suffix[j];
if (penalty < min_penalty) {
min_penalty = penalty;
min_hour = j;
}
}
return min_hour;
}
int main() {
string customers = "YYNY";
int result = minimumPenalty(customers);
cout << result << endl;
return 0;
}function minimumPenalty(customers) {
const n = customers.length;
const yPrefix = new Array(n + 1).fill(0);
const nSuffix = new Array(n + 1).fill(0);
for (let i = 0; i < n; i++) {
yPrefix[i + 1] = yPrefix[i] + (customers[i] === 'Y' ? 1 : 0);
}
for (let i = n - 1; i >= 0; i--) {
nSuffix[i] = nSuffix[i + 1] + (customers[i] === 'N' ? 1 : 0);
}
let minPenalty = n;
let minHour = 0;
for (let j = 0; j <= n; j++) {
const penalty = yPrefix[j] + nSuffix[j];
if (penalty < minPenalty) {
minPenalty = penalty;
minHour = j;
}
}
return minHour;
}
// Example usage
const customers = "YYNY";
console.log(minimumPenalty(customers)); // Output: 2#include <stdio.h>
#include <string.h>
int minimumPenalty(char* customers) {
int n = strlen(customers);
int penalty = 0, min_penalty = n, min_hour = 0;
int y_prefix[n+1];
int n_suffix[n+1];
y_prefix[0] = 0;
for (int i = 0; i < n; i++) {
y_prefix[i+1] = y_prefix[i] + (customers[i] == 'Y');
}
n_suffix[n] = 0;
for (int i = n - 1; i >= 0; i--) {
n_suffix[i] = n_suffix[i+1] + (customers[i] == 'N');
}
for (int j = 0; j <= n; j++) {
penalty = y_prefix[j] + n_suffix[j];
if (penalty < min_penalty) {
min_penalty = penalty;
min_hour = j;
}
}
return min_hour;
}
int main() {
char customers[] = "YYNY";
int result = minimumPenalty(customers);
printf("%d\n", result);
return 0;
}using System;
class Program {
public static int MinimumPenalty(string customers) {
int n = customers.Length;
int[] yPrefix = new int[n + 1];
int[] nSuffix = new int[n + 1];
for (int i = 0; i < n; i++) {
yPrefix[i + 1] = yPrefix[i] + (customers[i] == 'Y' ? 1 : 0);
}
for (int i = n - 1; i >= 0; i--) {
nSuffix[i] = nSuffix[i + 1] + (customers[i] == 'N' ? 1 : 0);
}
int minPenalty = n;
int minHour = 0;
for (int j = 0; j <= n; j++) {
int penalty = yPrefix[j] + nSuffix[j];
if (penalty < minPenalty) {
minPenalty = penalty;
minHour = j;
}
}
return minHour;
}
static void Main() {
string customers = "YYNY";
int result = MinimumPenalty(customers);
Console.WriteLine(result);
}
}By using prefix and suffix sums, you can determine the cumulative count of 'Y' and 'N' in linear time, which allows efficient penalty calculation when considering different closing hours.
Time Complexity: O(n)
Space Complexity: O(n)
Approach 2: Sliding Window Approach
The sliding window approach attempts to keep a running window of penalty calculation as the considered closing hour is incremented, using just a few shared variables instead of arrays.
def minimum_penalty(customers):
n = len(customers)
open_no_customers = customers.count('N')
closed_with_customers = 0
min_penalty = open_no_customers
min_hour = 0
for i in range(n):
if customers[i] == 'Y':
closed_with_customers += 1
else:
open_no_customers -= 1
current_penalty = open_no_customers + closed_with_customers
if current_penalty < min_penalty:
min_penalty = current_penalty
min_hour = i + 1
return min_hour
# Example usage:
customers = "YYNY"
result = minimum_penalty(customers)
print(result) # Output: 2public class Main {
public static int minimumPenalty(String customers) {
int n = customers.length();
int open_no_customers = 0, closed_with_customers = 0;
int min_penalty = 0, min_hour = 0;
for (char c : customers.toCharArray()) {
if (c == 'N') open_no_customers++;
}
min_penalty = open_no_customers;
for (int i = 0; i < n; ++i) {
if (customers.charAt(i) == 'Y')
closed_with_customers++;
else
open_no_customers--;
int current_penalty = open_no_customers + closed_with_customers;
if (current_penalty < min_penalty) {
min_penalty = current_penalty;
min_hour = i + 1;
}
}
return min_hour;
}
public static void main(String[] args) {
String customers = "YYNY";
int result = minimumPenalty(customers);
System.out.println(result);
}
}#include <iostream>
#include <string>
using namespace std;
int minimumPenalty(string customers) {
int n = customers.size();
int open_no_customers = 0, closed_with_customers = 0, min_penalty = 0, min_hour = 0;
for (char c : customers) {
if (c == 'N') open_no_customers++;
}
min_penalty = open_no_customers;
for (int i = 0; i < n; ++i) {
if (customers[i] == 'Y')
closed_with_customers++;
else
open_no_customers--;
int current_penalty = open_no_customers + closed_with_customers;
if (current_penalty < min_penalty) {
min_penalty = current_penalty;
min_hour = i + 1;
}
}
return min_hour;
}
int main() {
string customers = "YYNY";
int result = minimumPenalty(customers);
cout << result << endl;
return 0;
}function minimumPenalty(customers) {
const n = customers.length;
let openNoCustomers = 0;
let closedWithCustomers = 0;
for (let i = 0; i < n; i++) {
if (customers[i] === 'N') openNoCustomers++;
}
let minPenalty = openNoCustomers;
let minHour = 0;
for (let i = 0; i < n; i++) {
if (customers[i] === 'Y')
closedWithCustomers++;
else
openNoCustomers--;
const currentPenalty = openNoCustomers + closedWithCustomers;
if (currentPenalty < minPenalty) {
minPenalty = currentPenalty;
minHour = i + 1;
}
}
return minHour;
}
// Example usage
const customers = "YYNY";
console.log(minimumPenalty(customers)); // Output: 2#include <stdio.h>
#include <string.h>
int minimumPenalty(char* customers) {
int n = strlen(customers);
int open_no_customers = 0, closed_with_customers = 0, min_penalty, min_hour = 0;
for (int i = 0; i < n; i++) {
if (customers[i] == 'N')
open_no_customers++;
}
min_penalty = open_no_customers;
for (int i = 0; i < n; i++) {
if (customers[i] == 'Y')
closed_with_customers++;
else
open_no_customers--;
int current_penalty = open_no_customers + closed_with_customers;
if (current_penalty < min_penalty) {
min_penalty = current_penalty;
min_hour = i + 1;
}
}
return min_hour;
}
int main() {
char customers[] = "YYNY";
int result = minimumPenalty(customers);
printf("%d\n", result);
return 0;
}using System;
class Program {
public static int MinimumPenalty(string customers) {
int n = customers.Length;
int openNoCustomers = 0, closedWithCustomers = 0;
foreach(char c in customers) {
if (c == 'N') openNoCustomers++;
}
int minPenalty = openNoCustomers;
int minHour = 0;
for (int i = 0; i < n; i++) {
if (customers[i] == 'Y')
closedWithCustomers++;
else
openNoCustomers--;
int currentPenalty = openNoCustomers + closedWithCustomers;
if (currentPenalty < minPenalty) {
minPenalty = currentPenalty;
minHour = i + 1;
}
}
return minHour;
}
static void Main() {
string customers = "YYNY";
int result = MinimumPenalty(customers);
Console.WriteLine(result);
}
}Maintaining two counters, this implementation dynamically computes the penalty for each incrementing closing hour by using minimal state-tracking variables.
Time Complexity: O(n)
Space Complexity: O(1)
Approach 3: Enumeration
If the shop closes at hour 0, then the cost is the number of character 'Y' in customers. We initialize the answer variable ans to 0, and the cost variable cost to the number of character 'Y' in customers.
Next, we enumerate the shop closing at hour j (1 leq j leq n). If customers[j - 1] is 'N', it means no customer arrived during the open period, and the cost increases by 1; otherwise, it means a customer arrived during the closed period, and the cost decreases by 1. If the current cost cost is less than the minimum cost mn, we update the answer variable ans to j, and update the minimum cost mn to the current cost cost.
After the traversal ends, we return the answer variable ans.
The time complexity is O(n), where n is the length of the string customers. The space complexity is O(1).
function bestClosingTime(customers: string): number {
let ans = 0;
let cost = 0;
for (const ch of customers) {
if (ch === 'Y') {
cost++;
}
}
let mn = cost;
for (let j = 1; j <= customers.length; j++) {
const c = customers[j - 1];
cost += c === 'N' ? 1 : -1;
if (cost < mn) {
mn = cost;
ans = j;
}
}
return ans;
}func bestClosingTime(customers string) int {
ans := 0
cost := strings.Count(customers, "Y")
mn := cost
for j := 1; j <= len(customers); j++ {
c := customers[j-1]
if c == 'N' {
cost++
} else {
cost--
}
if cost < mn {
ans = j
mn = cost
}
}
return ans
}impl Solution {
pub fn best_closing_time(customers: String) -> i32 {
let bytes = customers.as_bytes();
let mut cost: i32 = bytes.iter().filter(|&&c| c == b'Y').count() as i32;
let mut mn = cost;
let mut ans: i32 = 0;
for j in 1..=bytes.len() {
let c = bytes[j - 1];
if c == b'N' {
cost += 1;
} else {
cost -= 1;
}
if cost < mn {
mn = cost;
ans = j as i32;
}
}
ans
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Cumulative Sum Approach | Time Complexity: O(n) |
| Sliding Window Approach | Time Complexity: O(n) |
| Enumeration | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Simulation | O(n²) | O(1) | Good for understanding the penalty definition or verifying logic on small inputs |
| Cumulative Sum / Prefix Penalty | O(n) | O(n) | When you want clear prefix-based reasoning using precomputed counts |
| Sliding Window Penalty Tracking | O(n) | O(1) | Optimal solution for interviews and production due to constant space |
Frequently asked questions
Is Minimum Penalty for a Shop easy or hard?
The problem is rated Medium because the brute force idea is straightforward but recognizing the prefix sum optimization requires pattern recognition. Once you model the penalties as incremental updates, the solution becomes a simple linear scan.
Minimum Penalty for a Shop Python/Java solution
Python, Java, C++, C#, and JavaScript implementations typically follow the same O(n) logic. Maintain a running penalty value and update it while iterating through the string, tracking the minimum penalty and its corresponding closing hour.
How to solve Minimum Penalty for a Shop in O(n)?
Start with the penalty assuming the shop closes at hour 0, meaning every 'Y' contributes a penalty. Iterate through the string and update the penalty: encountering 'Y' reduces the penalty, while 'N' increases it. Track the minimum penalty encountered and record the earliest hour where it occurs.
What is the best approach for Minimum Penalty for a Shop?
The best approach is the O(n) sliding window or prefix penalty method. Instead of recomputing penalties for every closing hour, update the penalty dynamically while scanning the string. This reduces the problem to a single pass and constant extra space.
Is Minimum Penalty for a Shop asked at Google/Amazon/Meta?
This problem represents a common interview pattern involving prefix sums and incremental scoring. Variations of this technique appear in interviews at companies like Amazon, Google, and Meta where candidates must optimize repeated calculations using prefix or running sums.
What data structure is used in Minimum Penalty for a Shop?
The problem primarily uses strings and prefix sum style counting. Some implementations use arrays for prefix and suffix penalties, while the most optimized approach uses simple integer counters and a single pass over the string.
What is the time complexity of Minimum Penalty for a Shop?
The optimal solution runs in O(n) time where n is the length of the customers string. Each character is processed once while updating the running penalty. Space complexity can be O(1) with the sliding window technique or O(n) with prefix arrays.