Minimum Penalty for a Shop

Medium Arrays & Hashing Prefix Sum Strategy Original on LeetCode

Reported atStripe

Minimum Penalty for a Shop is a medium arrays & hashing problem solved with the prefix sum strategy pattern. The best approach, optimal (one pass, relative penalty), runs in O(n) time and O(1) space. Below are 3 approaches in Java, Python, C++ and JavaScript, from brute force up.

Problem

A shop logs its customers hour by hour in a string customers of length n: customers[i] is 'Y' if at least one customer came during hour i, and 'N' if nobody did.

If the shop closes at hour j (where 0 <= j <= n), it is open for hours 0 to j - 1 and closed from hour j on. The penalty is one point for every hour it is open with no customers, plus one point for every hour it is closed while customers show up.

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

Examples

Example 1

Input
customers = "YNYYN"
Output
4
Why
Closing at hour 4 costs 1 (hour 1 open with nobody) + 0 + 0 = 1. No other closing hour costs less.

Example 2

Input
customers = "NNY"
Output
0
Why
Closing at 0 costs 1 (the customer at hour 2). Closing at 3 costs 2, and hours 1 and 2 cost 2 or more as well.

Example 3

Input
customers = "YY"
Output
2
Why
Customers come every hour, so staying open the whole day has zero penalty.

Constraints

  • 1 <= customers.length <= 10^5
  • Each customers[i] is 'Y' or 'N'.

Solve it here

Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.

00:00
Testcase

Run checks the testcases above (3 examples, or your own). Submit also runs 15 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.

ApproachTimeSpace
Brute forceO(n²)O(1)
Prefix and suffix countsO(n)O(n)
Optimal (one pass, relative penalty)O(n)O(1)

1Brute force

TimeO(n²)n + 1 closing hours, each scored with a full O(n) scan.
SpaceO(1)Only counters.

For each closing hour j from 0 to n, count the penalty directly by scanning the whole string, and keep the smallest (earliest on ties).

  1. For j from 0 to n: penalty = count of 'N' in [0, j) + count of 'Y' in [j, n).
  2. If penalty is strictly smaller than the best so far, record j.
  3. Return the recorded hour.
class Solution {
    public int bestClosingTime(String customers) {
        int n = customers.length();
        int best = Integer.MAX_VALUE, bestHour = 0;
        for (int j = 0; j <= n; j++) {
            int penalty = 0;
            for (int i = 0; i < n; i++) {
                char c = customers.charAt(i);
                if (i < j && c == 'N') penalty++;
                if (i >= j && c == 'Y') penalty++;
            }
            if (penalty < best) {
                best = penalty;
                bestHour = j;
            }
        }
        return bestHour;
    }
}

2Prefix and suffix counts

TimeO(n)Two passes to build the arrays and one to score every hour.
SpaceO(n)Two arrays of n + 1 counts.

Precompute how many 'N' appear before each hour and how many 'Y' appear from each hour on. The penalty for hour j is then the sum of two array lookups.

  1. noBefore[0] = 0 and noBefore[i + 1] = noBefore[i] + (customers[i] == 'N').
  2. yesFrom[n] = 0 and yesFrom[i] = yesFrom[i + 1] + (customers[i] == 'Y').
  3. For j from 0 to n, penalty = noBefore[j] + yesFrom[j]; keep the earliest minimum.
class Solution {
    public int bestClosingTime(String customers) {
        int n = customers.length();
        int[] noBefore = new int[n + 1];
        int[] yesFrom = new int[n + 1];
        for (int i = 0; i < n; i++) {
            noBefore[i + 1] = noBefore[i] + (customers.charAt(i) == 'N' ? 1 : 0);
        }
        for (int i = n - 1; i >= 0; i--) {
            yesFrom[i] = yesFrom[i + 1] + (customers.charAt(i) == 'Y' ? 1 : 0);
        }
        int bestHour = 0;
        for (int j = 1; j <= n; j++) {
            if (noBefore[j] + yesFrom[j] < noBefore[bestHour] + yesFrom[bestHour]) bestHour = j;
        }
        return bestHour;
    }
}

3Optimal (one pass, relative penalty)

TimeO(n)A single pass over the string.
SpaceO(1)Three integers.

Measure every closing hour against closing at hour 0. Pushing the closing time past hour i makes that hour open: a 'Y' there saves one penalty point, an 'N' costs one. So keep a running score (+1 for 'N', -1 for 'Y') and remember the first hour where it hits a new minimum.

  1. score = 0, best = 0, bestHour = 0.
  2. For i from 0 to n - 1: score += (customers[i] == 'N') ? 1 : -1.
  3. If score < best, set best = score and bestHour = i + 1.
  4. Return bestHour.
class Solution {
    public int bestClosingTime(String customers) {
        int score = 0, best = 0, bestHour = 0;
        for (int i = 0; i < customers.length(); i++) {
            score += customers.charAt(i) == 'N' ? 1 : -1;
            if (score < best) {
                best = score;
                bestHour = i + 1;
            }
        }
        return bestHour;
    }
}

Edge cases to test

  • All 'N': closing at hour 0 is best
  • All 'Y': stay open through the last hour and close at n
  • Ties between several hours: return the earliest
  • A single hour

Hints

Hint 1

The penalty for closing at hour j is (number of N before j) + (number of Y from j onwards). Try every j.

Hint 2

Moving the closing hour from j to j + 1 changes the penalty by exactly one, depending only on customers[j].

Hint 3

Track the change relative to closing at hour 0 instead of absolute penalties; you never need the totals.

FAQ

What is the best time complexity for Minimum Penalty for a Shop?

Optimal (one pass, relative penalty) runs in O(n) time and O(1) extra space. A single pass over the string.

Which pattern does Minimum Penalty for a Shop use?

It is a arrays & hashing problem that uses the prefix sum strategy pattern. Other problems with the same pattern: Subarray Sum Equals K, Subarray with given XOR, Range Sum Query - Immutable.

Is there a brute force solution for Minimum Penalty for a Shop?

Yes. Brute force takes O(n²) time and O(1) space. For each closing hour j from 0 to n, count the penalty directly by scanning the whole string, and keep the smallest (earliest on ties).

Which edge cases should I test for Minimum Penalty for a Shop?

All 'N': closing at hour 0 is best; All 'Y': stay open through the last hour and close at n; Ties between several hours: return the earliest; A single hour.