Yeah, I'm walking out the interview if I get this question

Didn't they use to put the hard problems at the end of the month?

@raunakgiri21

6 ай бұрын

Now it's probably weekends too

@zaki_1337

6 ай бұрын

no they used to do that every weekend before Festival season (December).

@salim444

6 ай бұрын

​@@zaki_1337cool profile photo bro

@Strikas_shroud

6 ай бұрын

Weekend hard mode lol 😆

@krishnakanthati8510

6 ай бұрын

I think it would be useful to show you working through a dfs solution and telling us where you get stuck

@sdmfslkdm

6 ай бұрын

class Solution { public: int dp(vector& nums, int ind, long long diff, int prev, int cnt) { if (ind >= nums.size()) { return 0; } int pick = 0; if (cnt if (cnt == 1) { pick = dp(nums, ind + 1, static_cast(nums[ind]) - static_cast(nums[prev]), ind, cnt + 1); } else { pick = dp(nums, ind + 1, diff, ind, cnt + 1); } } else if (static_cast(nums[ind]) - static_cast(nums[prev]) == diff) { pick = 1 + dp(nums, ind + 1, diff, ind, cnt + 1); } int notPick = dp(nums, ind + 1, diff, prev, cnt); return pick + notPick; } int numberOfArithmeticSlices(vector& nums) { return dp(nums, 0, 0LL, 0, 0); } }; if you use vector memoisation , you will get mle and if you use map and store the key it will still give tle

I was stuck on how to calculate a 3-element subsequence in 1 hour, and boom, you were there, exploding my mind! The subtracting approach is intelligent. Thanks.

Thank you, was waiting for it. ❤

Great explanation, thank you !

Amazing explanation. Thank you

Thanks, good explanation.

I gave up on this question

Great explanation

great, thank you

at 18:03 would not putting putting res after the end of the for loop result in a bug ( if somehow we managed to), cause it will only the add last difference result? or I am missing something.

Thank youuuu!!!! YOU AREEE THE BESTTTT!!!!

Bro, please consider explaining in following order: recursion -> memoization -> tabulation -> space optimization , it will be more helpful.

One day I hope I can solve questions like this

Easy DFS Solution but TLE: n = len(nums) @cache def dfs(i, diff): # if i == n: # return 0 ans = 0 if diff == float('inf'): # sequence not started for j in range(i+1, n): # start with all differences possible ans += dfs(j, nums[j]-nums[i]) # explore with each else: # sequence started for j in range(i+1, n): if nums[j] - nums[i] == diff: # find next element ans += 1 + dfs(j, diff) # explore after incremenenting return ans res = 0 for i in range(n): res += dfs(i, float('inf')) return res

@cinimodmil

6 ай бұрын

does ur solution TLE because its TC is n^3? just a wild guess. i might be wrong, please correct me if so, thank you!

@zaki_1337

6 ай бұрын

@@cinimodmil I’m probably less knowledgeable than you. No idea if it’s n^3. ChatGPT said it’s 2^n 💀

Thank you for your explanation, it did help me a lot. Literally GENIUS!

Yeah... It's dp and I spent some time drawing a decision tree. However counting for a sub sequence of length 2 felt like unnecessary extra work to remember/account for later and then solving from top to bottom in the case didn't look intuitive at all *to me*.... Regardless, great solution! I'd definitely need to be more flexible with how I think about and work with decision trees especially the question about the sub problems I'm actually looking for.

@NeetCodeIO There was a part that was cut off at 16:50 FYI

great solution and explanation. I did the brute way memoization.

@EasterBunnyGaming

6 ай бұрын

how did u do memoisation ? what were the keys

@BROOKnim

6 ай бұрын

@@EasterBunnyGaming the same. difference and the starting index of subsequence

What does it mean when one says "ending here" , does it mean that we need to include the element at that index in the subsequence ?

at 13:21 states that 20 is the number of combinations. However, isn't 20 the number of permutations st [6,2] is different than [2,6]. The number of length 2 permutations of 5 elements: (5!)/(3!) = 20 If we count the number of combinations of length 2 of 5 elements we get 5 choose 2 --> (5!)/(2! x 3!) = 10. Since order doesn't matter, and for each of these combinations one element comes before the other, each are valid subsequences. Cheers

@NeetCodeIO

6 ай бұрын

Yeah that's exactly right, there are more permutations than combinations.

since the number of diff elements are coming from every possible pair of combination of elements wouldn't the total time complexity be n^3 as total number of diff would be n^2? do verify if i am wrong

Kept awake till 6 AM solving this, utilised a helper function for Arithmetic Progression, only the test cases with 0 difference between some elements were giving wrong answers, specifically 21/101 [0,1,2,2,2]. Lost the streak. Also sleep.

My approach was to find the maximum length of subsequence of length diff (then counting subsequence using maths also for diff 0 i use to calculate using 2^n - 1 - n - (n*(n+1))/2) but the problem was with double occurence of the elements. my algo would fail for [2,4,6,6,8,10]

@tasneemayham974

6 ай бұрын

I think we should consider combinations here. nC2 gives the correct answer. like 5C2 == 10 hence for nCr (n! / (r! * (n-r)!)) --> this could then be simplified to n(n-1)/2.

@zweitekonto9654

6 ай бұрын

Even i thought the same thing. But why wouldn't it work here? The algo would still find 2,4,6,8,10 with diff 2 and 6,6 with diff 0 as the largest arithmetic sequence.

Thank you, good explanation. I just didn't get that part where you subtracted n(n-1)/2. Can someone help???

@capecrusader2709

6 ай бұрын

Now, that's a concept from permutation and combination. If we take 5 elements and want combination of 2, then we do 5C2 which turns out to be 5! / (2! * (5-2)!), which is equal to 5! / (2! * 3!), now factorial formula for n! = n*(n-1)! and 0! = 1. So, 5!/ (2! * 3!) = 5*4*3! / (2! * 3!), cancelling out 3! from above and below, we get (5*4)/ (2!), now 2! is 2*1*0 = 2, again simplifying we get, (5*4) / 2 == 10, which is n*(n-1) / 2. I know that from youtube comment section, its hard to understand but do check out combination theory. Thank you

@pragyantripathi3979

6 ай бұрын

@@capecrusader2709 got the combination concept. So basically we are subtracting all 2length subsequences from the total subsequences which are >= 2. Thank you

What happened at 16:58? It seems we lost a piece of explanation

id rather get problems like these all month honestly its actually challenging and you'd be much better at dsa even if you didnt solve a single problem on your own atleast you tried

I tried to do recursion and cache, but I got TLE. When I reduce the number of arguments, caching gives incorrect results. When I have 3 argument variables, caching gives correct results. However, the second last test case give TLE :(

@tasneemayham974

6 ай бұрын

Notice, we have two for loops for i and diff which means the memoization should be with 2 variables. So work on that more.

@mire5234

6 ай бұрын

@@tasneemayham974 I certainly tried that, too. If I don't do cache, the results are correct but TLE. If I do cache, the results are incorrect. Do you have any ideas? from functools import cache class Solution: def numberOfArithmeticSlices(self, nums: List[int]) -> int: n = len(nums) ans = [] # @cache def backtrack(right,diff): if right == len(nums): if len(curr) >= 3: return 1 return 0 res = 0 if len(curr) >= 3: res += 1 for k in range(right,n): if nums[k] - nums[right-1] == diff: curr.append(nums[k]) res += backtrack(k+1,diff) curr.pop() return res res = 0 for i in range(n-2): for j in range(i+1,n-1): curr = [nums[i],nums[j]] res += backtrack(j+1,nums[j]-nums[i]) return res

I'm not skilled enough to come up with a solution by myself. And reading the "Editorial" section is also a quiet challenging for me - it takes hours to understand the idea through the text. Does anyone also see that LeetCodes's text explanation is more difficult than video? @NeetCodeIO Thank you for your video tutorials, your explanation is simple and understandable.

@ngocnb52

6 ай бұрын

I think it's badly written.

@vinayjangra1401

6 ай бұрын

the editorial for this problem is premium ;)

@user-bf7yz3qd2i

6 ай бұрын

Go learn Dp form striver , you will be skilled enough to think about the solution.

me, new with only easies done, trying to understand this solution:

Bro, you gotta teach discrete mathematics and combinatorics as well, please!

I got the Recursive code correct but its giving TLE. Here's the code : #define ll long long class Solution { int n; public: int f(int i, int a0, int a1, int cnt, vector& nums) { if(i == n) return (cnt >= 3); int notPick = f(i+1, a0, a1, cnt, nums); int pick = 0; if(a0 == -1 || a1 == -1 || (ll)nums[i]-(ll)nums[a1] == (ll)nums[a1] - (ll)nums[a0]) { pick = f(i + 1, a1, i, cnt + 1, nums); } return pick + notPick; } int numberOfArithmeticSlices(vector& nums) { n = nums.size(); return f(0, -1, -1, 0, nums); } };

@pranavsharma7479

6 ай бұрын

is this correct memoization solution, the test cases are failing dont know where class Solution { public int helper(int idx, int prev1, int prev2, int count, int nums[],int dp[][][]){ if(idx == nums.length){ if(count >= 3) return 1; return 0; } if(dp[idx][prev1+1][prev2+1] != -1) return dp[idx][prev1+1][prev2+1]; //not pick int not_pick = helper(idx+1,prev1,prev2,count,nums,dp); //pick int pick = 0; if(prev1 == -1 || prev2 == -1 || (long)nums[prev2]-(long)nums[prev1] == (long)nums[idx]-(long)nums[prev2]){ pick = helper(idx+1,prev2,idx,count+1,nums,dp); } return dp[idx][prev1+1][prev2+1] = pick + not_pick; } public int numberOfArithmeticSlices(int[] nums) { int n = nums.length; int dp[][][] = new int[n][n+1][n+1]; for(int i=0; i

@krat9707

6 ай бұрын

@@pranavsharma7479 its cuz you're not keeping track of the count.

I'm too tired to even think about this problem😂 yesterday's one was a disaster and today is even worse😢...

When BOSS is saying "its really hard" , we are finally in a problem which is HARD as duck,

java class Solution { public int numberOfArithmeticSlices(int[] nums) { int result = 0; int n = nums.length; Map dp = new HashMap(); for (int i = 0; i dp.put(i, new HashMap()); for (int j = 0; j long diff = (long) nums[i] - nums[j]; int count = dp.get(j).getOrDefault(diff, 0); dp.get(i).put(diff, dp.get(i).getOrDefault(diff, 0) + count + 1); result += count; } } return result; } }

To help out.. Why n*(n-1)//2? Why you need subtract counts of subsequence of length 2 out of 'res'? In problem statement: "A sequence of numbers is called arithmetic if it consists of at least three elements" Explained in Neetcode video 12'25" to 14' What are the subsequences of length 2? Take example 1 as example, nums = [2,4,6,8,10] Diff=2 (4 counts) 2,4 4,6 6,8 8,10 Diff=4 (3 counts) 2,6 4,8 6,10 Diff=6 (2 counts) 2,8 4,10 Diff=8 (1 count) 2,10 Total, 10 counts! Formula to estimate count for this is: n*(n-1)//2

Came up with this solution but getting a TLE after 38 test cases ! Recursion + Memoization (by generating all subsequences and then checking AP). class Solution: def numberOfArithmeticSlices(self, nums: List[int]) -> int: n = len(nums) dp = {} def is_arithmetic_slice(l): for j in range(1, len(l) - 1): if l[j] - l[j-1] != l[j+1] - l[j]: return False return True def rec(i,c, l): if (i,c) in dp: return dp[(i,c)] if i == n: #print(l) return 1 if len(l) >= 3 and is_arithmetic_slice(l) else 0 ntk = rec(i + 1,c, l) l.append(nums[i]) tk = rec(i + 1,c+1, l) l.pop(-1) dp[i] = tk + ntk return dp[i] return rec(0,0, [])

Dynamic programming is so hard :(

DP is Hard.

editing issue at 17:04 great explanation otherwise

🎯 Key Takeaways for quick navigation: 00:00 🧠 *Introduction to Problem* - Explanation of the problem "Arithmetic Slices II - Leetcode 446." - Definition of subsequences and the condition for arithmetic subsequences. 01:22 🤔 *Subsequence Problem Solving Approach* - Decision-making process for including or skipping integers in subsequences. - The challenge of counting subsequences with the same difference. - Recursive approach complexities and reasons for skipping it in this case. 02:32 🔄 *Identifying Subproblem for Dynamic Programming* - Discussion on identifying the subproblem for dynamic programming. - Explanation of the subproblem: "Starting at index I, how many subsequences can we get?" - The importance of keeping track of the current index and the difference. 05:24 📊 *Dynamic Programming Solution Implementation* - Initialization of a 2D grid (implemented as a list of hashmaps) to store subsequences. - Exploring the subsequences in a bottom-up manner. - Highlighting the reverse order iteration for ease of implementation. 07:28 🔍 *Subsequence Counting in Dynamic Programming* - Explanation of how to count subsequences ending at a specific index with a particular difference. - Demonstration of updating the DP grid and counting subsequences. - The observation that all subsequences are guaranteed to be of length three or more. 15:15 🖥️ *Final Code Implementation* - Initialization of variables for result and input length. - Nested loops to iterate through indices and calculate subsequences. - Correcting a bug related to overcounting subsequences. 19:27 ➖ *Adjusting Result Calculation* - Alternative method for calculating the result without adding subsequences of length two. - Explanation of subtracting duplicates using a combinatorial approach. - Demonstration of how this adjustment works effectively. Made with HARPA AI

Even with your explanation, I failed to understand this one😂