Yeah, I'm walking out the interview if I get this question
@NeetCodeIO10 ай бұрын
Didn't they use to put the hard problems at the end of the month?
@raunakgiri2110 ай бұрын
Now it's probably weekends too
@zaki_133710 ай бұрын
no they used to do that every weekend before Festival season (December).
@salim44410 ай бұрын
@@zaki_1337cool profile photo bro
@Strikas_shroud10 ай бұрын
Weekend hard mode lol 😆
@krishnakanthati851010 ай бұрын
@CS_n00b10 ай бұрын
I think it would be useful to show you working through a dfs solution and telling us where you get stuck
@sdmfslkdm10 ай бұрын
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 < 2) { 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
@minhtrannhat332210 ай бұрын
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.
@niels902510 ай бұрын
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
@NeetCodeIO10 ай бұрын
Yeah that's exactly right, there are more permutations than combinations.
@NoFormalities-y1k10 ай бұрын
Bro, please consider explaining in following order: recursion -> memoization -> tabulation -> space optimization , it will be more helpful.
@zaki_133710 ай бұрын
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
@cinimodmil10 ай бұрын
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_133710 ай бұрын
@@cinimodmil I’m probably less knowledgeable than you. No idea if it’s n^3. ChatGPT said it’s 2^n 💀
@ap2s200010 ай бұрын
@NeetCodeIO There was a part that was cut off at 16:50 FYI
@BirajDahal-z6u10 ай бұрын
I gave up on this question
@normanfung712410 ай бұрын
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
@shivamchaurasia291010 ай бұрын
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]
@tasneemayham97410 ай бұрын
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.
@zweitekonto965410 ай бұрын
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.
@diplodocus310 ай бұрын
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.
@pritz910 ай бұрын
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, [])
@dera_ng10 ай бұрын
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.
@aij19jha3810 ай бұрын
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
@IK-xk7ex10 ай бұрын
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.
@ngocnb5210 ай бұрын
I think it's badly written.
@vinayjangra140110 ай бұрын
the editorial for this problem is premium ;)
@NoFormalities-y1k10 ай бұрын
Go learn Dp form striver , you will be skilled enough to think about the solution.
@yang584310 ай бұрын
java class Solution { public int numberOfArithmeticSlices(int[] nums) { int result = 0; int n = nums.length; Map dp = new HashMap(); for (int i = 0; i < n; i++) { dp.put(i, new HashMap()); for (int j = 0; j < i; 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; } }
@sidyadav2310 ай бұрын
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 ?
@tasneemayham97410 ай бұрын
Thank youuuu!!!! YOU AREEE THE BESTTTT!!!!
@BROOKnim10 ай бұрын
great solution and explanation. I did the brute way memoization.
@EasterBunnyGaming10 ай бұрын
how did u do memoisation ? what were the keys
@BROOKnim10 ай бұрын
@@EasterBunnyGaming the same. difference and the starting index of subsequence
@王瀚君-c3j10 ай бұрын
Thank you for your explanation, it did help me a lot. Literally GENIUS!
@teslax924310 ай бұрын
Thanks, good explanation.
@EduarteBDO10 ай бұрын
One day I hope I can solve questions like this
@MP-ny3ep10 ай бұрын
Amazing explanation. Thank you
@krateskim416910 ай бұрын
Great explanation
@akakartiksaini10 ай бұрын
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.
@erminiottone10 ай бұрын
What happened at 16:58? It seems we lost a piece of explanation
@laumatthew7110 ай бұрын
Great explanation, thank you !
@pastori267210 ай бұрын
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
@pragyantripathi397910 ай бұрын
Thank you, good explanation. I just didn't get that part where you subtracted n(n-1)/2. Can someone help???
@capecrusader270910 ай бұрын
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
@pragyantripathi397910 ай бұрын
@@capecrusader2709 got the combination concept. So basically we are subtracting all 2length subsequences from the total subsequences which are >= 2. Thank you
@hackytech749410 ай бұрын
Thank you, was waiting for it. ❤
@mire523410 ай бұрын
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 :(
@tasneemayham97410 ай бұрын
Notice, we have two for loops for i and diff which means the memoization should be with 2 variables. So work on that more.
@mire523410 ай бұрын
@@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
@hkleiser584810 ай бұрын
great, thank you
@krat970710 ай бұрын
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); } };
@pranavsharma747910 ай бұрын
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
@krat970710 ай бұрын
@@pranavsharma7479 its cuz you're not keeping track of the count.
@sergioo722210 ай бұрын
me, new with only easies done, trying to understand this solution:
@joydeeprony8910 ай бұрын
When BOSS is saying "its really hard" , we are finally in a problem which is HARD as duck,
@rinnaaaaae10 ай бұрын
I'm too tired to even think about this problem😂 yesterday's one was a disaster and today is even worse😢...
@rahulsbhatt10 ай бұрын
Bro, you gotta teach discrete mathematics and combinatorics as well, please!
@krishnakanthati851010 ай бұрын
DP is Hard.
@kuda912910 ай бұрын
editing issue at 17:04 great explanation otherwise
@bundiderp510910 ай бұрын
Dynamic programming is so hard :(
@andrewsong776010 ай бұрын
🎯 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
@Pegasus02Kr10 ай бұрын
Even with your explanation, I failed to understand this one😂