Minimum Penalty for a Shop

MEDIUM

Description

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

Approaches

Checkout 3 different approaches to solve Minimum Penalty for a Shop. Click on different approaches to view the approach and algorithm in detail.

Using Prefix and Suffix Sums

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.

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 Analysis

Time Complexity: 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 Complexity: O(n). We use two extra arrays of size `n+1` to store the prefix and suffix counts.

Pros and Cons

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.

Code Solutions

Checking out 3 solutions in different languages for Minimum Penalty for a Shop. Click on different languages to view the code.

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 Solution

Watch the video walkthrough for Minimum Penalty for a Shop

Patterns:

Prefix Sum

Data Structures:

String

Companies:

Stripe |