Scale Engineer

Minimum Penalty for a Shop

Med
#2265Time: O(n). We perform three separate passes over the data: one for `prefixN`, one for `suffixY`, and one to find the minimum penalty. Each pass takes O(n) time.Space: O(n). We use two extra arrays of size `n+1` to store the prefix and suffix counts.1 company
Patterns
Prefix Sum
Data structures
String
Companies
Stripe

Prompt

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

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 <= 105
  • customers consists only of characters 'Y' and 'N'.

Approaches

3 approaches with complexity analysis and trade-offs.

This approach optimizes the penalty calculation by pre-computing the counts of 'N's and 'Y's. The penalty for closing at hour j is the sum of 'N's before j and 'Y's at or after j. We can use a prefix sum array for the 'N's and a suffix sum array for the 'Y's to find these counts in O(1) time for each j.

Algorithm

  • Create a prefixN array of size n+1. Populate it such that prefixN[i] is the count of 'N's in customers up to index i-1.
  • Create a suffixY array of size n+1. Populate it such that suffixY[i] is the count of 'Y's in customers from index i to the end.
  • Initialize minPenalty to a large value and bestHour to 0.
  • Iterate j from 0 to n.
  • For each j, calculate currentPenalty = prefixN[j] + suffixY[j].
  • If currentPenalty is less than minPenalty, update minPenalty to currentPenalty and bestHour to j.
  • Return bestHour.

Walkthrough

The core idea is to avoid re-calculating counts for each closing hour. We create a prefixN array where prefixN[i] stores the total number of 'N's in the substring customers[0...i-1]. We also create a suffixY array where suffixY[i] stores the total number of 'Y's in the substring customers[i...n-1]. Both arrays can be computed in O(n) time. Once we have these arrays, the penalty for closing at hour j can be calculated in O(1) time as penalty(j) = prefixN[j] + suffixY[j]. We then iterate from j = 0 to n, calculate the penalty for each j using the pre-computed arrays, and find the hour with the minimum penalty.

class Solution {    public int bestClosingTime(String customers) {        int n = customers.length();                int[] prefixN = new int[n + 1];        for (int i = 0; i < n; i++) {            prefixN[i + 1] = prefixN[i] + (customers.charAt(i) == 'N' ? 1 : 0);        }         int[] suffixY = new int[n + 1];        for (int i = n - 1; i >= 0; i--) {            suffixY[i] = suffixY[i + 1] + (customers.charAt(i) == 'Y' ? 1 : 0);        }         int minPenalty = Integer.MAX_VALUE;        int bestHour = -1;        for (int j = 0; j <= n; j++) {            int currentPenalty = prefixN[j] + suffixY[j];            if (currentPenalty < minPenalty) {                minPenalty = currentPenalty;                bestHour = j;            }        }        return bestHour;    }}

Complexity

Time

O(n). We perform three separate passes over the data: one for `prefixN`, one for `suffixY`, and one to find the minimum penalty. Each pass takes O(n) time.

Space

O(n). We use two extra arrays of size `n+1` to store the prefix and suffix counts.

Trade-offs

Pros

  • Much more efficient than the brute-force approach.

  • Linear time complexity is well within the given constraints.

Cons

  • Requires extra space proportional to the input size, which might be a concern for very large inputs in a memory-constrained environment.

Solutions

class Solution {public  int bestClosingTime(String customers) {    int n = customers.length();    int[] s = new int[n + 1];    for (int i = 0; i < n; ++i) {      s[i + 1] = s[i] + (customers.charAt(i) == 'Y' ? 1 : 0);    }    int ans = 0, cost = 1 << 30;    for (int j = 0; j <= n; ++j) {      int t = j - s[j] + s[n] - s[j];      if (cost > t) {        ans = j;        cost = t;      }    }    return ans;  }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem