40 Evaluate Expression To True Boolean Parenthesization Memoized

[@lostgen36]

11:10 for those whom are watching in flow.

[@VinayakSrivastava101]

This should be a pinned comment for those watching in flow.

[@namandadhich]

Thanks man for this

[@shivanshgoswami5330]

🙏

[@sagarsondur]

this helps

[@shubhaverma5697]

thanks bro

[@praffulmishra1582]

I have been following the entire DP series and trust me it is the best playlist for dp in youtube. This question is more complicated than previous questions, but just watch the main logic 2-3 times and you will definitely understand it. Once you understand it, try coding it on your own. Fair warning: It's going to get more complicated. For those who are looking for an optimised solution similar to the Palindrome Partitioning, here is the entire code: #include using namespace std; int BP(string &s, int i, int j, bool b, vector &dp) { if (i > j) return false; if (i == j) { if (b) return s[i] == 'T'; else return s[i] == 'F'; } if (dp[i][j][b] != -1) return dp[i][j][b]; int ans = 0; for (int k = i + 1; k > s; bool b = true; vector dp(s.size() + 1, vector(s.size() + 1, vector(2, -1))); int cost = BP(s, 0, s.size() - 1, b, dp); cout

[@saurabh4326]

Ekk hi to dil hai kitni baar jeetoge ye line shayd bhai ke liye hi likhi gayi thi :-)

[@TheAdityaVerma]

Thanks bhai ✌️❤️

[@prabhatmishra6753]

@@TheAdityaVerma you are one of the best tutor for students who want to learn DSA

[@Wanna_be_01]

@@TheAdityaVerma Bhaiya... Actually I'm from ECE and literally 😑 I didn't like DSA Before... It seemed me a nightmare coz I'm not from CODING background tbh... But But after Watching your all Playlists 😇 I don't know how but I'm actually fall in love with DSA :) Now, it seems that DSA is the Most interesting thing :) But do you know, bcs of whom I fall in love with DSA????? Well.... Bcs of YOU BHAIYA ❤️🙌 and your teaching styles... :) And thanks for Your playlist 😊😊😊 bhaiya... :) Now, I'm like - "Aise teachers colleges me kyon nhi hote hai? yrr😕" Thanks again to you 🥺 and your each and every playlists are just at the top notch... :)

[@vaishnaviagarwal5259]

Please complete the dp playlist topics like Kandane's algorithm, dp on grids,etc.

[@himanshugiri4214]

Yes,please much needed

[@rohan_2844]

Check this out : kzbin.info/aero/PLauivoElc3ggagradg8MfOZreCMmXMmJ-

[@hokkisthaal5820]

@@himanshugiri4214 oho

[@sonianarendramodi2605]

@@hokkisthaal5820 ye himanshu flirt kar rahe hi na bhenchod..

[@Aladin40chor]

Exactly bro this playlist is incomplete with kadane and dp on grid. 😢

[@arpitanand4248]

Legendary explanation sir ! Not many people have guts to go this basic to explain the concepts of DP . Thanks a lot sir .

[@sutanubhattacharya6307]

@Aditya Verma thanks a lot bhai.. It's a hard level question in GFG and you made it look so easy. This is the best youtube channel for coding!! must say

[@TheAdityaVerma]

Thanks, if you like it, do share the channel among your friends and college !!

[@sutanubhattacharya6307]

@@TheAdityaVerma definitely... Anyway I would have surely left DP for my placements, if I hadn't discovered ur videos... Could you please upload a playlist on interview questions on hashing... ?

[@yashgupta-rg5it]

Great video Bhai. Easier way to add to map string temp=to_string(i)+" "+to_string(j)+" "+to_string(isTrue);

[@TusharKumar-em4qu]

Unordered map, In case someone's wondering

[@rutanshu85]

Some OJs like Leetcode doesn't like unordered_map for time. Gets TLE. So 2 DP arrays might be the way to go.

[@yangzhang1870]

Thanks a lot ( instead of filling comment section with thanks, just increment the counter, lets keep the comment section for "suggestions / improvement / query " ).

[@pulkitgpt1234]

on GFG when we return the answer it should be ans%1003 as it is written in the problem description.

[@surajsuryawanshi7835]

Thanks bro I have been searching for this for 2 hrs

[@raghavbhatia5548]

@@surajsuryawanshi7835 me too

[@0anant0]

39 of 50 (78%) done! I prefer the 3D array.

[@anandsharma5850]

same

[@ryanryan6567]

Sir Please don't say Thanks at the end. It's our Responsibility to say Thanks to You for this awesome DP series. So Thanks a lot. ❤️

[@HimanshuKumar-xz5tk]

His understanding of DP is so good.

[@aalekhsrivastava9973]

