What is the brute force approach and complexity for Minimum Penalty for a Shop?

For each j in 0..n, count 'N' before j and 'Y' from j onward with time complexity O(N²) and space complexity O(1).

What is the optimal approach and complexity for Minimum Penalty for a Shop?

Start at penalty = total Y, then ±1 per hour as the closing time moves right with optimal time complexity O(N) and space complexity O(1).

How do you identify the pattern for Minimum Penalty for a Shop?

Look for key signals in the prompt: "open during hours 0 … j−1" indicates The left part is a prefix: count 'N' before j.; "closed from hour j onward" indicates The right part is a suffix: count 'Y' from j on.; "0 ≤ j ≤ n" indicates n + 1 split points, including both empty ends — like prefix arrays of size n + 1.; "earliest hour on a tie" indicates Scan j from 0 upward and only update on a strictly smaller penalty..

Minimum Penalty for a Shop

Medium·LeetCode #2483 Pro OnlyTricky / Edge Case

LeetCode

Problem Statement

A shop keeps a log of n hours as a string customers. customers[i] is 'Y' if customers came during hour i, and 'N' if nobody came.

You must pick a closing hour j, where 0 ≤ j ≤ n. The shop is open during hours 0 … j−1 and closed from hour j onward. Choosing j = n means it stays open for every hour.

The penalty for closing at j is:

+1 for every open hour with 'N' (open, but nobody came), and
+1 for every closed hour with 'Y' (closed, but customers came).

Return the closing hour with the smallest penalty. If several hours tie, return the earliest one.

Input

A string customers of length n made of the characters 'Y' and 'N'.

Output

One integer j in [0, n]: the earliest closing hour with the minimum penalty.

Example 1

Input: customers = "YYNY"

Output: 2

Penalties for j = 0, 1, 2, 3, 4 are 3, 2, 1, 2, 1. The minimum is 1, first reached at j = 2 (open for YY, closed for NY: one missed Y).

Example 2

Input: customers = "NNNNN"

Output: 0

Nobody ever comes, so closing right away costs 0.

Example 3

Input: customers = "YYYY"

Output: 4

Customers come every hour, so the best is to stay open the whole time: j = n = 4.

Constraints

• 1 ≤ n ≤ 10^5
• customers contains only 'Y' and 'N'.

Pattern Recognition Clues

Recognising these key signals in the problem description immediately identifies the pattern:

“open during hours 0 … j−1”

→ The left part is a prefix: count 'N' before j.

“closed from hour j onward”

→ The right part is a suffix: count 'Y' from j on.

“0 ≤ j ≤ n”

→ n + 1 split points, including both empty ends — like prefix arrays of size n + 1.

“earliest hour on a tie”

→ Scan j from 0 upward and only update on a strictly smaller penalty.

Approach Complexity Ladder

Brute Force — compute the penalty of every closing hourO(N²)O(1)

For each j in 0..n, count 'N' before j and 'Y' from j onward

Better — prefix 'N' counts + suffix 'Y' countsO(N)O(N)

Build N-counts from the left and Y-counts from the right, then add them per hour

Optimal — one running penaltyO(N)O(1)

Start at penalty = total Y, then ±1 per hour as the closing time moves right

Brute Force Intuition

Try every closing hour j from 0 to n. Count the 'N' in customers[0 … j−1] and the 'Y' in customers[j … n−1]. Keep the first j with the smallest total.

Recognition rule for this sub-pattern:

Each index needs information from its left and its right. Build a left pass and a right pass, then combine.

Remember this · Prefix Sum

Trigger

Range sums, "subarray sum equals K" (especially with negatives), equal counts, divisible by K.

Think

If I knew the total up to every index, would the answer become a difference of two totals?

Key question

Which earlier prefix value am I looking for when I stand at index i?

Brute2Best Pro Content

Unlock Complete Visual Walkthrough & Optimal C++

The interactive animated dry-run player, optimized C++ implementation, state invariant derivations, and edge-case breakdown for this question are part of Brute2Best Pro. The anchor question of every sub-pattern is completely free.

All 440 visual dry runs & algorithms

Interactive step-by-step playback with pointer & array state transitions

52 comprehensive LLD chapters

Interactive UML diagrams, real-world stories (Food Delivery, Trading, RPG), and practice solutions

40 C++ basics labs & hardware memory models

Vtables, byte layouts, assembly insights, and multi-threading race conditions

Production-ready C++23 source code

Modern idioms, clean contracts, time/space complexity derivations, and interview takeaways

Create Free Account Log in

First anchor question per pattern, Part 1 LLD & Module 1 C++ basics are 100% Free forever.

Beyond The LeetCode Problem

How this concept connects to System Design & C++ Systems

Bridge DSA with production engineering

Top engineering interviews test whether you understand how algorithms like Prefix Sum translate into production architectures and low-level memory mechanics.

LLD Architecture