Minimum Penalty for a Shop - Leetcode 2483 - Python

[@dumbfailurekms]

man if you ever decide to go back to working as a regular SWE you'll be like the final boss for interviewers ......

[@leeroymlg4692]

an easier solution would be to keep track of the penalty. The penalty starts off as the amount of Y's in the string. And for every Y you come across, the penalty drops by 1. For every N you come across, the penalty increases by 1. Then you just return the index + 1 of the smallest penalty def bestClosingTime(self, customers: str) -> int: p = customers.count('Y') res = [p, 0] #penalty, hour for i, c in enumerate(customers): if c == 'Y': p -= 1 else: p += 1 if p < res[0]: res[0] = p res[1] = i + 1 return res[1]

[@souryadeepbhattacharya1984]

Please go through the O(1) space solution. Thanks.

[@hobo9968]

For the optimized solution, you can realize that there are only two options, a Y or N. Meaning if I know the count of one, I can infer the count of the other. That way you can use one loop to get the count and another to repeat the same calculations done in this solution. Another optimized solution is done in one pass. For that, if you look at the patterns of the total score in the array, prefix_n[i] + postfix_y[i], you'll notice that the score either goes up every time there's a Y, or drops every time there's an N. With this realization, you can simply increment or decrement the score based on whether the current char is a Y or X and the earliest index with the minScore is the answer.

[@amidofulue6205]

For the O(1) space method, I guess we just calculate the total amount of Y first, then in the loop of finding the min penalty, we can get the postfix sum of Y by subtracting the amount of Y we met so far from the total amount of Y

[@coldsky_]

Legend 😎 You can also iterate through the array twice, the first time counting the number of Ys and the second calculating the penalty at each idx.

[@sanooosai]

constant memory, linear time def bestClosingTime(self, customers: str) -> int: # first get the max penalty if close at 0 hrs mp=0 for p in customers: if p=='Y': mp+=1 h=0 ansh=0 minp=mp # now we need min penalty with early closure for p in customers: if p=='Y': mp-=1 else: mp+=1 h+=1 if minp>mp: minp=mp ansh=h return ansh

[@anlee728]

Love your video all the time !!! you help me learn so much!! I hope can see the other video to discuss it, and want to share my understanding of the solution on LeetCode : ) For the space: O(1) solution on the leetCode's editorial took me a long time to figure out: class Solution: def bestClosingTime(self, customers: str) -> int: """ 1. Assume we close at the 0 hour, how many penalties should we have (initial val) 2. Iterate the customers, use current status(Y/N) to calculate the penalty of next hour """ curr_p = p = customers.count('Y') close_hr = 0 for i, c in enumerate(customers): # if we close at next hour, this Y reduce our penalty # cause in open hour's, Y is safe (no penalty) if c == "Y": curr_p -= 1 else: curr_p += 1 # update the minimum penalty and close_hr if curr_p < p: p = curr_p # we are talking about the next hour close_hr = i + 1 return close_hr

[@AyushSachan2211]

please explain all approach. i was able to come up with this solution myself but unable to understand the intuition behind the more better/complex solution.

[@committedeel1751]

Nice! I feel like you could still do this in one pass though but working towards building that optimal solution with O(n) time complexity

[@6kostia]

My Solution: class Solution: def bestClosingTime(self, customers: str) -> int: n, res, res_time = len(customers), 10**6, 0 current_y, total_y = 0, customers.count('Y') for i in range(n+1): # if we close at time i, the penealty will be all # N times until now and Y times after now penalty = (i - current_y) + (total_y - current_y) if penalty < res: res, res_time = penalty, i if i < n and customers[i] == 'Y': current_y += 1 return res_time

[@piyushdubey_]

Hey @neetcode - curious what is your setup for writing on the screen? Do you use any stylus or sth else?

[@lazyGladiator]

Use Kadane's but don't reset the max, one pass with constant memory

[@sharabugnanesh3098]

can you share the code if you got solved?

[@intelegixlabs]

class Solution: def bestClosingTime(self, customers: str) -> int: penalty = customers.count("Y") global_penalty = penalty close_index = 0 for i in range(1, len(customers)+1): if customers[i-1] == "Y": penalty -= 1 if global_penalty > penalty: global_penalty = penalty close_index = i else: penalty += 1 if global_penalty > penalty: global_penalty = penalty close_index = i return close_index

[@ChristForAll-143]

dude, you keep on posting new questions which u r making tuff for already working professional to pratice more and more I would rather suggest u to show case the pattern and how n of problems are falling into that pattern, because u r gng get infinity problems gng forward there is no point solving all 2k or 3k leetcode prblms quality over quantity Its my humble request since u r content is so good, i hope you read my comment

[@biplabsarkar3567]

Dude you wake up early in the morning then solve the potd and upload it, salute

[@MP-ny3ep]

Great explanation as always. Thank you!

[@uptwist2260]

Thanks for the daily

[@sanooosai]

thank you sir

[@juliuskingsley6212]

my 10 lines O(1) space solution (Python3) class Solution: def bestClosingTime(self, customers: str) -> int: curr = customers.count("N") currMin = curr ans = len(customers) for i in range(len(customers) - 1, -1, -1): curr += 1 if customers[i] == "Y" else -1 if curr

[@DevvOscar]

What does he use for the image and drawing?This setup helps so much for my thought prpcess

[@scykl3]

mspaint works, just screenshot the question and paste it into a blank canvas to start

[@DevvOscar]

@@scykl3 well this was anticlimactic.. don’t know what I was expecting. But thanks that works.

[@sharabugnanesh3098]

please explain another approach too!

[@chrisrectenwald7307]

Why the change to c++

[@amir78989]

that was just one of the selections for programming languages for his new problem solver feature on his website.