Great Explanation. I also came up with a similar approach but the way of implementation and thought process is different. Lets say we have input = {T^T^F*T&F...........T} create a parent function which just counts the ways by splitting at different operands index. e.g. for k = 1, check if (left part ^ right part == True) ->> increase count for k = 3, check if (left part ^ right part == True) ->> increase count for k = 5, check if (left part * right part == True) ->> increase count at the end return count; Now for evaluating left and right part separately, write a different evaluate function whose purpose is just to evaluate and return true or false. Of course evaluate function will also break the input expression at different operands. Code below :- public class EvaluateExpressionToTrue { static int count = 0; static Map map = new HashMap(); public static void main(String[] args) { String x = "T^T^F"; countWays(x.toCharArray(), 0, x.length() - 1); System.out.println(count); } private static int countWays(char[] x, int i, int j) { for (int k = i + 1; k < j; k = k + 2) { System.out.println("evaluating in parent - " + i + "::" + k + "::" + j); int lRes = evaluate(x, i, k - 1); int rRes = evaluate(x, k + 1, j); int res = getResult(lRes, rRes, x[k]); if (res == 1) count++; } return count; } private static int evaluate(char[] x, int i, int j) { if (i == j) return 1; for (int k = i + 1; k < j; k = k + 2) { System.out.println("evaluating - " + i + "::" + k + "::" + j); String key = i + ":" + k + ":" + j; if (!map.containsKey(key)) { int lRes = evaluate(x, i, k - 1); int rRes = evaluate(x, k + 1, j); int res = getResult(lRes, rRes, x[k]); if (res == 1) { map.put(key, 1); return 1; } } map.put(key, 0); } return 0; } private static int getResult(int lRes, int rRes, char operand) { int res; switch (operand) { case '|': res = lRes | rRes; break; case '&': res = lRes & rRes; break; case '^': res = lRes ^ rRes; break; default: throw new IllegalStateException("Unexpected value: " + operand); } return res; } }

[@TheIndianGam3r]

Those who are getting TLE on gfg or any other website please follow this: 1) use a 3D dp array instead of unordered_map as the complexity of unordered_map is still O(N) in worst case due to collisions in hashing. 2) memoize at every call in the k loop too like @Aditya Verma has shown in palindrome partitioning optimization video. 3) (For the worst of edge cases) In the base condition i==j , before returning store value 0/1 (T/F) depending on outcome in you dp array then return. I have personally tried this and it works. Hope this helps!

[@ashishmohapatra4654]

Thanks, bro, I did all the 3 points u mentioned, and my code got succeeded in GFG... TYSM. But Did you have any optimization algo. in using unordered_map and getting passed in GFG ???? (AFTER considering 2nd & 3rd concepts above, in my code) If yes, please share :)

[@rishabsinha8749]

Bro please paste your code here

[@ashishmohapatra4654]

@@rishabsinha8749 sure bro.. #include #include using namespace std; // Better use 3D Matrix cuz we don't have to iteratively search in the matrix as we are doing with Map. int dp[1001][1001][2]; //for storing every sub-problems ans.(Memoization) int TBP(string s, int i, int j, bool output) // here boolean output is the subproblem expression o/p { if(dp[i][j][output] != -1) return dp[i][j][output]; if(i>j) //invalid i/p return dp[i][j][output] = 0; if(i==j) //smallest valid i/p { if(output == true) { if(s[i] == 'T') // i& j index pointer always lies either on T or F return dp[i][j][output] = 1; else return dp[i][j][output] = 0; } else if(output == false) { if(s[i] == 'F') return dp[i][j][output] = 1; else return dp[i][j][output] = 0; } } ////Base Condition int ans = 0; for(int k=i+1; k>t; while(t--) { memset(dp, -1, sizeof(dp)); int n; cin>>n; //str length string str; cin>>str; int TrueNoOfWaysParenthesize = TBP(str, 0 ,n-1 , true); //final value of expression to be evaluated true. cout

[@abhishekbajaj109]

@@ashishmohapatra4654 bro in base condition when i==j cant we directly do this if(output == true) return dp[i][j][output] = 1; but not what you did if(i==j) //smallest valid i/p { if(output == true) { if(s[i] == 'T') // i& j index pointer always lies either on T or F return dp[i][j][output] = 1; else return dp[i][j][output] = 0; } else if(output == false) { if(s[i] == 'F') return dp[i][j][output] = 1; else return dp[i][j][output] = 0; } } ////Base Condition

[@princesaini9580]

@@ashishmohapatra4654 Bro my only qus. for this solution is what would be the optimum size of the 3D Matrix. As len of string mentioned in the problem is 1

[@gandhijainamgunvantkumar6783]

for those who are getting time limit on gfg on this code, you also have to store the ans of subproblems lt, rt, lf,rf in 3d matrix

[@anmolsinghal484]

