Arithmetic Slices II - Leetcode 446 - Python

  Рет қаралды 17,243

NeetCodeIO

NeetCodeIO

Күн бұрын

Пікірлер: 68
@yang5843
@yang5843 10 ай бұрын
Yeah, I'm walking out the interview if I get this question
@NeetCodeIO
@NeetCodeIO 10 ай бұрын
Didn't they use to put the hard problems at the end of the month?
@raunakgiri21
@raunakgiri21 10 ай бұрын
Now it's probably weekends too
@zaki_1337
@zaki_1337 10 ай бұрын
no they used to do that every weekend before Festival season (December).
@salim444
@salim444 10 ай бұрын
​@@zaki_1337cool profile photo bro
@Strikas_shroud
@Strikas_shroud 10 ай бұрын
Weekend hard mode lol 😆
@krishnakanthati8510
@krishnakanthati8510 10 ай бұрын
@CS_n00b
@CS_n00b 10 ай бұрын
I think it would be useful to show you working through a dfs solution and telling us where you get stuck
@sdmfslkdm
@sdmfslkdm 10 ай бұрын
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
@minhtrannhat3322
@minhtrannhat3322 10 ай бұрын
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.
@niels9025
@niels9025 10 ай бұрын
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
@NeetCodeIO 10 ай бұрын
Yeah that's exactly right, there are more permutations than combinations.
@NoFormalities-y1k
@NoFormalities-y1k 10 ай бұрын
Bro, please consider explaining in following order: recursion -> memoization -> tabulation -> space optimization , it will be more helpful.
@zaki_1337
@zaki_1337 10 ай бұрын
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
@cinimodmil 10 ай бұрын
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
@zaki_1337 10 ай бұрын
@@cinimodmil I’m probably less knowledgeable than you. No idea if it’s n^3. ChatGPT said it’s 2^n 💀
@ap2s2000
@ap2s2000 10 ай бұрын
@NeetCodeIO There was a part that was cut off at 16:50 FYI
@BirajDahal-z6u
@BirajDahal-z6u 10 ай бұрын
I gave up on this question
@normanfung7124
@normanfung7124 10 ай бұрын
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
@shivamchaurasia2910
@shivamchaurasia2910 10 ай бұрын
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
@tasneemayham974 10 ай бұрын
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
@zweitekonto9654 10 ай бұрын
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.
@diplodocus3
@diplodocus3 10 ай бұрын
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.
@pritz9
@pritz9 10 ай бұрын
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_ng
@dera_ng 10 ай бұрын
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.
@aij19jha38
@aij19jha38 10 ай бұрын
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-xk7ex
@IK-xk7ex 10 ай бұрын
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
@ngocnb52 10 ай бұрын
I think it's badly written.
@vinayjangra1401
@vinayjangra1401 10 ай бұрын
the editorial for this problem is premium ;)
@NoFormalities-y1k
@NoFormalities-y1k 10 ай бұрын
Go learn Dp form striver , you will be skilled enough to think about the solution.
@yang5843
@yang5843 10 ай бұрын
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; } }
@sidyadav23
@sidyadav23 10 ай бұрын
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 ?
@tasneemayham974
@tasneemayham974 10 ай бұрын
Thank youuuu!!!! YOU AREEE THE BESTTTT!!!!
@BROOKnim
@BROOKnim 10 ай бұрын
great solution and explanation. I did the brute way memoization.
@EasterBunnyGaming
@EasterBunnyGaming 10 ай бұрын
how did u do memoisation ? what were the keys
@BROOKnim
@BROOKnim 10 ай бұрын
@@EasterBunnyGaming the same. difference and the starting index of subsequence
@王瀚君-c3j
@王瀚君-c3j 10 ай бұрын
Thank you for your explanation, it did help me a lot. Literally GENIUS!
@teslax9243
@teslax9243 10 ай бұрын
Thanks, good explanation.
@EduarteBDO
@EduarteBDO 10 ай бұрын
One day I hope I can solve questions like this
@MP-ny3ep
@MP-ny3ep 10 ай бұрын
Amazing explanation. Thank you
@krateskim4169
@krateskim4169 10 ай бұрын
Great explanation
@akakartiksaini
@akakartiksaini 10 ай бұрын
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.
@erminiottone
@erminiottone 10 ай бұрын
What happened at 16:58? It seems we lost a piece of explanation
@laumatthew71
@laumatthew71 10 ай бұрын
Great explanation, thank you !
@pastori2672
@pastori2672 10 ай бұрын
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
@pragyantripathi3979
@pragyantripathi3979 10 ай бұрын
Thank you, good explanation. I just didn't get that part where you subtracted n(n-1)/2. Can someone help???
@capecrusader2709
@capecrusader2709 10 ай бұрын
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
@pragyantripathi3979 10 ай бұрын
@@capecrusader2709 got the combination concept. So basically we are subtracting all 2length subsequences from the total subsequences which are >= 2. Thank you
@hackytech7494
@hackytech7494 10 ай бұрын
Thank you, was waiting for it. ❤
@mire5234
@mire5234 10 ай бұрын
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
@tasneemayham974 10 ай бұрын
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
@mire5234 10 ай бұрын
@@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
@hkleiser5848
@hkleiser5848 10 ай бұрын
great, thank you
@krat9707
@krat9707 10 ай бұрын
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
@pranavsharma7479 10 ай бұрын
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
@krat9707 10 ай бұрын
@@pranavsharma7479 its cuz you're not keeping track of the count.
@sergioo7222
@sergioo7222 10 ай бұрын
me, new with only easies done, trying to understand this solution:
@joydeeprony89
@joydeeprony89 10 ай бұрын
When BOSS is saying "its really hard" , we are finally in a problem which is HARD as duck,
@rinnaaaaae
@rinnaaaaae 10 ай бұрын
I'm too tired to even think about this problem😂 yesterday's one was a disaster and today is even worse😢...
@rahulsbhatt
@rahulsbhatt 10 ай бұрын
Bro, you gotta teach discrete mathematics and combinatorics as well, please!
@krishnakanthati8510
@krishnakanthati8510 10 ай бұрын
DP is Hard.
@kuda9129
@kuda9129 10 ай бұрын
editing issue at 17:04 great explanation otherwise
@bundiderp5109
@bundiderp5109 10 ай бұрын
Dynamic programming is so hard :(
@andrewsong7760
@andrewsong7760 10 ай бұрын
🎯 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
@Pegasus02Kr
@Pegasus02Kr 10 ай бұрын
Even with your explanation, I failed to understand this one😂
K Inverse Pairs Array - Leetcode 629 - Python
29:44
NeetCodeIO
Рет қаралды 16 М.
Кто круче, как думаешь?
00:44
МЯТНАЯ ФАНТА
Рет қаралды 5 МЛН
Увеличили моцареллу для @Lorenzo.bagnati
00:48
Кушать Хочу
Рет қаралды 8 МЛН
What type of pedestrian are you?😄 #tiktok #elsarca
00:28
Elsa Arca
Рет қаралды 32 МЛН
Student Attendance Record II - Leetcode 552 - Python
27:10
NeetCodeIO
Рет қаралды 9 М.
Become a Malloc() Pro
6:58
thedoubleeguy
Рет қаралды 2,4 М.
Cherry Pickup II - Leetcode 1463 - Python
24:00
NeetCodeIO
Рет қаралды 16 М.
Minimum Cost to Hire K Workers - Leetcode 857 - Python
19:01
NeetCodeIO
Рет қаралды 14 М.
446. Arithmetic Slices II - Subsequence - Day 7/31 Leetcode January Challenge
32:18
Programming Live with Larry
Рет қаралды 581
Dynamic Programming isn't too hard. You just don't know what it is.
22:31
DecodingIntuition
Рет қаралды 197 М.
Sliding Window Technique - Algorithmic Mental Models
36:45
Ryan Schachte
Рет қаралды 362 М.
Rotating the Box - Leetcode 1861 - Python
15:14
NeetCodeIO
Рет қаралды 6 М.
Freedom Trail - Leetcode 514 - Python
25:18
NeetCodeIO
Рет қаралды 14 М.
Кто круче, как думаешь?
00:44
МЯТНАЯ ФАНТА
Рет қаралды 5 МЛН