Minimum Penalty for a Shop
Problem 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 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.
Examples:
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.
Input: customers = "NNNNN"
Output: 0
Explanation: It is best to close the shop at the 0th hour as no customers arrive.
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 <= 10⁵
- customers consists only of characters 'Y' and 'N'.
Brute Force Approach
Okay, so here's the thought process:
What comes to mind after reading the problem statement?
We need to calculate the penalty incurred for closing the shop at each hour and determine the hour at which the shop should be closed to minimize this penalty. The shopkeeper incurs a penalty in the following cases:
- When a customer arrives and the shop is closed.
- When no customers arrive, but the shop is open.
For every hour, we will compute the total penalty for closing the shop at that specific hour. Finally, we will return the hour that results in the minimum penalty.
How can we do that?
We will create an array penalties of size n+1 (n+1, because the shop can also be closed at the nth hour) to store the penalty for closing the shop at each hour.
For every hour, we will iterate through the entire string again and increase the penalty in the following cases:
- If the shop is closed and a customer arrives.
- If the shop is open and no customers arrive.
The penalty for that hour will be stored in the penalties array.
At the end, we will traverse the penalties array to find and return the hour with the minimum penalty.
Let's walk through an example:
Dry Run for customers = "YYNY":
- Initialization:
customers = "YYNY" (Length = 4)
penalties = [0, 0, 0, 0, 0] (Array of size n+1 = 5) - Penalty Calculation for Each Closing Hour:
- Hour 0: Shop is closed for all hours.
Penalty = 1 (Hour 0, Customer Y) + 1 (Hour 1, Customer Y) + 1 (Hour 3, Customer Y) = 3
penalties[0] = 3 - Hour 1: Shop is open only for Hour 0.
Penalty = 0 (Hour 0, Open, Customer Y) + 1 (Hour 1, Customer Y) + 1 (Hour 3, Customer Y) = 2
penalties[1] = 2 - Hour 2: Shop is open for Hours 0 to 1.
Penalty = 0 (Hour 0, Open, Customer Y) + 0 (Hour 1, Open, Customer Y) + 1 (Hour 3, Customer Y) = 1
penalties[2] = 1 - Hour 3: Shop is open for Hours 0 to 2.
Penalty = 0 (Hour 0, Open, Customer Y) + 0 (Hour 1, Open, Customer Y) + 0 (Hour 3, Open, Customer Y) = 1
penalties[3] = 1 - Hour 4: Shop is open for all hours.
Penalty = 0 (No customers missed) = 0
penalties[4] = 0
- Hour 0: Shop is closed for all hours.
- Find Minimum Penalty:
penalties = [3, 2, 1, 1, 0]
Minimum penalty = 1, occurs at Hour 2. - Output: 2
How to convert it in code:
Here are the steps to convert the approach into code:
1. Initialize Variables
- Determine the size of the customers string and store it in n.
- Create a penalties array of size n+1 to store the penalty values for each possible closing hour.
2. Calculate Penalties for Each Closing Hour
- Loop through all possible closing hours (from 0 to n). For each hour:
- Initialize a penalty variable to zero.
- Iterate through all hours of the day:
- If the current hour is less than the closing hour, check if the shop is open. Add to the penalty if no customers arrive (indicated by 'N').
- If the current hour is greater than or equal to the closing hour, check if the shop is closed. Add to the penalty if customers arrive (indicated by 'Y').
- Store the penalty for the current hour in the penalties array.
3. Find the Hour with Minimum Penalty
- Initialize a variable ans to store the hour with the minimum penalty and set penalty to a large value (to represent infinity initially).
- Traverse through the penalties array:
- If the penalty for the current hour is less than the stored minimum, update penalty and set ans to the current hour.
4. Return the Result
- Return the value of ans, which represents the hour with the minimum penalty.
Code Implementation
1. C++ Try on Compiler
class Solution {
public:
int bestClosingTime(string customers) {
// Get the size of the customer string.
int n = customers.size();
// Create a penalties array of size n+1, initialized to 0.
vector<int> penalties(n+1, 0);
// Calculate the penalty for closing the shop at each hour.
// Loop through all possible closing hours (from 0 to n).
for (int i = 0; i <= n; i++) {
// Initialize penalty for the current closing hour.
int penalty = 0;
// Iterate through all hours of the day.
for (int j = 0; j < n; j++) {
// If the shop is open (before the closing hour),
if (j < i) {
// and no customer arrives ('N'),
if (customers[j] == 'N')
// increase the penalty.
penalty++;
// If the shop is closed (after or at the closing hour),
} else {
// and a customer arrives ('Y'),
if (customers[j] == 'Y')
// increase the penalty.
penalty++;
}
}
// Store the penalty for closing at hour i.
penalties[i] = penalty;
}
// Find the hour with the minimum penalty.
// Initialize the answer to store the best closing hour.
int ans = 0;
// Initialize the minimum penalty to a large value.
int penalty = INT_MAX;
// Traverse through the penalties array.
for (int i = 0; i <= n; i++) {
// If the current penalty is less than the minimum penalty,
if (penalties[i] < penalty) {
// update the minimum penalty.
penalty = penalties[i];
// Update the answer with the current hour.
ans = i;
}
}
// Return the hour with the minimum penalty.
return ans;
}
};
2. Java Try on Compiler
class Solution {
public int bestClosingTime(String customers) {
// Get the size of the customer string.
int n = customers.length();
// Create a penalties array of size n+1, initialized to 0.
int[] penalties = new int[n + 1];
// Calculate the penalty for closing the shop at each hour.
// Loop through all possible closing hours (from 0 to n).
for (int i = 0; i <= n; i++) {
// Initialize penalty for the current closing hour.
int penalty = 0;
// Iterate through all hours of the day.
for (int j = 0; j < n; j++) {
// If the shop is open (before the closing hour),
if (j < i) {
// and no customer arrives ('N'),
if (customers.charAt(j) == 'N')
// increase the penalty.
penalty++;
// If the shop is closed (after or at the closing hour),
} else {
// and a customer arrives ('Y'),
if (customers.charAt(j) == 'Y')
// increase the penalty.
penalty++;
}
}
// Store the penalty for closing at hour i.
penalties[i] = penalty;
}
// Find the hour with the minimum penalty.
// Initialize the answer to store the best closing hour.
int ans = 0;
// Initialize the minimum penalty to a large value.
int minPenalty = Integer.MAX_VALUE;
// Traverse through the penalties array.
for (int i = 0; i <= n; i++) {
// If the current penalty is less than the minimum penalty,
if (penalties[i] < minPenalty) {
// update the minimum penalty.
minPenalty = penalties[i];
// Update the answer with the current hour.
ans = i;
}
}
// Return the hour with the minimum penalty.
return ans;
}
}
3. Python Try on Compiler
class Solution:
def bestClosingTime(self, customers):
# Get the size of the customer string.
n = len(customers)
# Create a penalties array of size n+1, initialized to 0.
penalties = [0] * (n + 1)
# Calculate the penalty for closing the shop at each hour.
# Loop through all possible closing hours (from 0 to n).
for i in range(n + 1):
# Initialize penalty for the current closing hour.
penalty = 0
# Iterate through all hours of the day.
for j in range(n):
# If the shop is open (before the closing hour),
if j < i:
# and no customer arrives ('N'),
if customers[j] == 'N':
# increase the penalty.
penalty += 1
# If the shop is closed (after or at the closing hour),
else:
# and a customer arrives ('Y'),
if customers[j] == 'Y':
# increase the penalty.
penalty += 1
# Store the penalty for closing at hour i.
penalties[i] = penalty
# Find the hour with the minimum penalty.
# Initialize the answer to store the best closing hour.
ans = 0
# Initialize the minimum penalty to a large value.
min_penalty = float('inf')
# Traverse through the penalties array.
for i in range(n + 1):
# If the current penalty is less than the minimum penalty,
if penalties[i] < min_penalty:
# update the minimum penalty.
min_penalty = penalties[i]
# Update the answer with the current hour.
ans = i
# Return the hour with the minimum penalty.
return ans
4. Javascript Try on Compiler
/**
* @param {string} customers
* @return {number}
*/
var bestClosingTime = function(customers) {
// Get the size of the customer string.
const n = customers.length;
// Create a penalties array of size n+1, initialized to 0.
const penalties = Array(n + 1).fill(0);
// Calculate the penalty for closing the shop at each hour.
// Loop through all possible closing hours (from 0 to n).
for (let i = 0; i <= n; i++) {
// Initialize penalty for the current closing hour.
let penalty = 0;
// Iterate through all hours of the day.
for (let j = 0; j < n; j++) {
// If the shop is open (before the closing hour),
if (j < i) {
// and no customer arrives ('N'),
if (customers[j] === 'N')
// increase the penalty.
penalty++;
// If the shop is closed (after or at the closing hour),
} else {
// and a customer arrives ('Y'),
if (customers[j] === 'Y')
// increase the penalty.
penalty++;
}
}
// Store the penalty for closing at hour i.
penalties[i] = penalty;
}
// Find the hour with the minimum penalty.
// Initialize the answer to store the best closing hour.
let ans = 0;
// Initialize the minimum penalty to a large value.
let minPenalty = Infinity;
// Traverse through the penalties array.
for (let i = 0; i <= n; i++) {
// If the current penalty is less than the minimum penalty,
if (penalties[i] < minPenalty) {
// update the minimum penalty.
minPenalty = penalties[i];
// Update the answer with the current hour.
ans = i;
}
}
// Return the hour with the minimum penalty.
return ans;
};Time Complexity: O(n²)
The outer loop iterates through all possible closing hours, from 0 to n (inclusive). This results in n+1 iterations.
For each closing hour, the inner loop iterates through all the hours of the day, which is n iterations. This results in a nested loop structure with n+1 outer iterations and n inner iterations for each outer iteration.
This means that during the first iteration, the inner loop runs n times, during the second iteration it runs n times again, and so on, for a total of n+1 iterations of the outer loop.
Thus, the total number of operations performed by the inner loop across all iterations of the outer loop is:
n + n + n ... (n+1 times)
This simplifies to: (n+1) * n / 2
When analyzing complexity, we drop constants and lower-order terms, leaving us with a time complexity of O(n²).
For each iteration of the inner loop, comparisons and conditional statements are performed, which are O(1) operations.
Hence, Overall Time Complexity: O(n²)
Space Complexity: O(n)
Auxiliary Space Complexity: O(n)
The penalties array is explicitly allocated to store the penalties for each possible closing hour. Its size is n+1 (where n is the length of the customers string).
No other data structures requiring additional memory are used apart from a few variables like ans, and penalty (inside the loop), which are scalar values and take constant space.
so, the Total Auxiliary Space is O(n) (dominated by the penalties array).
Total Space Complexity: O(n)
The input string customers is passed as an argument, which occupies O(n) space.
Adding this to the auxiliary space gives: Total Space = O(n) + O(n) = O(n)
Will Brute Force Work Against the Given Constraints?
For the current solution, the time complexity is O(n²), which is not suitable for n ≤ 10⁵. This means that for each test case, where the length of the string is at most 10⁵, the solution might not execute within the given time limits.
Since O(n²) results in a maximum of 10¹⁰ operations (for n = 10⁵), the solution is not expected to work well for larger test cases. In most competitive programming environments, problems can handle up to 10⁶ operations per test case, meaning that for n ≤ 10⁵, the solution with 10¹⁰ operations is not efficient enough.
When multiple test cases are involved, the total number of operations could easily exceed this limit and approach 10¹⁰ operations, especially when there are many test cases or the value of n increases.
Thus, while the solution meets the time limits for a single test case, the O(n²) time complexity poses a risk for Time Limit Exceeded (TLE) errors when handling larger input sizes or multiple test cases. This can be a challenge for competitive programming problems with larger inputs or numerous test cases.
Can we optimize it?
Yes! There is a better approach to solve this problem.
Curious?
In our previous approach, we calculated how much penalty there would be if we closed the shop at a certain hour by iterating through the customers string again for every hour. This resulted in a time complexity of O(n²) because, for every hour, we traversed the string again to compute the penalty.
But what if we could do this in just one loop? How?
What if we already knew the penalty for every hour in advance?
How can we achieve that?
We can precompute the penalty for every hour and then find the minimum penalty.
Here’s how it works:
As we traverse over the customers array and extend the closing time of the shop for each hour index:
- If we encounter an 'N', our penalty will increase because it represents a situation where the shop is open, but no customer arrives during that hour. Thus, the penalty is added for each 'N' we encounter while traversing.
Similarly, if we decrease the closing time of the shop, the penalty will increase as we encounter more 'Y' after the shop has closed. Each 'Y' represents a customer who arrived after the shop closed, contributing to the penalty.
Using this observation we can precompute the penalty for every hour.
Here’s the idea:
- Computing the penalty before closing the shop: When the shop is open, encountering an 'N' (no customer arrives) increases the penalty because the shop is open but not being utilized effectively.
As we traverse the string from the beginning for each hour, we accumulate the count of 'N' up to that hour. This count represents the penalty incurred before closing the shop, as these are missed opportunities where the shop was open but no customer arrived. - Computing the penalty after closing the shop: After the shop is closed, encountering a 'Y' (a customer arrives) increases the penalty because these customers missed the opportunity to shop.
By traversing the string backward for each hour, we calculate the cumulative count of 'Y' that occur after the shop closes. This count represents the penalty incurred after the closing, as these customers would have arrived but found the shop closed.
By combining these two penalties (before and after closing), we can compute the total penalty for choosing a specific hour as the closing time. The goal is to find the hour that minimizes this total penalty.
In this way, we precompute penalties for every hour in advance, and we can simply return the hour with the minimum penalty.
How can we do that?
Here's how we can do it:
First, we iterate over the customers array. As we iterate, we simply keep a count of all the 'N' characters because they represent the penalty incurred before the shop is closed. We store this count for all indices in an array called prefix.
Next, we iterate the customers array from the back and keep a count of all the 'Y' characters. These represent the penalty for customers who arrive after the shop is closed for a given index. We store this count for all indices in an array called suffix.
Now, for every index i, prefix[i] represents the penalty incurred before closing the shop at the i-th hour, and suffix[i] represents the penalty incurred after closing the shop at the i-th hour.
The total penalty due to closing the shop at the i-th hour is simply prefix[i] + suffix[i].
Finally, we find the hour that has the minimum total penalty and return that hour.
Note : We make the prefix and suffix arrays of size n+1 (where n is the length of the customers string) because we need to account for all possible closing times, including the case when the shop closes after the last hour.
Let's understand with an example:
Here’s a concise dry run for customers = "YYNYNY":
We will use two arrays: prefix and suffix of size n+1 to effectively count for each index, including the nth hour.
Step 1: Build prefix (Penalties Before Closing)
Iterate from the start, counting 'N' penalties before each hour.
- At index 0: prefix[0] = 0
- At index 1: prefix[1] = 0
- At index 2: prefix[2] = 0
- At index 3: prefix[3] = 1
- At index 4: prefix[4] = 1
- At index 5: prefix[5] = 2
- At index 6: prefix[6] = 2
Result: prefix = [0, 0, 0, 1, 1, 2, 2]
Step 2: Build suffix (Penalties After Closing)
Iterate from the end, counting 'Y' penalties after each hour.
- At index 6: suffix[6] = 0
- At index 5: suffix[5] = 1
- At index 4: suffix[4] = 1
- At index 3: suffix[3] = 2
- At index 2: suffix[2] = 2
- At index 1: suffix[1] = 3
- At index 0: suffix[0] = 4
Result: suffix = [4, 3, 2, 2, 1, 1, 0]
Step 3: Calculate Total Penalty for Each Hour
total_penalty[i] = prefix[i] + suffix[i]
- At index 0: 4 = 0 + 4
- At index 1: 3 = 0 + 3
- At index 2: 2 = 0 + 2
- At index 3: 3 = 1 + 2
- At index 4: 2 = 1 + 1
- At index 5: 3 = 2 + 1
- At index 6: 2 = 2 + 0
Result: total_penalty = [4, 3, 2, 3, 2, 3, 2]
Step 4: Find Minimum Penalty
- Minimum penalty = 2 at index 2.
Final Answer:
The shop should close at hour 2.
How to code it up:
Here’s a step-by-step guide to coding the solution:
Step 1: Initialize Variables
- Define n as the length of the customers string.
- Create two arrays:
- prefixN of size n + 1 initialized to 0, to store penalties for 'N's before closing the shop.
- suffixY of size n + 1 initialized to 0, to store penalties for 'Y's after closing the shop.
- Set the first value of prefixN and the last value of suffixY to 0 because no penalties occur before the shop opens or after it closes completely.
Step 2: Compute the prefixN Array
- Loop from 1 to n:
- If the customer at the previous hour (customers[i-1]) is 'N', increment the penalty by adding 1 to prefixN[i-1].
- Otherwise, carry forward the previous penalty (prefixN[i] = prefixN[i-1]).
Step 3: Compute the suffixY Array
- Loop from n-1 down to 0:
- If the customer at the current hour (customers[i]) is 'Y', increment the penalty by adding 1 to suffixY[i+1].
- Otherwise, carry forward the penalty (suffixY[i] = suffixY[i+1]).
Step 4: Calculate Minimum Penalty
- Initialize two variables:
- minPenalty to INT_MAX to track the smallest penalty.
- minHour to INT_MAX to track the best closing hour.
- Loop from 0 to n:
- Compute the total penalty for each hour as prefixN[i] + suffixY[i].
- If the current penalty is less than minPenalty, update minPenalty and set minHour to the current index.
Step 5: Return the Result
- Return minHour, which represents the best hour to close the shop.
Code Implementation
1. C++ Try on Compiler
class Solution {
public:
int bestClosingTime(string customers) {
// Step 1: Get the number of hours in the customers string
int n = customers.length();
// Step 2: Create the prefix array to store penalties for 'N's before each hour
vector<int> prefix(n+1, 0);
// No penalty before the shop opens
prefix[0] = 0;
// Step 3: Create the suffix array to store penalties for 'Y's after each hour
vector<int> suffix(n+1, 0);
// No penalty after the shop is fully closed
suffix[n] = 0;
// Step 4: Compute the prefix penalties for 'N's
for (int i = 1; i <= n; i++) {
if (customers[i-1] == 'N') {
// If no customer arrives, increment penalty
prefix[i] = prefix[i-1] + 1;
} else {
// Carry forward the penalty if customer arrives
prefix[i] = prefix[i-1];
}
}
// Step 5: Compute the suffix penalties for 'Y's
for (int i = n-1; i >= 0; i--) {
if (customers[i] == 'Y') {
// If a customer arrives after shop is closed, increment penalty
suffix[i] = suffix[i+1] + 1;
} else {
// Carry forward the penalty if no customer arrives
suffix[i] = suffix[i+1];
}
}
// Step 6: Find the hour with the minimum total penalty
// Track the smallest penalty
int minPenalty = INT_MAX;
// Track the hour corresponding to the smallest penalty
int minHour = INT_MAX;
for (int i = 0; i < n+1; i++) {
// Calculate the total penalty for closing at hour i
int currPenalty = prefix[i] + suffix[i];
// Update the minimum penalty and the corresponding hour if needed
if (currPenalty < minPenalty) {
minPenalty = currPenalty;
minHour = i;
}
}
// Step 7: Return the hour with the minimum penalty
return minHour;
}
};2. Java Try on Compiler
class Solution {
public int bestClosingTime(String customers) {
// Step 1: Get the number of hours in the customers string
int n = customers.length();
// Step 2: Create the prefix array to store penalties for 'N's before each hour
int[] prefix = new int[n+1];
// No penalty before the shop opens
prefix[0] = 0;
// Step 3: Create the suffix array to store penalties for 'Y's after each hour
int[] suffix = new int[n+1];
// No penalty after the shop is fully closed
suffix[n] = 0;
// Step 4: Compute the prefix penalties for 'N's
for (int i = 1; i <= n; i++) {
if (customers.charAt(i-1) == 'N') {
// If no customer arrives, increment penalty
prefix[i] = prefix[i-1] + 1;
} else {
// Carry forward the penalty if customer arrives
prefix[i] = prefix[i-1];
}
}
// Step 5: Compute the suffix penalties for 'Y's
for (int i = n-1; i >= 0; i--) {
if (customers.charAt(i) == 'Y') {
// If a customer arrives after shop is closed, increment penalty
suffix[i] = suffix[i+1] + 1;
} else {
// Carry forward the penalty if no customer arrives
suffix[i] = suffix[i+1];
}
}
// Step 6: Find the hour with the minimum total penalty
// Track the smallest penalty
int minPenalty = Integer.MAX_VALUE;
// Track the hour corresponding to the smallest penalty
int minHour = Integer.MAX_VALUE;
for (int i = 0; i < n+1; i++) {
// Calculate the total penalty for closing at hour i
int currPenalty = prefix[i] + suffix[i];
// Update the minimum penalty and the corresponding hour if needed
if (currPenalty < minPenalty) {
minPenalty = currPenalty;
minHour = i;
}
}
// Step 7: Return the hour with the minimum penalty
return minHour;
}
}
3. Python Try on Compiler
class Solution:
def bestClosingTime(self, customers):
# Step 1: Get the number of hours in the customers string
n = len(customers)
# Step 2: Create the prefix array to store penalties for 'N's before each hour
prefix = [0] * (n + 1)
# No penalty before the shop opens
prefix[0] = 0
# Step 3: Create the suffix array to store penalties for 'Y's after each hour
suffix = [0] * (n + 1)
# No penalty after the shop is fully closed
suffix[n] = 0
# Step 4: Compute the prefix penalties for 'N's
for i in range(1, n + 1):
if customers[i-1] == 'N':
# If no customer arrives, increment penalty
prefix[i] = prefix[i-1] + 1
else:
# Carry forward the penalty if customer arrives
prefix[i] = prefix[i-1]
# Step 5: Compute the suffix penalties for 'Y's
for i in range(n-1, -1, -1):
if customers[i] == 'Y':
# If a customer arrives after shop is closed, increment penalty
suffix[i] = suffix[i+1] + 1
else:
# Carry forward the penalty if no customer arrives
suffix[i] = suffix[i+1]
# Step 6: Find the hour with the minimum total penalty
# Track the smallest penalty
minPenalty = float('inf')
# Track the hour corresponding to the smallest penalty
minHour = float('inf')
for i in range(n + 1):
# Calculate the total penalty for closing at hour i
currPenalty = prefix[i] + suffix[i]
# Update the minimum penalty and the corresponding hour if needed
if currPenalty < minPenalty:
minPenalty = currPenalty
minHour = i
# Step 7: Return the hour with the minimum penalty
return minHour
4. Javascript Try on Compiler
/**
* @param {string} customers
* @return {number}
*/
var bestClosingTime = function(customers) {
// Step 1: Get the number of hours in the customers string
const n = customers.length;
// Step 2: Create the prefix array to store penalties for 'N's before each hour
let prefix = new Array(n + 1).fill(0);
// No penalty before the shop opens
prefix[0] = 0;
// Step 3: Create the suffix array to store penalties for 'Y's after each hour
let suffix = new Array(n + 1).fill(0);
// No penalty after the shop is fully closed
suffix[n] = 0;
// Step 4: Compute the prefix penalties for 'N's
for (let i = 1; i <= n; i++) {
if (customers[i - 1] === 'N') {
// If no customer arrives, increment penalty
prefix[i] = prefix[i - 1] + 1;
} else {
// Carry forward the penalty if customer arrives
prefix[i] = prefix[i - 1];
}
}
// Step 5: Compute the suffix penalties for 'Y's
for (let i = n - 1; i >= 0; i--) {
if (customers[i] === 'Y') {
// If a customer arrives after shop is closed, increment penalty
suffix[i] = suffix[i + 1] + 1;
} else {
// Carry forward the penalty if no customer arrives
suffix[i] = suffix[i + 1];
}
}
// Step 6: Find the hour with the minimum total penalty
// Track the smallest penalty
let minPenalty = Number.MAX_VALUE;
// Track the hour corresponding to the smallest penalty
let minHour = Number.MAX_VALUE;
for (let i = 0; i < n + 1; i++) {
// Calculate the total penalty for closing at hour i
const currPenalty = prefix[i] + suffix[i];
// Update the minimum penalty and the corresponding hour if needed
if (currPenalty < minPenalty) {
minPenalty = currPenalty;
minHour = i;
}
}
// Step 7: Return the hour with the minimum penalty
return minHour;
}
Time Complexity: O(n)
The time complexity of the solution can be analyzed by breaking down the steps involved:
We iterate over the customers string once to compute the prefix array. This step takes O(n) time, where n is the length of the customers string.
We iterate over the customers string in reverse to compute the suffix array. This also takes O(n) time.
We then loop through the arrays prefix and suffix to calculate the total penalty at each hour and determine the minimum penalty. This step takes O(n) time as well.
Total Time Complexity:
The overall time complexity is the sum of the above three steps:
- O(n) for prefix calculation
- O(n) for suffix calculation
- O(n) for finding the minimum penalty
Thus, the total time complexity of the solution is O(n), where n is the length of the customers string.
Space Complexity: O(n)
- Auxiliary Space Complexity: O(n)
The only additional space used is for the prefix and suffix arrays, both of size n+1.
Therefore, the auxiliary space complexity is O(n). - Total Space Complexity: O(n)
The input is the customers string, which requires O(n) space.We also use two arrays, prefix and suffix, each of size n+1.
Thus, the total space complexity is O(n) for the input string plus O(n) for the two additional arrays. Therefore, the total space complexity is O(n).
Can we optimise it further?
Yes! we can optimise this further.
In our previous approach, we maintained two arrays, prefix and suffix, to calculate the exact penalty for any hour. The prefix array stored the penalty before the shop closes, due to the non-arrival of customers, while the suffix array stored the penalty after the shop closes, due to the arrival of customers.
If we observe closely, the suffix array is in a non-decreasing state. This is because, as time passes, the number of customers who can arrive after a certain hour decreases.
For example, if n = 6, meaning six customers can potentially come to the shop on a given day, as we move through the hours, the number of customers who can come decreases.
Suppose at hour i = 1, only five customers can arrive after this hour. As the hour increases, the number of customers who can come continues to decrease. This means that the number of 'Y' (customers arriving) after hour i will either decrease or stay the same, resulting in a non-increasing sequence of penalties.
To break it down:
- For hour 0 (shop closed right at the start), the penalty will be the total number of 'Y' in the customers array (since no customers can arrive once the shop is closed).
- As we move to the next hour, for hour 1, the penalty will reduce because fewer customers can arrive after this hour.
- The penalty continues to decrease or remain the same as the hour shifts right, because fewer customers will arrive after the closing time is extended.
For example, consider the customers string: "YYNYNY".
- At hour 0, the penalty is 4 because four customers arrive after the shop is closed.
- At hour 1, the penalty is reduced to 3 because now only three customers can arrive after closing, and so on.
But, when we encounter an 'N', the penalty increases because the shop remains open, yet no customer arrives.
So, we can start by calculating the total penalty caused by the arrival of customers 'Y' after the shop is closed before the 0th hour.
As we traverse through the customers array, we gradually extend the shop's closing time. When we encounter a 'Y', we reduce the penalty because the shop is now open for that customer.
Conversely, if we encounter an 'N', we increase the penalty because the shop remains open, but no customer arrives.
In this way, we can calculate the penalty dynamically as we move through the hours without having to recompute it for every hour from scratch.
How can we do it?
Here’s how we can do it:
We can create a variable penalty that initially calculates the number of 'Y' in the customers string. This represents the penalty for hour 0 (when the shop is closed immediately).
As we traverse through the string, the penalty decreases when we encounter a 'Y' because the shop's closing time is extended (the shop will close after the i-th index).
However, when we encounter a 'N', we increase the penalty because the shop is still open, and no customers have arrived.
At each index, we check if the current penalty is the minimum we’ve encountered so far.
At the end, we return the hour that corresponds to the minimum penalty encountered. This approach allows us to dynamically adjust the penalty as we move through the hours without needing to recompute the penalty from scratch each time.
Note: As we are assuming the shop is open at the i-th hour, we will set minHour to i + 1 in each iteration, since the shop is open for that index and closes after that index (after the i-th hour). This adjustment ensures we account for the fact that the shop will close at the end of each hour.
Let's understand with example:
Let's perform a concise dry run of the approach on the customers string: "YYNYNY".
Initialization:
- penalty = 4 (because there are 4 'Y' in the string, which represents the penalty for closing at hour 0).
- minPenalty = 4 (initially set to penalty for hour 0).
- minHour = 0 (hour 0 is the starting point).
Iterating through the string:
- Hour 0:
- Encounter 'Y', penalty decreases by 1 (penalty = 3).
- minPenalty = 3 (updated since the new penalty is lower).
- minHour = 1 (set to i + 1 for i = 0), (hour 1 is the new minimum).
- Hour 1:
- Encounter 'Y', penalty decreases by 1 (penalty = 2).
- minPenalty = 2 (updated since the new penalty is lower).
- minHour = 2 (set to i + 1 for i = 1), (hour 2 is the new minimum).
- Hour 2:
- Encounter 'N', penalty increases by 1 (penalty = 3).
- minPenalty remains 2 (no change).
- minHour remains 2.
- Hour 3:
- Encounter 'Y', penalty decreases by 1 (penalty = 2).
- minPenalty remains 2 (no change).
- minHour remains 2.
- Hour 4:
- Encounter 'N', penalty increases by 1 (penalty = 3).
- minPenalty remains 2 (no change).
- minHour remains 2.
- Hour 5:
- Encounter 'Y', penalty decreases by 1 (penalty = 2).
- minPenalty remains 2 (no change).
- minHour remains 2.
Final Result:
- minHour = 2, which corresponds to the hour with the minimum penalty, so the answer is minHour.
Thus, the shop should close at hour 2 to minimize the penalty.
Code Implementation
1. C++ Try on Compiler
class Solution {
public:
int bestClosingTime(string customers) {
// Step 1: Get the total number of customers ('Y') in the customers string.
int n = customers.length();
// Step 2: Initialize minHour to store the best closing hour (starting at 0).
// Initialize penalty as the total number of 'Y' customers (penalty for closing at hour 0).
int minHour = 0;
int penalty = count(begin(customers), end(customers), 'Y');
// Step 3: Set minPenalty to the initial penalty at hour 0.
int minPenalty = penalty;
// Step 4: Loop through the customer string to check the penalty for each closing hour.
for (int i = 0; i < n; i++) {
// Step 5: If a customer arrives ('Y'), reduce the penalty since we are moving closer to the shop closing time.
// If no customer arrives ('N'), increase the penalty as the shop is still open and no customer arrives.
if (customers[i] == 'Y') {
penalty--;
} else {
penalty++;
}
// Step 6: Check if the current penalty is less than the minimum penalty encountered so far.
// If it is, update minHour and minPenalty to the current hour and its corresponding penalty.
if (penalty < minPenalty) {
minHour = i + 1; // Update minHour to i + 1 because the shop closes after the i-th hour.
minPenalty = penalty;
}
}
// Step 7: Return the hour with the minimum penalty.
return minHour;
}
};
2. Java Try on Compiler
class Solution {
public int bestClosingTime(String customers) {
// Step 1: Get the total number of customers ('Y') in the customers string.
int n = customers.length();
// Step 2: Initialize minHour to store the best closing hour (starting at 0).
// Initialize penalty as the total number of 'Y' customers (penalty for closing at hour 0).
int minHour = 0;
int penalty = 0;
for (int i = 0; i < n; i++) {
if (customers.charAt(i) == 'Y') {
penalty++;
}
}
// Step 3: Set minPenalty to the initial penalty at hour 0.
int minPenalty = penalty;
// Step 4: Loop through the customer string to check the penalty for each closing hour.
for (int i = 0; i < n; i++) {
// Step 5: If a customer arrives ('Y'), reduce the penalty since we are moving closer to the shop closing time.
// If no customer arrives ('N'), increase the penalty as the shop is still open and no customer arrives.
if (customers.charAt(i) == 'Y') {
penalty--;
} else {
penalty++;
}
// Step 6: Check if the current penalty is less than the minimum penalty encountered so far.
// If it is, update minHour and minPenalty to the current hour and its corresponding penalty.
if (penalty < minPenalty) {
minHour = i + 1; // Update minHour to i + 1 because the shop closes after the i-th hour.
minPenalty = penalty;
}
}
// Step 7: Return the hour with the minimum penalty.
return minHour;
}
}
3. Python Try on Compiler
class Solution:
def bestClosingTime(self, customers):
# Step 1: Get the total number of customers ('Y') in the customers string.
n = len(customers)
# Step 2: Initialize minHour to store the best closing hour (starting at 0).
# Initialize penalty as the total number of 'Y' customers (penalty for closing at hour 0).
minHour = 0
penalty = customers.count('Y')
# Step 3: Set minPenalty to the initial penalty at hour 0.
minPenalty = penalty
# Step 4: Loop through the customer string to check the penalty for each closing hour.
for i in range(n):
# Step 5: If a customer arrives ('Y'), reduce the penalty since we are moving closer to the shop closing time.
# If no customer arrives ('N'), increase the penalty as the shop is still open and no customer arrives.
if customers[i] == 'Y':
penalty -= 1
else:
penalty += 1
# Step 6: Check if the current penalty is less than the minimum penalty encountered so far.
# If it is, update minHour and minPenalty to the current hour and its corresponding penalty.
if penalty < minPenalty:
minHour = i + 1 # Update minHour to i + 1 because the shop closes after the i-th hour.
minPenalty = penalty
# Step 7: Return the hour with the minimum penalty.
return minHour
4. Javascript Try on Compiler
/**
* @param {string} customers
* @return {number}
*/
var bestClosingTime = function(customers) {
// Step 1: Get the total number of customers ('Y') in the customers string.
let n = customers.length;
// Step 2: Initialize minHour to store the best closing hour (starting at 0).
// Initialize penalty as the total number of 'Y' customers (penalty for closing at hour 0).
let minHour = 0;
let penalty = 0;
for (let i = 0; i < n; i++) {
if (customers[i] === 'Y') {
penalty++;
}
}
// Step 3: Set minPenalty to the initial penalty at hour 0.
let minPenalty = penalty;
// Step 4: Loop through the customer string to check the penalty for each closing hour.
for (let i = 0; i < n; i++) {
// Step 5: If a customer arrives ('Y'), reduce the penalty since we are moving closer to the shop closing time.
// If no customer arrives ('N'), increase the penalty as the shop is still open and no customer arrives.
if (customers[i] === 'Y') {
penalty--;
} else {
penalty++;
}
// Step 6: Check if the current penalty is less than the minimum penalty encountered so far.
// If it is, update minHour and minPenalty to the current hour and its corresponding penalty.
if (penalty < minPenalty) {
minHour = i + 1; // Update minHour to i + 1 because the shop closes after the i-th hour.
minPenalty = penalty;
}
}
// Step 7: Return the hour with the minimum penalty.
return minHour;
};
Time Complexity: O(n)
Counting the total number of 'Y' in the customers string using customers.count('Y') or its equivalent, takes time Complexity of O(n), where n is the length of the customers string. This is because we iterate through the string once to count all occurrences of 'Y'.
Looping through the customers string and adjusting the penalty at each index, take time Complexity of O(n), because we iterate over the entire string once, performing constant time operations (checking the character and updating the penalty).
The loop for calculating the penalty and finding the minimum penalty for each closing hour is O(n), as we iterate through the string once.
Therefore, the overall time complexity is:
O(n) + O(n) = O(n)
Where n is the length of the customers string.
Space Complexity: O(n)
- Auxiliary Space Complexity: O(1)
We are using a constant amount of extra space for variables like minHour, penalty, minPenalty, and the string itself, which takes O(1) additional space. - Total Space Complexity: O(n)
The space required for storing the input string customers is O(n).
Thus, the overall space complexity is O(n) due to the input string.
Learning Tip
Now we have successfully tackled this problem, let's try these similar problems.
You and a gang of thieves are planning on robbing a bank. You are given a 0-indexed integer array security, where security[i] is the number of guards on duty on the i-th day. The days are numbered starting from 0. You are also given an integer time.
The i-th day is a good day to rob the bank if:
- There are at least time days before and after the i-th day.
- The number of guards at the bank for the time days before i are non-increasing, and
- The number of guards at the bank for the time days after i are non-decreasing.
More formally, this means day i is a good day to rob the bank if and only if:
- security[i - time] >= security[i - time + 1] >= ... >= security[i]
- security[i] <= ... <= security[i + time - 1] <= security[i + time]
Return a list of all days (0-indexed) that are good days to rob the bank. The order that the days are returned in does not matter.
You are given an integer array nums sorted in non-decreasing order.
Build and return an integer array result with the same length as nums such that result[i] is equal to the summation of absolute differences between nums[i] and all the other elements in the array.
In other words, result[i] is equal to sum(|nums[i]-nums[j]|) where 0 <= j < nums.length and j != i (0-indexed).