Cherry Pickup | BackTracking Solution | Leetcode 741

Please consume this content on nados.pepcoding.com for a richer experience. It is necessary to solve the questions while watching videos, nados.pepcoding.com enables that.
NADOS also enables doubt support, career opportunities and contests besides free of charge content for learning. For a better experience and more exercises, VISIT: www.pepcoding....
Have a look at our result: www.pepcoding....
Follow us on our UA-cam page: / pepcoding
Follow us on our FB page: / pepcoding
Follow us on Instagram: / pepcoding
Follow us on LinkedIn: / pepcoding-education
Follow us on Pinterest: / _created
Follow us on Twitter: home
.
.
.
Happy Programming !!! Pep it up 😍🤩
.
.
.
#pepcoding #code #coder #codinglife #programming #coding #java #freeresources #datastrucutres #pepcode #competitive #competitiveprogramming #softwareengineer #engineering #engineer

[@abhishekupadhayay9399]

No one can imagine, how much happy I m after seeing sir back on UA-cam,
Just see him calmness while explaining the solution...
Sir is really a legend🔥

[@dayanandraut5660]

Time complexity analysis. For going from top left to bottom right. O(2^nxn) and for each such path, we need to explore 2^nxn paths. so overal time complexity will be O(4^nxn). i.e 4 to the power n square

[@AnshulSharma-gq2vn]

I think the overall time complexity should be O(4 ^ (n + n)) because in any path you will at most traverse through n rows and n columns before reaching your destination.

[@AbhishekMishra-me4mu]

If the input is [[1]]. This code will give 0 as the answer! So include one more condition to handle this specific input, rest inputs works fine! Nice Explanation though!!

[@avinashjain227]

here is the cpp solution
//backtracking approach - TLE
class Solution {
public:
int maxi=0;
void help2(int r,int c,vector&grid,int count,int n)
{
if(r=n || c=n || grid[r][c]==-1)
return;
if(r==0 && c==0)
{
maxi=max(maxi,count);
return;
}
int cherry=grid[r][c];
grid[r][c]=0;
help2(r-1,c,grid,count+cherry,n);
help2(r,c-1,grid,count+cherry,n);
grid[r][c]=cherry;
}
void help(int r,int c,vector&grid,int count,int n)
{
if(r=n || c=n || grid[r][c]==-1)
return;
if(r==n-1 && c==n-1)
{
int cher=grid[r][c];
grid[r][c]=0;
help2(r,c,grid,count+cher,n);
grid[r][c]=cher;
return;
}
int cherry=grid[r][c];
grid[r][c]=0;
help(r+1,c,grid,count+cherry,n);
help(r,c+1,grid,count+cherry,n);
grid[r][c]=cherry;
}
int cherryPickup(vector& grid) {
// int count=0;
int n=grid.size();
help(0,0,grid,0,n);
return maxi;
}
};

[@B_i_n_o_d]

I think it will not work for one corner case,grid= [[1]]

[@gautamarora6556]

Add this condition in before making call the any other function:
if(grid.size()== 1 && grid[0][0]== 1) return 1;

[@samyakjain7422]

You are definitely real life Jeetu bhaiya as in reel life Jeetu bhaiya in Kota Factory.The way you explained approach and solution, I became your fan.

[@Pepcoding]

Thanks for your compliment.
Keep learning.
And for better experience, visit nados.io, where you will get well curated content and career opportunities.

[@KandulaAsrith]

very good explanation sir. Thank you...

[@amandixit3555]

the base case -:
row>=n || col >=n || ar[row][col]==-1 is sufficient

[@Pepcoding]

For better insight, visit nados.io, post your doubts, community will help you out there.

[@shantanukumar4081]

Quality Content Great Explanation !!!

[@NikhilKumar-vf9nv]

Thank you sir for making these good level questions vedios this question asked by many companies in OA as well as in interviews

[@sushilkumarrai8956]

Good to see you sir after a long time. We were missing you.

[@Mercer80]

no dry run or even a recursion tree to show the working of code ,where is the backtracking done ? anyone plz explain

[@vivekjaiswal3663]

time complexcity discuss krdo ek baar it would be good

[@dayanandraut5660]

Great explanation

[@amritanshvajpayee5147]

Bhaiya Maximum Product Subarray pe please bnai video. Abhi tak nhi bani hai

[@tanujpandey9870]

Can this question be solved through recursion also?

[@ayushmansharma5321]

bhai recursion hi toh he ye bus isme backtracking aur aa gayi he

[@tusharnain6652]

this can be more optimized using dp

[@rishabhyadav4994]

bhaiya plz add all dp videos in dp playlist level 2 on youtube

[@irfanquader3944]

bhaiya please do leetcode 78 if possilbe

[@261288888]

Bahut slow ho aap