The one who droped directly at video 43, *When comes why memoization* : Ohh WOW!! nice explaination what a nice guy, no one teaches like that,THE LEGEND! *The guy watching from video 1* When comes why memoization : Not again.. ahhh. NO.. Ohh lets hear him maybe we could learn something new..... NO NOT AGAIN!!!..
Even this memorized solution is giving TLE on Leet Code -> Better Solution can be figuring out the max no. of floor that cn be checked with a given no of egg.
@@aayush5474 gfg needs stricter test cases then. Also, if the interviewer asks to optimize this then you are out of options if you CHOOSE not to apply BS.
Python: Bottom Up, Time: O(E N^2), Space: O(EN) def Solve(eggs, floors): # Initialize T with 0's T = [[0 for _ in range(floors+1)] for _ in range(eggs+1)] # If only 1 egg was given for j in range(floors+1): T[1][j] = j for i in range(2, eggs+1): # From 2 because we do not want to overwrite row index 1 values for j in range(1, floors+1): T[i][j] = float('inf') for k in range(1, j+1): count = 1 + max(T[i-1][k-1], T[i][j-k]) T[i][j] = min(T[i][j], count) return T[i][j] eggs = 2 floors = 100 attempts = Solve(eggs, floors) print('Min # of attempts: ', attempts)
@@thevijayraj34 Time Limit Exceeded (TLE)...I modified the solution but still I get TLE...there might be some optimization needed... TLE when 4 eggs and 5000 floors class Solution(object): def superEggDrop(self, K, N): """ :type K: int :type N: int :rtype: int """ # Initialize table with infinity T = [[float('inf') for _ in range(N+1)] for _ in range(K+1)] # Base cases: 0 floor or 1 floor for i in range(K+1): T[i][0] = 0 # 0 floor -> 0 attempt T[i][1] = 1 # 1 floor -> 1 attempt # Base cases: 0 egg or 1 egg for j in range(N+1): T[0][j] = 0 # 0 egg -> 0 attempt T[1][j] = j # 1 egg -> check each floor for i in range(2, K+1): # Rows: 0 and 1 are base cases for j in range(2, N+1): # Cols: 0 and 1 are base cases for f in range(1, j+1): # Check 1 to j floors count = 1 + max(T[i-1][f-1], T[i][j-f]) T[i][j] = min(T[i][j], count) return T[K][N]
@@ankoor Hey bruh.. Just found the efficient way to solve this. Right now we're trying to find no. of attempts using (Floor and Eggs). But we've to do it in other way around. We should look for No. of Floors using (No. of Attempts and Eggs). This goes from min. numbers to big numbers and it resolves the TLE. This is one of the fine problem to solve.
N^3 since its a variation of MCM but it can be further optimized to N^2logN by using binary search instead of linear search for k loop , some people have commented the binary search version down below
@@LegitGamer2345 Hey. No.. This is not n^3. The recursive solution is tradition 2^n. (2 choices each). But the memoized code is n*k^2 (n*k is the dp matrix, k is the for loop)
Bro, I used Recursive and Memoization, However, it is exceeding time limit on LeetCode for Test Case (Egg -> 3, Floors -> 25). I have also memoized inner loop but still getting same issue. Any Help?
Go through this link leetcode.com/problems/super-egg-drop/discuss/792736/CPP-Explained-Recursive-greatermemoization-greateroptimization-greaterDP-oror-Well-Explained-oror-Easy-to-unserstand
JAVA CODE : static int funMemo(int egg, int floor, int[][] memo) { if (floor == 0 || floor == 1) return floor; if (egg == 1) return floor; if (memo[egg][floor] != -1) return memo[egg][floor]; int min = Integer.MAX_VALUE; for (int k = 1; k temp) min = temp; } memo[egg][floor] = min; return min; }
Code for the same in Java (leetcode) - class Solution { private int[][] dp = new int[101][10001]; public Solution() { for (int[] row: dp) Arrays.fill(row, -1); } public int superEggDrop(int k, int n) { if (n == 0) return 0; if (k == 1) return n; if (dp[k][n] != -1) return dp[k][n]; int ans = Integer.MAX_VALUE; for (int i = 1; i
Use binary search instead of linear loop to avoid tle like this, code-- private int helper(int K, int N, int[][] memo) { if (N 0) { return memo[K][N]; }
int low = 1, high = N, result = N; while (low < high) { int mid = low + (high - low) / 2; int left = helper(K - 1, mid - 1, memo); int right = helper(K, N - mid, memo); result = Math.min(result, Math.max(left, right) + 1); if (left == right) { break; } else if (left < right) { low = mid + 1; } else { high = mid; } } memo[K][N] = result; return result; }
#include using namespace std; int static t[11][51]; int solve(int e, int f) { if (f == 0 || f == 1) return f; if (e == 1) return f; if (t[e][f] != -1) return t[e][f]; int mn = INT_MAX; for (int k = 1; k as we have to find minimum Number of attempt // basically hame worst case ka minimum number of attempt nikalna hai mn = min(mn, temp); } // pahle store and then return return t[e][f] = mn; } int main() { memset(t, -1, sizeof(t)); int e = 2; int f = 4; // op should be 3 int minTrail = solve(e, f); cout
JAVA OPTIMIZE -- ``` class Solution { //Function to find minimum number of attempts needed in //order to find the critical floor. static HashMap hm = new HashMap(); static int eggDrop(int n, int k) { if(k==0 || k==1) return k; if(n == 1) return k; if(hm.containsKey(n+" "+k)) return hm.get(n+" "+k); int min=Integer.MAX_VALUE; for(int i=1;i
The one who droped directly at video 43,
*When comes why memoization* : Ohh WOW!! nice explaination what a nice guy, no one teaches like that,THE LEGEND!
*The guy watching from video 1*
When comes why memoization : Not again.. ahhh. NO.. Ohh lets hear him maybe we could learn something new..... NO NOT AGAIN!!!..
those who know why memoization needed start at 12:32
thanks bro
Thanks bro
thnksss biro
Thanks bro
Thanks bro
Thanks buddy ❤️ finally i have some command over Dp, Completed the playlist with full enthusiasm and knowledge gathering. #Dpwithadityaverma ❤️
No Dislikes, I think Tushar Roy has not watched this video yet.
But I am surprised why the viewership is low (7K vs 20k for most other videos). Maybe ppl already have become experts by watching prev videos :-)
kali zuban, ab dislike aagya
@@0anant0 memoized dhekne ki zarurat nhi if you know recursive 😁
@@Unknown-Stranger tushar roy ne matlab dekh li video
has watched now and from two ids 😁
43 of 50 (86%) done! Nice revision of memoization.
Can we get the pdf copy of all the pages you write an explanation on? Will be of great help!
Python: Top Down
eggs = 3
floors = 5
T = [[-1 for _ in range(floors+1)] for _ in range(eggs+1)]
def Solve(eggs, floors):
if floors == 0 or floors == 1:
return floors
if eggs == 1:
return floors
if T[eggs][floors] != -1:
return T[eggs][floors]
count = float('inf')
for i in range(1, floors+1):
temp = 1 + max(Solve(eggs, floors-i), Solve(eggs-1, i-1))
count = min(count, temp)
T[eggs][floors] = count
return count
attempts = Solve(eggs, floors)
print('# of attempts: ', attempts)
TLE on Leetcode
Explanation tgda tha bhai 🤝
sir,when r u uploading the videoes fibonaci and their 7 variation,grid(14),knade's(6).....?
did you find about these questions ?
Bhai Its called Top down apporach. Although Its brilliant the way you explain.
Even this memorized solution is giving TLE on Leet Code -> Better Solution can be figuring out the max no. of floor that cn be checked with a given no of egg.
you should have returned 1 + mn as we are making an attempt to check for future conditions.
Bro, you need to use binary search in place of your for loop, otherwise this will give TLE on lc despite memoization.
No you should not try binary in egg dropping. It is an another problem, think it over
@@RathourShubham Bro, say good bye to logic - Did you even tried submitting it on lc?
it worked on gfg
@@aayush5474 gfg needs stricter test cases then. Also, if the interviewer asks to optimize this then you are out of options if you CHOOSE not to apply BS.
Can you please share your code pls?
why can't we use hashmap like previous videos for memoization
Those two dislikes are from Tushar and Jenny
Can anybody tell he is live or not just asking for in some previous videos comments someone says he is not live
Python: Bottom Up, Time: O(E N^2), Space: O(EN)
def Solve(eggs, floors):
# Initialize T with 0's
T = [[0 for _ in range(floors+1)] for _ in range(eggs+1)]
# If only 1 egg was given
for j in range(floors+1):
T[1][j] = j
for i in range(2, eggs+1): # From 2 because we do not want to overwrite row index 1 values
for j in range(1, floors+1):
T[i][j] = float('inf')
for k in range(1, j+1):
count = 1 + max(T[i-1][k-1], T[i][j-k])
T[i][j] = min(T[i][j], count)
return T[i][j]
eggs = 2
floors = 100
attempts = Solve(eggs, floors)
print('Min # of attempts: ', attempts)
Are you able to pass the leet code question with this approach?
leetcode.com/problems/super-egg-drop/submissions/
@@thevijayraj34 Time Limit Exceeded (TLE)...I modified the solution but still I get TLE...there might be some optimization needed... TLE when 4 eggs and 5000 floors
class Solution(object):
def superEggDrop(self, K, N):
"""
:type K: int
:type N: int
:rtype: int
"""
# Initialize table with infinity
T = [[float('inf') for _ in range(N+1)] for _ in range(K+1)]
# Base cases: 0 floor or 1 floor
for i in range(K+1):
T[i][0] = 0 # 0 floor -> 0 attempt
T[i][1] = 1 # 1 floor -> 1 attempt
# Base cases: 0 egg or 1 egg
for j in range(N+1):
T[0][j] = 0 # 0 egg -> 0 attempt
T[1][j] = j # 1 egg -> check each floor
for i in range(2, K+1): # Rows: 0 and 1 are base cases
for j in range(2, N+1): # Cols: 0 and 1 are base cases
for f in range(1, j+1): # Check 1 to j floors
count = 1 + max(T[i-1][f-1], T[i][j-f])
T[i][j] = min(T[i][j], count)
return T[K][N]
@@ankoor There must be a different story for this to solve. Lemme dig it, then we'll discuss about this further.
@@ankoor Hey bruh.. Just found the efficient way to solve this. Right now we're trying to find no. of attempts using (Floor and Eggs). But we've to do it in other way around. We should look for No. of Floors using (No. of Attempts and Eggs). This goes from min. numbers to big numbers and it resolves the TLE. This is one of the fine problem to solve.
Code is correct.
In leetcode same solution in Java get accepted but TLE for python.
Can we use the concept of binary search on answer?
What's the time complexity of this optimized code?
N^3 since its a variation of MCM but it can be further optimized to N^2logN by using binary search instead of linear search for k loop , some people have commented the binary search version down below
@@LegitGamer2345 Hey. No.. This is not n^3. The recursive solution is tradition 2^n. (2 choices each). But the memoized code is n*k^2 (n*k is the dp matrix, k is the for loop)
Bro, I used Recursive and Memoization, However, it is exceeding time limit on LeetCode for Test Case (Egg -> 3, Floors -> 25). I have also memoized inner loop but still getting same issue. Any Help?
you must use dp-optimization to reduce the time(o) ie use tabulation
try same loop with binary search
Go through this link
leetcode.com/problems/super-egg-drop/discuss/792736/CPP-Explained-Recursive-greatermemoization-greateroptimization-greaterDP-oror-Well-Explained-oror-Easy-to-unserstand
JAVA CODE :
static int funMemo(int egg, int floor, int[][] memo) {
if (floor == 0 || floor == 1)
return floor;
if (egg == 1)
return floor;
if (memo[egg][floor] != -1)
return memo[egg][floor];
int min = Integer.MAX_VALUE;
for (int k = 1; k temp)
min = temp;
}
memo[egg][floor] = min;
return min;
}
8:13 why are we using max PLEASE HELP
because ques mein worst case pucha hai
@@chiragkhemani1615 thanks
Can u please add English subtitles to this I am not able to find the English subtitles for this video..I am poor at Hindi
the real magic is in his hindi though.
Code for the same in Java (leetcode) -
class Solution {
private int[][] dp = new int[101][10001];
public Solution() {
for (int[] row: dp) Arrays.fill(row, -1);
}
public int superEggDrop(int k, int n) {
if (n == 0) return 0;
if (k == 1) return n;
if (dp[k][n] != -1) return dp[k][n];
int ans = Integer.MAX_VALUE;
for (int i = 1; i
Use binary search instead of linear loop to avoid tle like this,
code--
private int helper(int K, int N, int[][] memo) {
if (N 0) {
return memo[K][N];
}
int low = 1, high = N, result = N;
while (low < high) {
int mid = low + (high - low) / 2;
int left = helper(K - 1, mid - 1, memo);
int right = helper(K, N - mid, memo);
result = Math.min(result, Math.max(left, right) + 1);
if (left == right) {
break;
} else if (left < right) {
low = mid + 1;
} else {
high = mid;
}
}
memo[K][N] = result;
return result;
}
I was also thinking of binary search bro
#include
using namespace std;
int static t[11][51];
int solve(int e, int f)
{
if (f == 0 || f == 1)
return f;
if (e == 1)
return f;
if (t[e][f] != -1)
return t[e][f];
int mn = INT_MAX;
for (int k = 1; k as we have to find minimum Number of attempt
// basically hame worst case ka minimum number of attempt nikalna hai
mn = min(mn, temp);
}
// pahle store and then return
return t[e][f] = mn;
}
int main()
{
memset(t, -1, sizeof(t));
int e = 2;
int f = 4;
// op should be 3
int minTrail = solve(e, f);
cout
JAVA OPTIMIZE --
```
class Solution
{
//Function to find minimum number of attempts needed in
//order to find the critical floor.
static HashMap hm = new HashMap();
static int eggDrop(int n, int k)
{
if(k==0 || k==1) return k;
if(n == 1) return k;
if(hm.containsKey(n+" "+k)) return hm.get(n+" "+k);
int min=Integer.MAX_VALUE;
for(int i=1;i