Student Attendance Record II - Leetcode 552 - Python

🚀 neetcode.io/ - A better way to prepare for Coding Interviews
🧑‍💼 LinkedIn: / navdeep-singh-3aaa14161
🐦 Twitter: / neetcode1
⭐ BLIND-75 PLAYLIST: • Two Sum - Leetcode 1 -...
Problem Link: leetcode.com/problems/student...
0:00 - Read the problem
3:25 - Intuition
6:59 - Math Explanation
16:38 - Coding Recursive
24:18 - Coding DP
leetcode 552
#neetcode #leetcode #python

[@NeetCodeIO]

hope you guys like watching this video as much as i enjoyed making it

[@jensenzhang2452]

neetcode i love you

[@NeetCodeIO]

i love you too

[@md_pedia1]

was waiting for this video 🔥🔥

[@yang5843]

I'm walking out of the interview

[@joydeeprony89]

because of you Navdeep Paji I can solve medium problems now.

[@oldmajor5240]

Great Video! I solved this problem in a similar fashion but I did the induction over sequences ending in pl, lp, ll and pp. I also had to implement additional logic to take care of the first condition, leading to a linear space solution. Awesome to see it can also be done in constant space! 🔥

[@ajayprabhu465]

content quality 100% my understanding 80% implementation 50%

[@ritikaagrawal769]

OMG this solution was brilliant! I kept scratching my head over how to make new states from previous states. I thought there are 6 states and for every state we have three options so, 18 steps to finally have new dp. But you boiled it down to seven lines. It was really good!

[@PreetamSahu-zr2qg]

As expected, the best solution is here

[@karimitani8024]

I love you , my initial thought process was to come up with a math formula but i had a hard time with that, but here comes neet codeeee u made my life eaiser !

[@aashishbathe]

Correct me if I'm wrong, but i think in this problem, the cache isn't relevant fir a particular testcase, but for further testcases, like if we calculate and cache for 3, then for 4, we only need 1 computation. Is that right?

[@naive_algorithm]

I used recursive lambda function in c++ and was getting TLE, but global function solved the problem why?

[@chien-yuyeh9386]

Really interesting 🤩

[@sidhartheleswarapu]

About to have my Coinbase final round interviews in a few days. They said it wasn't going to be like Leetcode 😅, so not sure the best way to prepare. Any advice?

[@mrvinyllad25]

tried to solve this through combinatorics.. but didn't pay attention to the constraint of n

[@dingus2332]

Code does not seem to run now

[@mukeshrawat1304]

@Neetcode literally simps over Math 😁 I am just worried that this guy could inherit some of his Math skills to us as well 😟

[@meemee417]

this one really reminded me of knight dialer

[@sachinwalunjakar8854]

Firstly, thank you for your hard work. I have a suggestion: starting with a top-down approach and then moving to a bottom-up approach might make things easier to understand

[@PhanNghia-fk5rv]

yah, i once read a solution that a guy told that we should start with recursion -> recursion with memorization top down -> iterative with momorization bottom up. It help me alot then.

[@sachinwalunjakar8854]

@@PhanNghia-fk5rv yes, you are right.

[@abhinavkumar4375]

Can someone explain why are we even using cache as we will go through a number n only once like count(4) -> count(3) -> count(2) -> count(1) at count 1 we got the matrix after that we update the cache val for 2 , 3 , 4 how are we reusing it . Please someone correct if i am thinking wrong .

[@NeetCodeIO]

Now that you mention it I think you're right. My brain was just on auto pilot, I think it works without caching

[@abhinavkumar4375]

​@@NeetCodeIO yes just ran it and it works .thanks for the video and for the great explanation .

[@rev_krakken70]

I solved this using 3D dp, it was 1D but other dimensions were 2 and 3.. bruh.. i am so naive.. Dp is really tough 😢

[@devin9544]

Can you do the daily leetcode questions?

[@iamabominable7462]

HI BRO

[@gabrielvrldev]

Great video! What is the software you use to draw and explain the problem?

[@ilovenaturesound5123]

He mentioned that he used Paint and mouse to draw. I think it's the video called "Yes, I was also Bad at LeetCode"

[@gabrielvrldev]

@@ilovenaturesound5123 thanks

[@Antinormanisto]

My confidence fell

[@inderlalchandani]

Next level thinking how I can develop this level of thinking 😢

[@deathbombs]

Just take my daily streak......