To all those jinka GFG pe TLE aa raha hai, I was getting TLE i.e. 1.96 seconds ki limit cross hori thi. For DP table, i was using VECTOR. So i replaced vector by Array and Mera solution 0.41 seconds me submit ho gaya. Hope it fixes yours too :)

[@prateeksinghal630]

Thank you so much

[@mayankpatel6735]

www.geeksforgeeks.org/boolean-parenthesization-problem-dp-37/ try this. The optimization is done in the previous problem, is not done in this problem. The optimization can be found in GFG,

[@mohammadareeb1882]

Thanks bro it helped .

[@_ADITITARATE]

Your videos really helped me grasp dp. Keep up the good work! And please make a graph playlist!

[@sriramsridhara1763]

if we take a 3d table as t[2][1001][1001] its easier to imagine. because now there are 2 layers of nxn stacked on top of each other. 1 layer depicts when isture is true and the other depicts when istrue is false. if we take t[1001][1001][2] then its the same thing except sideways. 1001 layers of 1001x2 tall strips which is same as 2 1001x1001 matrices side by side

[@engineersthing1557]

I guess the TC for the GFG problem is updated, i was getting TLE but passed all test cases after optimization explained in earlier videos Thankyou @Aditya Verma sir

[@vasudevparmar9876]

how did you know you passed all test cases

[@engineersthing1557]

@@vasudevparmar9876 It was accepted at GFG & had tested some manually.

[@nikhilsrivastava7719]

Very clear explanation in both part 1 and part 2. I understood everything.Thank you so much🤗

[@roushanraj8530]

Yrr aap bawal ho apka explanation ka koi jawab ni h 💯💥💥💯❤❤❤ Btw bhaiya, aap dp on fibonacci, LIS, kadan's algorithm and dp on grid ka videos ni upload kroge kya ??

[@ShashankRustagiCSE]

On GFG, they used similar example. They used Unordered_map

[@subhamsoy1280]

if the return type of the solve function is int then why (i>j)is returning true??

[@sourabhjain7302]

Just use 1 and 0 instead of True and False respectively

[@AbhaySingh-xd2cd]

true represents 1 and false represent 0

[@albumlist1]

If we store LT, LF, RT, RF too in the map , it will provide better optimization .

[@Bdixit]

Eventually, recursion will save these i.e. LT, LF, RT, RF. when we will not have them in map and when we will ask recusrion to solve them then last line of the code will be executed for each of them, which is saving calls.

[@sanjayvasnani988]

They will automatically get stored on their first function call

[@gourangpathak4443]

