New 21 Game - Leetcode 837 - Python

Solving leetcode 837 - New 21 Game, today's daily leetcode problem on may 24.
🚀 neetcode.io/ - A better way to prepare for Coding Interviews
🥷 Discord: / discord
🐦 Twitter: / neetcode1
🐮 Support the channel: / neetcode
⭐ BLIND-75 PLAYLIST: • Two Sum - Leetcode 1 -...
💡 DYNAMIC PROGRAMMING PLAYLIST: • House Robber - Leetco...
Problem Link: leetcode.com/problems/new-21-...
0:00 - Read the problem
0:50 - Non-optimal explanation
5:45 - Non-optimal code
8:30 - Optimal Explanation
13:52 - Optimal code
leetcode 837
#neetcode #leetcode #python

[@MgThompson]

I might think that, if the interviewer comes up with this problem, I will be sure they don't want to hire you.

[@NeetCodeIO]

Yeahhhh, this is what I call a crackhead problem..

[@dadhx8]

At first I thought there was some "simple" solution using Bayes theorem, but as I thought about it more, I realized I had no clue wtf to do lol

[@dorothychristina2721]

Could you share some insights on how you break the problem, gather inputs from the problem statement ,say your approach as you go about when you see this kind of problems ?

[@yolo3659]

Tip: You can also use a queue instead of a dp array to make life easier. Just initially push the required amount of zeroes and ones and push the subsequent probabilities into the queue while popping the front elements. In the end since we have to return dp[0] in the normal implementation, we have to return the last element in the queue. Here is the C++ code. Note here window_sum is named as sums for simplicity. And max_points is renamed as maxs double new21Game(int n, int k, int maxs) { if((k-1+maxs)=k;i--){ if(i

[@uptwist2260]

this was scary. thanks for the daily

[@MrKB_SSJ2]

Yoooooooo THANK YOUUUUU FOR MAKING THIS RIGHT NOW

[@sreesaiaditya2574]

Thank you. I really understood this problem and it is clearly explained.

[@DarkOceanShark]

I have been thinking about the solution in the same decision tree based approach like you, where I counted the number of solutions that give me value from k to n and, the number of solutions that give you a value of above or equal to k after previously being below k. I divided the former by latter and returned it as the answer. First and second passed but the third sample test case failed. I have realised the mistake now.

[@devMarcus]

I haven't watched any really recent videos because I have been on break but has NeetCode always used a csgo crosshair for drawing?

[@itachid]

How am I supposed to come up with this in an interview?

[@infernape716]

Pray

[@MoazMahmud]

I solved it the exact same way! I used the math formula you were talking about. Which is: windowSum = min(maxPoint, n - k + 1)

[@johnnychang3456]

Can you explain the formula? Thanks

[@LarryFisherman5]

@@johnnychang3456 Basically, the n - k + 1 part is counting how many ones we have at initialization, since we have ones from k up to n, and then onwards it's all 0s. However, if maxPts is less than n - k + 1, we can't reach those 1s which are beyond k + maxPts, so they shouldn't be included in the window sum. But note that this can only happen when k + maxPts

[@MoazMahmud]

@@LarryFisherman5 This is a great explanation 😃

[@akashuday7107]

wait why arent you uploading on the Neetcode official channel/?

[@Kan-JenLiu]

dangg..... this problem is just crazy...

[@ashishdhal4614]

I solved it using dp first i multiplied the probability of that number with a recursive call then added all recursive calls formed by the max value loop . After watching the sliding window technique I feel stupid😢😢

[@deadlyecho]

Shouldn't the probability of the non optimal solution be O(m^k)? Since the depth of the tree is of magnitude of order k?

[@himanshubarnwal1527]

we can optimize it by using 2d dp of n*k size. So, it will be O(n*k).

[@YashVashistha-ot5ux]

Please do the contest problems for each contest the hard ones atleast

[@dark_all_day9311]

I got asked this in an MLE interview with 20 mins to solve it 😔 been an MLE for 3 years built out and scaled many pipelines, never needed anything close to the knowledge required for a problem like this one. they rly set me up to fail lol

[@CS_n00b]

would the recursive solution have been enough?

[@ouchlock]

for testcase n=1 k=0 maxPts=2 as we have [1,2] where only 1 is

[@NeetCodeIO]

Not true. If we start at 0 and k is 0, then we can't draw any cards.

[@ouchlock]

@@NeetCodeIO yes, you're right, thanks

[@HelloWorld-lh1wk]

well a good way to solve this problem in a interview is to click the end meeting button....

[@harshmankodiya9397]

why avg?

[@NeetCodeIO]

Like I mentioned, if each branch has an equal probability, that implies we average.

[@shashivish2022]

Code does not works for Python 2 but works for Python3.

[@NeetCodeIO]

Yes, that's because I'm using python3. No one really uses python2 anymore.

[@chrisliu6444]

@@NeetCodeIO why is python2 not working but python3 working tho?

[@ccx0040]

Wrote this in C++ but it's not running, please help me figure out the problem double new21Game(int n, int k, int maxPts) { vectordp(n + 1, 0); for(int i = k; i

[@shishankrawat2105]

if(i+maxPts < k) remove = dp[i+maxPts] else if(i+maxPts

[@Amit-fn7bw]

Giving wrong answer on n = 185 , k = 183 , m = 2, correct output = 1, giving 62.1111 class Solution { public: double helper(int n, int k , int m, int pts){ if(pts >= k) return (pts

[@solutionscorner]

class Solution { public: double new21Game(int n, int k, int maxPts) { vector dp(n+1,0); double window_sum = 0; if(k == 0 || n >= k + maxPts) { return 1.0; } for(int i = k; i= 0; i--) { dp[i] = (double) window_sum/maxPts; double del = 0; if(i + maxPts

[@notgreen11]

is this one really that hard? seemed like a very easy DP problem when I first tried it, you’ve done many harder problems IMO so i’m surprised w your grading

[@reactionchamber]

relatively easy to come up with the recursive solution, but recognizing how to use a sliding window is quite a stretch imo

[@meowmaple]

ur mum's easier