Arithmetic Slices II - Leetcode 446 - Python
Vložit
- čas přidán 27. 07. 2024
- 🚀 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/arithme...
0:00 - Read the problem
1:08 - Drawing Explanation
15:12 - Coding Explanation
leetcode 446
#neetcode #leetcode #python
Didn't they use to put the hard problems at the end of the month?
Now it's probably weekends too
no they used to do that every weekend before Festival season (December).
@@zaki_1337cool profile photo bro
Weekend hard mode lol 😆
Yeah, I'm walking out the interview if I get this question
I think it would be useful to show you working through a dfs solution and telling us where you get stuck
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
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.
I gave up on this question
Thank you, was waiting for it. ❤
Bro, please consider explaining in following order: recursion -> memoization -> tabulation -> space optimization , it will be more helpful.
Great explanation, thank you !
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
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!
@@cinimodmil I’m probably less knowledgeable than you. No idea if it’s n^3. ChatGPT said it’s 2^n 💀
Amazing explanation. Thank you
Thanks, good explanation.
Great explanation
great, thank you
Thank youuuu!!!! YOU AREEE THE BESTTTT!!!!
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
Yeah that's exactly right, there are more permutations than combinations.
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.
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.
One day I hope I can solve questions like this
@NeetCodeIO There was a part that was cut off at 16:50 FYI
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.
great solution and explanation. I did the brute way memoization.
how did u do memoisation ? what were the keys
@@EasterBunnyGaming the same. difference and the starting index of subsequence
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.
I think it's badly written.
the editorial for this problem is premium ;)
Go learn Dp form striver , you will be skilled enough to think about the solution.
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 ?
Thank you for your explanation, it did help me a lot. Literally GENIUS!
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
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]
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.
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.
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
me, new with only easies done, trying to understand this solution:
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
What happened at 16:58? It seems we lost a piece of explanation
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);
}
};
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
@@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😢...
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, [])
Thank you, good explanation. I just didn't get that part where you subtracted n(n-1)/2. Can someone help???
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
@@capecrusader2709 got the combination concept. So basically we are subtracting all 2length subsequences from the total subsequences which are >= 2. Thank you
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 < 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;
}
}
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 :(
Notice, we have two for loops for i and diff which means the memoization should be with 2 variables. So work on that more.
@@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
Dynamic programming is so hard :(
DP is Hard.
editing issue at 17:04 great explanation otherwise
Even with your explanation, I failed to understand this one😂
🎯 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