Improved Memoization by using map for the recursive calls inside the for-loop as well class Solution{ public: unordered_map mp; int solve(string S,int i,int j, bool isTrue) { if(i > j) return 0; if(i == j) { if(isTrue) { return S[i] == 'T' ? 1 : 0; } else { return S[i] == 'F' ? 1 : 0; } } string key = to_string(i); key.push_back(' '); key.append(to_string(j)); key.push_back(' '); key.append(to_string(isTrue)); if(mp.find(key) != mp.end()) { return mp[key]; } int ans = 0; for(int k = i+1; k

[@kunalgoel9608]

bro why are we doing ans%1003

[@gourangpathak4443]

@@kunalgoel9608 Bro Gfg practice problem statement says "Your task is to complete the function countWays() which takes N and S as input parameters and returns number of possible ways modulo 1003." that is why I did it

[@kunalgoel9608]

@@gourangpathak4443 thanks bro

[@kunalgoel9608]

@@gourangpathak4443 class Solution{ static int countWays(int N, String S){ // code here return solve(S,0,N-1,true); } static Map numbers = new HashMap(); static int solve(String s,int i,int j,boolean isTrue){ //base Condition if(i>j){ return 0; } if(i==j){ if(isTrue==true){ return s.charAt(i)=='T'?1:0; }else{ return s.charAt(i)=='F'?1:0; } } //chek in map for value String key=i+" "+j+" "+isTrue; if(numbers.containsKey(key)){ return numbers.get(key); } // variable to store ans int ans=0; //choice diagram code for(int k=i+1;k

[@Nirmalkumar-rs5xh]

thanks man @@gourangpathak4443

[@ankitbhardwaj9566]

your explanation was great but the code is giving tle at gfg,i request you to please solve that question and put the solution in description

[@mayankpatel6735]

www.geeksforgeeks.org/boolean-parenthesization-problem-dp-37/ try this. The optimization is done in the previous problem, is not done in this problem. The optimization can be found in GFG,

[@harshtyagi700]

My learning always read the problem description completely even if you know the problem. I was getting wrong answer at GFG because the answer has to modulo with 1003. The C++ Solution for the problem is :- unordered_map mp; int noOfWays(string S,int i,int j , bool isTrue) { if(i>j) return 0; if(i==j) { if(isTrue) return S[i]=='T'?1:0; else return S[i]=='F'?1:0; } string temp=to_string(i)+' '+to_string(j)+' '+to_string(isTrue); if(mp.find(temp)!=mp.end()) return mp[temp]; int ans=0; for(int k=i+1;k

[@lifeofchetas]

why did u do %1003 ?

[@sakeel7341]

@@lifeofchetas given in question

[@shivanshyadu4830]

thankyou so much buddy for helping out

[@nikhilsisodia9576]

There is a mistake in the code. In the base condition if(i > j) return false; will come. Not if(i > j) return true; But it does not matter as the code wont reach that base case as k is always between (i, j) (i and j not inclusive)

[@shriharikulkarni3986]

return type is int and returning true / false ?

[@YashYadav-dd7is]

@@shriharikulkarni3986 true for 1 and false for 0 in cpp

[@bhagatalisha]

no he is right, it should be return false/0 only

[@aniketkumarsinha2537]

Can't we use two 2D matrix one for true and one for false??

[@vishalsiddha6637]

It will also work with map and not give TLE just use mapname.count(key) (will take O(1) time) instead of mapname.find. :) Happy learning!!

[@jeetgupta1107]

wrong it takes logarithmic in size, same as find

[@rahulraj_iitgn]

@@jeetgupta1107 logarithmic time i.e log(n) only in case of map i.e ordered_map not in case of unordered map.

[@jeetgupta1107]

@rahulrajsjs22 then in case of unordered_map it will take linear size

[@AftabKhan-dd8et]

You made this question so easy..how can i develop my thinking like yours?

[@lakshya8532]

Just to ask isn't it good idea to also store values of LT, LF, RT, RF values for further optimization ??

[@codexhammered007]

return type is int, we should return 0 or 1 based on the check in base conditions. something like: if (i>j) return 0; if (i==j) { if (isTrue) return s[i] ? 1 : 0; return !s[i] ? 1 : 0; }

[@Prashantkumar-pn6qq]

Jump to 10:00 if you know why we need memoization.

[@Vishwajeetkumar-gm8rf]

This code will give tle in gfg. So you need to do 2 changes in the code to run: 1. Use 3D array instead of map as even an unordered map takes logn time to find the key and when the key is string the the time complexity will be O(s.length()logn) so it'll give tle. 2. Take int t[205][205][2] instead of int t[101][101][2] as the constraint in the question is wrong. ##CODE## ## IT WILL IN 0.76 SEC ## #include #define mod 1003 using namespace std; int dp[205][205][2]; int solve(string s, int i, int j, bool isTrue){ if(i>j) return 0; if(dp[i][j][isTrue]!=-1) return dp[i][j][isTrue]; if(i==j){ if(isTrue) return s[i]=='T'; else return s[i]=='F'; } int ans=0; for(int k=i+1; k> t; int n; while(t-- && cin >> n){ memset(dp, -1, sizeof(dp)); string s; cin >> s; cout

[@chirag-sg4kd]

@Vishwajeet can you please explain to me why you used mod? Is it because of some constraints?

[@ananysharma9290]

Thank ypu buddy 🔥😍✅

[@Bdixit]

@@chirag-sg4kd it was asked in question and also to avoid int overflow. Read properties of modulo lke : ( a * b) % c = ( ( a % c ) * ( b % c ) ) % c

[@ManojKumar-wi2dn]

thanks bro...i was just worrying were i was wrong and you helped a lot

[@yashrajsingh8181]

Internally unordered_map is implemented using Hash Table, the key provided to map are hashed into indices of a hash table that is why the performance of data structure depends on hash function a lot but on an average, the cost of search, insert and delete from the hash table is O(1).

[@tejasharishborkar3754]

bro please start recursion and backtracking series ...I am waiting for it...😁😁

[@ajitkumarsingh871]

We all are waiting ! Plz 🙏🙏🏿🙏🏿🙏🙏🏿🙏🏿

[@sudiptakumardas3547]

aur bhai kya hal

[@mindpower185]

This is the memoization solution , totally fine ,and all are same only one thing , you just need to use ans % 1003 , ( for avoiding the overflow) int t[201][201][2]; int solve(string &s , int i , int j , bool isTrue){ //Base Case if(i > j ) return 0; //memoization check if(t[i][j][isTrue] != -1){ return t[i][j][isTrue]; } //Base case, if there is only one element if( i == j){ if(isTrue == true) return s[i] == 'T'; else return s[i]== 'F'; } //K loop int ans = 0; // temp ans // All possibilities for getting true and false as well for(int k = i+1 ; k

[@mindpower185]

use only if you facing diffcultly while using map solution

[@danielmcdonald7272]

Thank you @Adiyta Verma I have a question though, if for the solution we are calculating answer for all the times the expression evaluates true or false, aren't we supposed to find only the times the expression evaluates true only ?

[@gamerhu7462]

refer to prev question video bro he explained it! why u have to find both!!! ex - for XOR u need one true and one false !!! so u need to find the expr returning false and the remaining expr returning true;

[@rishikeshsingh8207]

Code as explained in the video. Passed all test cases on gfg unordered_map m; int solve(string s, int i, int j, bool isTrue){ if(i>j) return 0; if(i==j){ if(isTrue==true){ return s[i]=='T'; } else{ return s[i]=='F'; } } string temp=to_string(i); temp.push_back(' '); temp.append(to_string(j)); temp.push_back(' '); temp.append(to_string(isTrue)); if(m.find(temp)!=m.end()){ return m[temp]; } int ans=0; for(int k=i+1;k

[@roshansinghenc7745]

1003 se mod kyu kiya

[@rishikeshsingh8207]

@@roshansinghenc7745 on gfg according to question the required answer should be less than 1003 that is why mod is done

[@derekspecial1771]

Both map and 3d matrix will work absolutely fine but to pass all test cases use modulo in your code..

[@vishalplayzz2580]

iam getting some segmentation fault 😶😶

[@apoorvamittal1379]

What is the time complexity of this solution? Please help in finding out the complexity.

[@voldemort576]

it think O(n^3)

[@yadneshkhode3091]

@@voldemort576 How ? please explain

[@ABCD-gn5uw]

@@yadneshkhode3091 at worst we will need to calculate every single cube of matrix. so the time complexity would be. O(N*N*2). N is length of the string.

[@editorera239]

kaafi sahi explanation h sr

[@tejassharma2739]

how can we return boolean in base condition in a func returning integer

[@mayankbanwari4169]

op bro , hats off to you , but i cant understand one thing , in the function the return type is int then how you can return boolean in base condtion .

[@prathameshgaikwad9281]

Love u sirji bahot badiya💯💯😍

[@kushalappaca5324]

Nice way to explain.

[@aryankhare9393]

What is the space and time complexity for this solution?

[@ankitdubey9310]

recursion ki time complexity kya hai? before optimization

[@pankajarmo129]

By mistake, you have written the base condition i>j : True

[@vaibhavk3177]

if you are getting TLE error in gfg...we have to take at last (ans%1003)...it is given in qn too, I forgot to read the qn properly and was wasting my time for half an hour....hope this helps !

[@bhavyaagrawal7098]

my code is still showing TLE

[@NareshKumar-dw9xp]

If you are doing in Java at GFG then you need to use 3D array instead of Map. Otherwise you will become frustrated after writing a long code after watching (48+28) minutes video.

[@createinfinity3088]

can u plse tell me whats wrong with my java code...im getting output as 0 always import java.util.*; class Main { static int[][][] t; static int lf,lt,rf,rt; static int ans=0; static int solve(String s,int i,int j,int o) { if(i>j){return t[i][j][o]=0;} if(t[i][j][o]!=-1) return t[i][j][o]; if(i==j) { if(o==1) { if(s.charAt(i)=='T'){return t[i][j][o]=1;} else {return t[i][j][o]=0;} } if(o==0) { if(s.charAt(i)=='T'){return t[i][j][o]=0;} else {return t[i][j][o]=1;} } } for(int k=i+1;k

[@sameerm3662]

Amazing explanation for this complex problem, thanks Aditya for this. Btw for this memoization, we're used to with t[][] as suggested by you :). Can't we not use two 2-D arrays to keep the solution for sub-problems based on their "isTrue" value like below - static int[][] tTrue = new int[150][150]; static int[][] tFalse = new int[150][150];

[@LokeshSharma-hm5jz]

dp questions are like story , you cannot forget.

[@madhavchaturvedi4654]

How are you returning true and false in base condition of the function is int type

[@shuvrasishroy]

it returns 0 or 1

[@devanshmesson2777]

Thank you so so so so so so much!!!!

[@divyachoudhary5938]

I am a big fan of you now.... Wow, u r amazing.... Really so genius.... Ur way of approaching problems is awesome... I am still trying to rotate the pen like you 😂😂😂😂I wish you all the best and wish that you become the best youtuber.

[@kuldeepnarayanminj]

great explaination

[@jainildodia]

1D - line, 2D - square, 3D - cube

[@kartikeydixit3743]

you are genius bro!!!!!!

[@eswarbhupathi3863]

What will be the time and space complexity?

[@amangour4508]

unordered map me find function ki complexity O(N) hoti hai , shouldnt it be replace by ordred map ?

[@bestravi0]

I think if I>j is should be return false

[@harshitgoyal7592]

i was thinking if one has to solve using 2d matrix only just make two 2d matrix one for true and another for flase and just have a check on the starting on istrue ? I hope this approch will work as well 😊

[@saiyamjain5079]

Yes I did it

[@saiyamjain5079]

int solve(string s, int i, int j, bool isTrue, vector& dpTrue, vector& dpFalse){ if(i>j){ return 0; } if(i==j){ if(isTrue == true){ return s[i]=='T'; }else if(isTrue == false){ return s[i]=='F'; } } if(isTrue == true && dpTrue[i][j]!=-1){ return dpTrue[i][j]; }else if(isTrue == false && dpFalse[i][j]!=-1){ return dpFalse[i][j]; } int ans = 0; for(int k=i+1; k

[@a036nikhilsannat4]

How to identify whether sub-problems are overlapping or not

[@siddharthkushwaha9745]

When return type is int then in base conditions why we are returning Boolean.

[@anjanobalesh8046]

Hint for javascript coders using a map will timeout on gfg use 3d array

[@vikasgautam2408]

function is integer type but it is returning boolean value

[@TheAdityaVerma]

No, search comments for the answer, I have already answered it.

[@shree_divyansh]

15:52 Aditya Verma - Humna 1001 pe 1 extra laga dia, kyo? Me - Shagun ka lia?

[@prabhanshuchauhan4150]

Constraints are given wrong in GFG.. If someone is facing tle or sigsegv error, then initialise your dp[205][205][2] like this.. 105 is out of bound

[@priyanshu.tiwari]

Could you run the program??

[@prabhanshuchauhan4150]

@@priyanshu.tiwari Yes

[@priyanshu.tiwari]

@@prabhanshuchauhan4150 i tried, it still didn't work, can u share your code once?

[@prabhanshuchauhan4150]

@@priyanshu.tiwari you can ignore solve2 function. That is for bottom-up dp.

[@priyanshu.tiwari]

@@prabhanshuchauhan4150 hey, thanks, it worked :), I wrote a similar code but it was giving TLE, ide.geeksforgeeks.org/x0vJ1Ba2Tu

[@johntakerChiku]

can we use hashmap??? that would have been faster in terms of search time so...

[@Bdixit]

Hashmap isn't faster than array, array are index based data structure which have worst case O(1) time access to an element, Hashmap we do say it O(1) asymptotically through amortized analysis but it will definately take more running time than an arrays or a matrix.

[@thelegend5248]

Bro.. what microphone, camera and stick u use to keep in such position can you say? It's nice and interesting!! 😇

[@TheAdityaVerma]

kyaa bhai hr jgh troll kr rha h tu isko 😅

[@saptarshichatterjee9760]

not getting all testcases passed in IB

[@AbhishekGupta-mb4rw]

What is time complexity for this code ??

[@mayur_madhwani03]

n^2 with matrix with map it'll be slightly more

[@ShubhamSharma-sn8rq]

the approach is not correct giving tle on gfg, but the explanation is good. use table instead of a map.

[@ankitbhardwaj9566]

EARLIER I WAS USING THE MAP AS A MEMOIZATION METHOD BUT IT WAS GIVING TLE THEN I MOVED TO 3D MATRIX MEMOIZATION METHOD STILL IT WAS GIVING TLE ,,THEN I JUST APPLIED TWO LINES OF FAST AND MY CODE GOT ACCEPTED..THANKU #include using namespace std; #define ll long long #define fast ios::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL) //unordered_mapmp; long long int dp[501][501][3]; #define mod 1003 ll solve(string str,ll i,ll j,bool istrue){ if(i>j)return false; if(i==j){ if(istrue==true){ return str[i]=='T'; } else return str[i]=='F'; } if(dp[i][j][istrue]!=-1){ return dp[i][j][istrue]; } ll ans=0; for(ll k=i+1;k>n; string str; cin>>str; // mp.clear(); memset(dp,-1,sizeof(dp)); cout

[@ayushthakur2896]

Great video!!

[@anusatyachoudhary7382]

Question link - practice.geeksforgeeks.org/problems/boolean-parenthesization/0 Please help in finding the bug in my code. URL -ide.geeksforgeeks.org/P2ldnthQUD

[@rjramu6676]

showing TLE with map but not with 3d array plus few more optimization done in calculating lt lf rt rf as you taught in palindrome partitioning optimization. thanks^infinity is small for you man! well this not my real id : }

[@amansinghgautam9189]

Bro can u share me the code.

[@rangapavankumar79]

@@amansinghgautam9189 did u get the code?

[@govindrathi9340]

gfg mein bina bottom up test pass nhi ho rhe....

[@mayank3949]

i have doubt .. in memoization jb hm ye check krte h ki value already present h ya nhi ..or agr present h toh fir uss value ko use krte instead of again recursive call toh iske liye hm "return " ku use krte ku ki return s toh function whi terminate ho jayega , hme wo value ko sirf use krna chaiye na

[@youryuvv]

Complete JAVA SOLUTION FOR THIS PROBLEM --> public class Solution { int mod; HashMap memo = new HashMap(); public int cnttrue(String expr) { mod = 1003; return numWaysForType(expr, 0, expr.length() - 1, 'T'); } int numWaysForType(String expr,int i, int j, char value) { if(i > j) return 0; if( i == j) return expr.charAt(i) == value ? 1 : 0; String key = i + " " + j + " " + value; // String key = String.valueOf(i) ; // key= key.concat(" ") ; // key = key.concat(String.valueOf(j)) ; // key= key.concat(" ") ; // key= key.concat(String.valueOf(value)) ; if(memo.containsKey(key)) return memo.get(key); long ans = 0; for(int k = i + 1; k

[@jiteshtokas2229]

why global variable doesn't work on interviewbit? it always give wrong ans.

[@ridimamittal4064]

I m not getting the difference between the top-down and bottom-up approaches?

[@ayushbisht2689]

Using matrix is easier as compared to map bcz we don't need to visualise the matrix

[@svworld01]

In base condition you have returned boolean and as an answer you have returned integer value,, I'm not getting what should be the return type of this solve method?

[@TheAdityaVerma]

I have already covered this question somewhere in the comment, do search for a detailed answer, but here's a summary since our function return int true will be converted to 1 and false to zero.

[@svworld01]

@@TheAdityaVerma got it. Actually I'm doing in java where 0 is not false and 1 is not true.

[@TheAdityaVerma]

@@svworld01 I am sure you can resolve that to java.

[@svworld01]

@@TheAdityaVerma ofcourse sir, I simply done it as if(isTrue) return (s.charAt(i) == 'T')? 1: 0; else return (s.charAt(i) == 'F')? 1: 0;

[@कत्यूषा]

@@svworld01 can you please share your Java code for this problem.

[@gauravbanerjee2898]

Dp god or what 🔥❤️‍🔥

[@1111rinku]

the base condition returning Boolean for T and F and function returning int ?

[@aayush5474]

doesn't matter it will return 1 or 0

[@priyanshu.tiwari]

why for i>j condition, we are returning true? at that time expression can't be evaluated, so it should be returning false..

[@adarshkunwar8113]

it was a silly mistake, if you look at the previous video it's written false there!

[@priyanshukhullar5836]

@@adarshkunwar8113 *there

[@adarshkunwar8113]

@@priyanshukhullar5836 fixed it! Thx!

[@ankoor]

Python Memoized using 3D Table: S = ['T', '|', 'F', '&', 'T', '^', 'T'] n = len(S) # T size: 2 x n x n T = [[[-1 for _ in range(n)] for _ in range(n)] for _ in range(2)] def Solve(S, i, j, isTrue): if i > j: return False if i == j: if isTrue: return S[i] == 'T' else: return S[i] == 'F' if T[isTrue][i][j] != -1: return T[isTrue][i][j] count = 0 for k in range(i+1, j, 2): LT = Solve(S, i, k-1, True) LF = Solve(S, i, k-1, False) RT = Solve(S, k+1, j, True) RF = Solve(S, k+1, j, False) if S[k] == '&': if isTrue: count = count + LT * RT else: count = count + LT * RF + LF * RT + LF * RF elif S[k] == '|': if isTrue: count = count + LT * RF + LF * RT + LT * RT else: count = count + LF * RF elif S[k] == '^': if isTrue: count = count + LT * RF + LF * RT else: count = count + LT * RT + LF * RF T[isTrue][i][j] = count return count count = Solve(S, 0, len(S) - 1, True) print(count)

[@stellararts9926]

Hey, I wrote almost the same code; however, for one of the test cases, the output I am getting is very large. Have you faced this ?

[@praharshsingh2095]

Bro ek doubt he ki jo solve recursive calls he usme seedhe sare LT , RT , LF , RF par call kr rahe he , but hame ye check nhi krna chahiye ki wo subproblems pehle se hi t matrix me exist kr rahi he ya nahi . ( jesa optimization boolean parenth. me kiya tha ). Please clear this doubt.

[@cripz4203]

interviewbit accept nhi kr rha tha isliye thoda optimise krdiya jisse kuch fn calls na krne pade. agar is case me bhi aisa hai toh optimise kr skte ho

[@lovleshbhatt7797]

bhai koi fayda ni usko check krke kyoki agar manlo LT solve ho chuki h aur humne usko call krdiya to wo bas ek extra recursion call legi or wps aa jaiga parent program mai... to usse TC pr farak ni padga na hi optimization pr.

[@rishabsinha8749]

@@lovleshbhatt7797 recursive calls are slower than if else condition so many recursive calls would be saved if you check it before and I think it's a kind of optimization otherwise interview bit wouldn't have accepted the solution

[@shreyashachoudhary480]

Amazing!

[@shivamagrawal6406]

can we store lT, lF, rT, rF values in map inside the for loop??

[@sanjayvasnani988]

They will automatically get stored on their first function call

[@HimanshuSingh-ob9qo]

Plz complete the playlist

[@vipulgupta3915]

Working code: public class Solution { static Map memoization; public int cnttrue(String str) { memoization= new HashMap(); int count = countBoolean(str, 0, str.length() - 1, true); return count; } static int countBoolean(String str, int i, int j, boolean isTrue) { if (i > j) return 0; if (i == j) { if (isTrue) return str.charAt(i) == 'T' ? 1 : 0; else return str.charAt(i) == 'F' ? 1 : 0; } String key = ""+i+j+isTrue; if(memoization.containsKey(key)) return memoization.get(key); int ans = 0; for (int k = i + 1; k < j; k += 2) { int lt = countBoolean(str, i, k - 1, true); int lf = countBoolean(str, i, k - 1, false); int rt = countBoolean(str, k + 1, j, true); int rf = countBoolean(str, k + 1, j, false); if (str.charAt(k) == '&') { if (isTrue) ans += lt * rt; else ans += lt * rf + lf * rt + lf * rf; } else if (str.charAt(k) == '|') { if (isTrue) ans += lt * rf + lf * rt + lt * rt; else ans += lf * rf; } else if (str.charAt(k) == '^') { if (isTrue) ans += lt * rf + lf * rt; else ans += lf * rf + lt * rt; } } ans = ans % 1003; memoization.put(key, ans); // dp[i][j][getNumfrombool(isTrue)] = ans; return ans; } }

[@su-prabhat]

GFG Updated it's constraint and looking for an iterative approach / complete matrix approach, so any plan of that video in the list?

[@bitbuybit9193]

following

[@nabeelmehar2984]

Nope Memoization is working . I Successfully Submitted Solution today . I will Attach the Java Solution in reply to this comment .

[@nabeelmehar2984]

class Solution{ static int countWays(int n, String s1){ int[][][] dp=new int[n+1][n+1][3]; for(int[][]a :dp){ for(int[]aa :a){ Arrays.fill(aa ,-1); } } return paranthize(s1 ,0 ,s1.length()-1 ,true ,dp); } static int paranthize(String s1 ,int i ,int j ,boolean isTrue ,int[][][] dp){ if(i == j){ if(isTrue){ if(s1.charAt(i)=='T'){ return 1; }else{ return 0; } }else{ if(s1.charAt(i)=='F'){ return 1; }else{ return 0; } } } if(dp[i][j][isTrue ? 1 :2]!=-1){ return dp[i][j][isTrue ? 1 :2]; } int ways=0; for(int k=i+1 ;k

[@Bdixit]

My cpp accepted solution with runtime of 0.5 // { Driver Code Starts // Initial Template for C++ #include using namespace std; // } Driver Code Ends // User function Template for C++ int t[201][201][2]; class Solution{ public: int countWays(int n, string s){ memset(t, -1, sizeof(t)); return solve(s, 0, n-1, true); } int solve(string &s, int i, int j, bool ex){ if(i > j) return 0; int exi = (ex == true ? 1 : 0); if(t[i][j][exi] != -1) return t[i][j][exi]; if(i == j){ if(ex){ return t[i][j][exi] = (s[i] == 'T'); } else{ return t[i][j][exi] = (s[i] == 'F'); } } int ans = 0; for(int k = i+1; k

[@mananmodi1246]

@@nabeelmehar2984 Hey! What's the %1003 for?

[@gigachad6844]

If you can't imagine a cube, imagine two 2D matrix first one - > i,j matrix fully for True another one > 2D matrix i,j fully for False.

[@raghavpande5704]

whys i return false valid when return type is of func solve is int?????

[@ashutoshdhyani8946]

memoized code ;) #include #include using namespace std; unordered_map mp; int mcm(string str,int i,int j,bool istrue) { if(i>j) return false; if(i==j) { if(istrue==true) return str[i]=='T'; else return str[i]=='F'; } string temp=""; temp.push_back(str[i]); temp.push_back(str[j]); if(istrue) temp.push_back('1'); else temp.push_back('0'); if(mp.find(temp)!=mp.end()) return mp[temp]; int ans=0; for(int k=i+1;k>str; mp.clear(); int indi=0; int indj=str.length()-1; bool istrue=true; cout

[@sayantandas99]

The memoized code done using MAP os giving TLE in gfg. If anyone has done it...Kindly send the code.... "Memoized code done by Mapping"

[@ashkrjha]

Map is giving TLE on gfg, better use 3D Matrix cuz we don't have to iteratively search in matrix as we are doing with Map. But if you get the optimized code, help me out too!

[@hindiexpress8021]

Why we need to take mode with 1003? on gfg

[@ROHITSHARMA-te2zo]

the reason is ans can be very long so they want to make it short ,this is written on other sites but not gfg