Arithmetic Slices II - Leetcode 446 - Python

[@NeetCodeIO]

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

[@raunakgiri21]

Now it's probably weekends too

[@zaki_1337]

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

[@salim444]

​@@zaki_1337cool profile photo bro

[@Strikas_shroud]

Weekend hard mode lol 😆

[@krishnakanthati8510]

[@yang5843]

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

[@minhtrannhat3322]

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.

[@CS_n00b]

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

[@sdmfslkdm]

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

[@zaki_1337]

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]

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]

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

[@niels9025]

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]

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

[@NoFormalities-y1k]

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

[@BirajDahal-z6u]

I gave up on this question

[@yang5843]

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; } }

[@diplodocus3]

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.

[@normanfung7124]

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

[@dera_ng]

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.

[@ap2s2000]

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

[@krat9707]

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]

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]

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

[@shivamchaurasia2910]

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]

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]

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.

[@IK-xk7ex]

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]

I think it's badly written.

[@vinayjangra1401]

the editorial for this problem is premium ;)

[@NoFormalities-y1k]

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

[@tasneemayham974]

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

[@teslax9243]

Thanks, good explanation.

[@MP-ny3ep]

Amazing explanation. Thank you

[@EduarteBDO]

One day I hope I can solve questions like this

[@krateskim4169]

Great explanation

[@pastori2672]

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

[@hackytech7494]

Thank you, was waiting for it. ❤

[@laumatthew71]

Great explanation, thank you !

[@BROOKnim]

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

[@EasterBunnyGaming]

how did u do memoisation ? what were the keys

[@BROOKnim]

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

[@pritz9]

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, [])

[@aij19jha38]

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

[@sidyadav23]

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 ?

[@akakartiksaini]

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.

[@andrewsong7760]

🎯 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

[@王瀚君-c3j]

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

[@hkleiser5848]

great, thank you

[@sergioo7222]

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

[@mire5234]

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]

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]

@@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

[@erminiottone]

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

[@pragyantripathi3979]

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

[@capecrusader2709]

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]

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

[@joydeeprony89]

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

[@rinnaaaaae]

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

[@rahulsbhatt]

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

[@krishnakanthati8510]

DP is Hard.

[@bundiderp5109]

Dynamic programming is so hard :(

[@kuda9129]

editing issue at 17:04 great explanation otherwise

[@Pegasus02Kr]

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