Minimum Penalty for a Shop - Solution & Explanation

Q: 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.

Q: 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.

Q: 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.

Q: 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.

Q: 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.

Q: 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.

Q: 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.

MediumString Prefix Sum21 min readAsked at: Amazon, Microsoft, Meta +3

Practice this problem

Problem Statement

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 i^th character is 'Y', it means that customers come at the i^th hour
whereas 'N' indicates that no customers come at the i^th hour.

If the shop closes at the j^th 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 j^th hour, it means the shop is closed at the hour j.

Example 1:

Input: customers = "YYNY"
Output: 2
Explanation: 
- Closing the shop at the 0^th hour incurs in 1+1+0+1 = 3 penalty.
- Closing the shop at the 1^st hour incurs in 0+1+0+1 = 2 penalty.
- Closing the shop at the 2^nd hour incurs in 0+0+0+1 = 1 penalty.
- Closing the shop at the 3^rd hour incurs in 0+0+1+1 = 2 penalty.
- Closing the shop at the 4^th hour incurs in 0+0+1+0 = 1 penalty.
Closing the shop at 2^nd or 4^th 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 0^th hour as no customers arrive.

Example 3:

Input: customers = "YYYY"
Output: 4
Explanation: It is best to close the shop at the 4^th hour as customers arrive at each hour.

Constraints:

1 <= customers.length <= 10⁵
customers consists 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.

The implementation uses prefix and suffix arrays to keep track of Y and N counts up to each hour. This preprocessing helps calculate the penalty efficiently for each potential closing time point.

Code

C C++Java Python C#JavaScript

C++

Java

Python

JavaScript

Complexity

Time Complexity: O(n)
Space Complexity: O(n)

Try this approach in the editor →

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.

This implementation uses two counters: 'open_no_customers' for open hours without customers and 'closed_with_customers' for closed hours with customers. As we evaluate each closing hour, penalties are adjusted efficiently without needing full array storage.

Code

C C++Java Python C#JavaScript

C++

Java

Python

JavaScript

Complexity

Time Complexity: O(n)
Space Complexity: O(1)

Try this approach in the editor →

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).

Code

Python Java C++Go TypeScript Rust C#

Python

Java

C++

TypeScript

Rust

Try this approach in the editor →

Complexity Comparison

Approach	Complexity
Cumulative Sum Approach	Time Complexity: O(n) Space Complexity: O(n)
Sliding Window Approach	Time Complexity: O(n) Space Complexity: O(1)
Enumeration	—

Detailed 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

Video Solution

Minimum Penalty for a Shop - Leetcode 2483 - Python • NeetCodeIO • 12,742 views views

Watch 9 more video solutions →

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.

Ready to solve this problem?

Practice Minimum Penalty for a Shop with our built-in code editor and test cases.

Practice on FleetCode

Grid Game

Minimum Amount of Damage Dealt to Bob

Problem Info

DifficultyMedium

Acceptance71.2%

Approaches3

Reading time21 min

Asked at

Amazon Microsoft Meta Google Stripe

Practice this problem

Open in Editor

Problem Statement

Approach Overview

Approach 1: Cumulative Sum Approach

Code

Complexity

Approach 2: Sliding Window Approach

Code

Complexity

Approach 3: Enumeration

Code

Complexity Comparison

Detailed Complexity Analysis

Video Solution

Frequently Asked Questions

Related Problems

Ready to solve this problem?

Problem Info

Table of Contents