[@aloha9938]

How am i getting TLE with this solution, it's the same thing class Solution: def checkRecord(self, n: int) -> int: pre = [[1,1,0], [1,0,0]] next = [[0]*3 for i in range(2)] for i in range(2,n+1): next[0][0] = pre[0][0] + pre[0][1] + pre[0][2] next[0][1] = pre[0][0] next[0][2] = pre[0][1] next[1][0] = pre[0][0] + pre[0][1] + pre[0][2] + pre[1][0] + pre[1][1] + pre[1][2] next[1][1] = pre[1][0] next[1][2] = pre[1][1] pre = next next = [[0]*3 for i in range(2)] res = 0 for l in pre: res += sum(l) % (10**9 + 7) return res % (10**9 + 7)

[@greatfate]

bro how is this constant space complexity if you have caching man

[@NeetCodeIO]

second solution doesnt have caching

[@greatfate]

@@NeetCodeIO oh shit fairs man

[@chaitanyasharma6270]

class Solution { int n; int mod=1000000007; Long dp[][][]; public int checkRecord(int N) { n=N; dp=new Long[n+1][2][3]; long c=dfs(0,0,0); return (int)(c%mod); } public long dfs(int i, int countA, int consL){ if(i>=n){ return 1; } if(dp[i][countA][consL]!=null) return dp[i][countA][consL]; long a=0; long l=0; long p=0; if(countA

[@muscleman6473]

Neetcode cooked again like he said he would

[@Sunil_Chandurkar]

Is anybody getting Coding Interviews?

[@ritikaagrawal769]

No bruh, but if you want to practice with mock interviews, i am looking for help too, maybe we can help each other?

[@ritikaagrawal769]

This one solution literally made me simp over you. **facepalm**

[@dingus2332]

MOD = 10**9 + 7 cache = {} def count(n): if n == 1 : #A , L (consecutive) return { (0, 0) : 1 , (0, 1): 1 , (0, 2) : 0 , (1, 0) : 1 , (1, 1): 0 , (1, 2) : 0 } if n in cache : return cache[n] tmp = count(n - 1) res = defaultdict(int) #Choose P res[(0 , 0)] = ((tmp[(0, 0)] + tmp[(0, 1)]) % MOD + tmp[(0, 2)]) % MOD res[(1 , 0)] = ((tmp[(1, 0)] + tmp[(1, 1)]) % MOD + tmp[(1, 2)]) % MOD #Choose L res[(0, 1)] = tmp[(0 , 1)] res[(1, 1)] = tmp[(1 , 0)] res[(0, 2)] = tmp[(0 , 1)] res[(1, 2)] = tmp[(1 , 1)] #Choose A #ignore sec row , because a needs to be fewer than 2 res[(1, 0)] = (res[(1,0)] + (((tmp[(0, 0)] + tmp[(0, 1)]) % MOD + tmp[(0, 2)])) % MOD) % MOD cache[n] = res return res return sum(count(n).values()) % MOD why my code not running plz help

[@pritz9]

How about this recursion+cache ? This is lot easier conceptually I believe! class Solution: def checkRecord(self, n: int) -> int: MOD = 10**9 + 7 dp = [[[-1 for _ in range(3)] for _ in range(2)] for _ in range(n + 1)] def rec(i, a_count, l_count): if i == n: return 1 if dp[i][a_count][l_count] != -1: return dp[i][a_count][l_count] count = 0 count += rec(i + 1, a_count, 0) if a_count < 1: count += rec(i + 1, a_count + 1, 0) if l_count < 2: count += rec(i + 1, a_count, l_count + 1) dp[i][a_count][l_count] = count % MOD return dp[i][a_count][l_count] return rec(0, 0, 0)

[@kamilrudny1884]

Is it working? I was geeting time limit exceeded error

[@pritz9]

@@kamilrudny1884 yess, its working fine. I think u missed some condition maybe. Its beating 35% submissions.

[@stevjobs786]

Hello Neetcode ! I love the way you explain the Leetcode problems, but the issues is sometimes you talk too much so we are not able to follow the exact concept to solve the problem ... So what I'm try to say is, if you can give directly the optimized solution without explaining the brute force solution because it becomes heavy to follow(just keep simple and direct). Thank you for your consideration and keep the great work !

[@ritikaagrawal769]

for that you have the option to just press forward key on the video, let him speak so the likes of us can understand!