All Indices in Array - Solution | Recursion | Data Structures and Algorithms in JAVA
Vložit
- čas přidán 24. 07. 2020
- 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. In this video, we discuss the solution where we are required to find all the indices of occurrence for a given element and print it using a separate array using a recursive logic. To watch the problem statement, click here: • All Indices in Array -...
For a better experience and more exercises, VISIT: www.pepcoding.com/resources/o...
#pepcoding #programming #freeonlinecourses
Have a look at our result: www.pepcoding.com/placements
Follow us on our FB page: / pepcoding
Follow us on Instagram: / pepcoding
Follow us on LinkedIn: / pepcoding-education
randomly started watching recursion tutorials playlist from your channel at around 12:00 am, now its 3:25 am and i am half way through it! (24/53), i cant tell you how brilliantly you have explained the concepts! I would definitely complete it and also complete all the major parts of Data Structures and Algorithms from your channel! Thank you so much Sir! I really appreciate your efforts!
I love this. This is what makes it worth for me. I hope you keep watching.
@@Pepcoding Sure Sir! I am loving this! Are we gonna get Intermediatary and adv level course videos too?
@@dheerajbarik383 yes. All of pepcoding's content, current and future in its entirety will be made available to the community.
@@Pepcoding I would definitely gonna share this with my friends! Thank you so much sir! ♥️
I am also following the same pattern, picking up DSA playlist of PepCoding, and watching in sequence, everything is explained very well in a detailed manner, and got 100% clear concepts, I am able to solve so many problems because of Pepcoding(Sumit Sir)!!, I am going level by level mentioned by Pepcoding, Thanks a lot for such great and in-depth content. Dedication, Interest, patience, and discipline are most important when following Pepcoding, Go level by level, and I can say with confidence, that in the future you won't stuck in DSA if you complete all levels of DSA from Pepcoding, no other channel is needed, Pepcoding is capable enough to clear all the concepts and problems of DSA.
This is GOLD!! I came here after someone's LinkedIn post. First watched Tower of Hanoi from your channel.I am hooked now.
Great. I like it when somebody likes this video. Tower of Hanoi mei bhot effort daala tha poori story bnane mei.
Also, i request you for a review
g.page/Pepcoding/review?rc
I don't think there could be a better explanation of this question with so much patience you explain the concepts make it crystal clear.
I am happy to know this
I was about to give up on DSA. But after watching your videos of the recursion series for the first time, I realized, "I shouldn't".
this channel deserves 1million subscribers...already shared with all my friends all across the platforms
I have tears in my eyes at how brilliantly Sir explains such complex concepts with so much ease. Thank you for coming on CZcams and uploading such brilliant content for free.
kya clarity hai ek dum crystal clear hojata hai concept!! Thank you so much sir!!
also, take a note that this playlist is the best playlist for recursion. you have just reborn my interest in coding.
This is real gold..All your videos are exceptional..
I usually don't comment but I can't stop myself to comment that "Bhai maza aa gya"....Itna depth me recursion koi nhi padhata
Glad that you loved it. For better experience and curated content sign up on nados.io, you can also post your queries on community tab of NADOS.
First of all ,thanks for this recursion playlist. And
Sir you dry run makes a recursion very very easy.
keep uploading playlist we will always support you.
Can't be taught simpler than this... Hats off to u sir and to your efforts...
The best playlist ever and i have been following ur dsa playlist , u make things easier. Keep it up sir stay blessed
Love from Kashmir 💗
This was my approach->
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
int[] arr = new int[n];
for (int i = 0; i < n; i++) {
arr[i] = Integer.parseInt(br.readLine());
}
int x = Integer.parseInt(br.readLine());
int[] iarr = allIndices(arr, x, 0, 0);
if (iarr.length == 0) {
System.out.println();
return;
}
for (int i = 0; i < iarr.length; i++) {
System.out.println(iarr[i]);
}
}
public static int[] allIndices(int[] arr, int x, int idx, int fsf) {
if (arr.length == idx) {
return new int[fsf];
}
if (arr[idx] == x) {
fsf++;
}
int[] ans = allIndices(arr, x, idx + 1, fsf);
if (arr[idx] == x) {
ans[--fsf] = idx;
}
return ans;
}
}
This is also a correct solution. But, you are comparing it while going up and while coming down as well. That's the only difference, which might be a slower approach as compared to the approach shown in this video.
Subscribed. Wholesome explanation.
I watched the first vedio for trial and now I can't stop myself from watching your vedios
Watched on 17 October, 2021 - Thanks for the video.
Only few people can do this great cause. Serving the community in such a nice way. Thanks!
I am a businessman, this content is my marketing.
Keep learning. We both win if you learn from my content. We win together.
Wish I knew about you in the start of my 1st year, it would have been a bliss fore me sir!
I got the logic clearly but I want to know what is the "faith" in this ques.
I was following you from starting of recursion. I solved this question by own. I am literally so happy sir.. Just because of you now I can show magics in recursion. I am very pumped up
Actually I use cpp so I used stack and I kept pushing_back while moving from start to end only and when I reached the end I returned the vector.
.. Thankss
Never Understand the recursive Concept Like this. Great work Sir and Thank you for making recursion crystal clear
Thankyou beta!
I am glad you liked it. I hope that you are watching till the end and trying to understand what, how, and especially why of the problem.
If you like our efforts, will you like to write a few words about us here (www.quora.com/What-are-the-good-websites-to-learn-data-structures-and-algorithms )
@@Pepcoding sure sir. I watched the whole Playlist can't able to leave it because of you. Now I love recursion.
Thank you sir, due to you I've gain confidence in solving recursion problems... :)
Thankyou beta!
I am glad you liked it. I hope that you are watching till the end and trying to understand what, how, and especially why of the problem.
If you like our efforts, will you like to write a few words about us here (www.quora.com/What-are-the-good-websites-to-learn-data-structures-and-algorithms )
After trying so many times , move here and there , done with everything to learn recursion but was not able to understand this topic . Everyone was saying recursion is a magic but I was not able to see that magic but sir You, I do not have words to describe your efforts , Thank you so much sir. You made it really easy thank you so much.
You dont know sir , i was totally blank after watching other youtube videos about recursion,backtracking btt your channel give me hope and confidentt too, that i can also solve some recursion questions
wow sir!! your explanation is next level 🔥😍🤍
Amazed !! Sometimes up and sometimes down.. and understood the intuition behind such complex recurison so easily.. Awesome sir :)
Thanks a ton. keep motivating, keep learning and keep loving Pepcoding😊
Hats off to your dedication and Patience. Thank you.
Glad you liked it!
Keep learning.
And for better experience, visit nados.io, where you will get well curated content and career opportunities.
Awesome Explanation
after learning so much, from this video I am able to write my own recursion functions properly... :)
Great job!
Keep learning.
And for better experience and well organised content visit nados.pepcoding.com
Kudos to you..🙏❤️
Your teaching skills are awesome!!!
Glad you like them!
Great explanation sir♥️
My approach ->
public static int[] allIndices(int[] arr, int x, int idx, int fsf) {
if(idx == arr.length){
return new int [fsf]; //base case
}
if(arr[idx] == x){ //upar jaate huye stack me check karna ke x kitni baar aaya
fsf++;
}
int arr1[] = allIndices(arr, x, idx + 1, fsf);
if(arr[idx] == x){ //waapas aate huye array jo aaya usko bharna
arr1[fsf - 1] = idx;
}
return arr1;
}
Really very good explanation
Best teacher I have been ever seen since nursery class.
wow, this cheers me up. I am glad we at pepcoding could be of help to you. Keep learning. Also, recommend us to your juniors and peers, they may also benefit.
@@Pepcoding sumeet sir teach us everything that you know.
@@knightrec869 google AUTO CORRECT is devil sumit sir you spelled submit
well explained
Pure gold!
Glad to know that you liked the content and thank you for appreciating.
The love and respect which I get from you people keep me highly motivated and the same I am able to forward It to you people through my videos.
So, keep motivating, keep learning and keep loving Pepcoding😊
maza aagya sir ;)
great ho sir aap
Bhai ek course lai rkha maine Ds ka khi or se Lekin vha bhi itna accha explain nhi krta koi jitna Apne yha btaya vo bhi free of cost . Thnnx sir ...
hmara he course le lete!! :-(
😍😍😍😍😍😍😍Bahut jayada hi maja aaya GURUji..LOve hard of ur teching
Glad to know that you liked the content and thank you for appreciating.
The love and respect which I get from you people keep me highly motivated and the same I am able to forward It to you people through my videos.
So, keep motivating, keep learning and keep loving Pepcoding😊
Sir u are just awesome🙏
Thankyou beta!
I am glad you liked it. If you like our efforts, will you like to write a few words about us here (www.quora.com/How-do-I-start-learning-or-strengthen-my-knowledge-of-data-structures-and-algorithms )
Sir in this question and in FIrst index second approach , how to think about the faith and link with expectation ?
bhaiya app sabse alag ho pure utube pai mai aur sab apki sari vedios ko share and popular karenge thnks sir
Thanks man for this lovely gesture. Also, If you like our efforts, will you like to write a review about us here - g.page/Pepcoding/review?rc
Superb explanation sir.
Thanksyou beta!
Keep learning and keep loving😊
8:20 agr saare teachers students ko aise hi smjhte to kya baat hoti!!!!
Was able to come up with a much smaller solution
arr = [3,4,3,4,1,2]
results = []
def all_idx(arr, number, index):
if index == len(arr):
return []
if arr[index] == number:
return [index] + all_idx(arr, number, index + 1)
return all_idx(arr, number, index + 1);
print(all_idx(arr, 3, 0))
You didn't do anything just ...
Merging the lines ..both solutions are same
sir what if we have to return the array to a function where it prints its content.... but it will require the length also apart from the address.
How can we solve this question using "faith" and "expectation" as done in other examples?
This is not an intuitively recursive problem I'd say. It's better to solve it iteratively both in terms of cost and fuzziness. Although this problem gives an in-depth understanding of memory management during recursive calls. Faith and Expectation is a technique to think about problems that are intuitively recursive. This on the other hand involves using an Array which by definition is a contiguous space in memory which is a CS specific concept, and hence you're bound by something specific to limitations in computer science. This is a very good problem for understanding the recursion in depth. Although Faith and Expectation will fit here as well, it won't make much sense to think about it since you're getting an array from the subproblem which is actually of the size which is determined by keeping the parent problem in mind.
That being said, this is a beautiful problem and Sumeet Sir did a great job like always, with the explanation.
Can we do it in single traversal?? As here we are traversing it 2 times(for count & for indices).
sir direct arraylist bna k indices add nahi kr skte hai kya ??
Wow❤️
Keep watching and keep learning😊
good explanation sir jiii !
Dynamic programing with the help of java pe pls video banaeye ga.........dynamic programming ke liye he recursion padh raha huuuu.
Haanji. Aj shuru ho jaega
writing this at timestamp 5:30
my code is below and its working totally fine,
please tell if its wrong approach in terms of recursion or time complexity.
vector rec(vector v,int tofind,int index, vector toreturn){
if(index==v.size())
return toreturn;
if(v[index]==tofind){
toreturn.push_back(index+1);
return rec(v,tofind,index+1,toreturn);
}
else{
return rec(v,tofind,index+1,toreturn);
}
}
For better insight, visit nados.pepcoding.com, post your doubts, community will help you out there.
Sir isme faith and Expectation kaise rahenge?
is it possible ki jo recursion se hoga wo iteration se bhi hoga?
If we do by sir’s approach, how will we know that fsf will get reduced if we previously not know the solution…. and if data is large how will we handle this and know this. And also fsf value is 3 and arr[fsf] is of size 3 how it will contain 4 values ??
can any one help me please
how to return the base case in python
sir op🔥
keep motivating, keep learning and keep loving Pepcoding😊
Wow what a logic. I am thinking about using collection framework
Glad you liked it!
If you like our efforts, will you like to write a few words about us here (www.quora.com/How-do-I-start-learning-or-strengthen-my-knowledge-of-data-structures-and-algorithms )
yes, you can do it that way too
Thank you so much sir for this type of effort and explanation 🥰🥰🙏🏻🙏🏻🙏🏻💕💕💕I feel so much Lucky🥰🥰🙏🏻 that I find pepcoding and a great teacher like you🎊🎊🎊🤗🤗
Loved the Explanation sir !! Sir plz suggest me that I should first complete the foundation course's all problems and then practice on leetcode etc. or I should do leetcode along side this ??
beta pehle level1 finish karo, firr leet
@@Pepcoding okay thankyou sir ..
public static void allArrayEleOcc(int arr[],int index,int data){
if(index==arr.length){
return;
}
if(arr[index]==data){
System.out.print(index+" ");
}
allArrayEleOcc(arr,index+1,data);
} //is it also right ?
could someone pls give cpp code with same logic
it will be a great help,tq
rather than doing all this, can't we simply output the required index in the first iteration itself (as soon as we found the element, why don't we output it)? making an array brings unnecessary load on memory
satya,
Bhai plzz CP ke uper bhi videos banao
Sir ye return likhe hai program me wo kaha jata hai bahut dino se confuse hu sir
sir your videos are great .
I have a request, While using your platform , i was unable to download the failed testcases.Please correct that bug.
Noted
Explanation was awesome.. Now, I am loving recurion bcoz of you!... Can u plse tell me , how can i return base case in c++ of this problem.. I am stucked..
Return vector instead of array
can you plz send the code
sir the content here is like open gold mine ,loot lo jitna loot sakte ho😂,
sumit sir is king.....
aapki seva mei tatpar!
If you like my efforts, I request a review
g.page/Pepcoding/review?rc
One more approach to this question:
public static int[] allIndices(int[] arr, int x, int idx, int fsf) {
// write ur code here
if(idx == arr.length){
int[] res = new int[fsf];
return res;
}
if(arr[idx] == x){
// add this index to the array
fsf++;
}
int[] res1 = allIndices(arr, x, idx+1, fsf);
if(arr[idx] == x){
res1[fsf-1] = idx;
}
return res1;
}
any cpp solution
if you will declare iarr outside then it will be more clear, i think
public static int[] AllIndeces(int[] arr, int x, int start, int tot) {
if(start == arr.length)
return new int[tot];
int[] res;
if(arr[start] == x){
res = AllIndeces(arr, x, start + 1, tot + 1);
res[tot] = start;
}else {
res = AllIndeces(arr, x, start + 1, tot);
}
return res;
}
Sir ismein ham ArrayList bhi to use kar sakte the. Fir size ka issue nhi aata
yes
In place of array we can you a list to right?
Beta, I regret to inform you that, I won't be able to answer/solve the personal doubts of each and every student over here. For clearing your doubts, you can join our community on telegram - t.me/pepcoding.
Sir I am used to writing codes in c++ instead of java,and I have been following your lectures sincerely and implementing the same codes into c++ and they have helped me a lot. But in this particular code I am unable to write it in c++,can you provide me with the code in c++, the same code, it would be very helpful.
yes
please do this in cpp
Hey cpp soln with same approach as discussed in the video
vector allIndex(vector& arr, int idx, int data, int count)
{
if(idx == arr.size()){
res.resize(count,0);
return res;
}
if(arr[idx]==data){
res = allIndex(arr,idx+1,data,count+1);
res[count]=idx;
return res;
}
else{
res = allIndex(arr,idx+1,data,count);
return res;
}
}
@@codinggems9973 what is 'res' here it is undefined...can you please tell me cause I am facing that problem
@@omrajgure4553 vector..
all the explanations are awesome, but can anyone clarify for me what does 4k and 5k represent?
addresses of variables
Sir what is return new int (100)
dynamic allocation of array
I don't have any words...........but, Thanks a lot !
Thank you for appreciating.
The love and respect which I get from you people keep me highly motivated and the same I am able to forward It to you people through my videos.
So, keep motivating, keep learning and keep loving Pepcoding😊
@@Pepcoding yeah, sure sir ! 😇
Sir ,
how to know to kitne call laganii h recursiiiion me?
run your recursive algorith for small cases like 1-2-3 and then you can find the call on that basis
int* printAllIndexes(int arr[],int idx,int data,int n,int fsf){
if(idx==n){
int * p=(int *)malloc((fsf)*sizeof(int));
return p;
}
if(arr[idx]==data){
int *iarr= printAllIndexes(arr,idx+1,data,n,fsf+1);
iarr[fsf]=idx;
return iarr;
}
else{
int *iarr=printAllIndexes(arr,idx+1,data,n,fsf);
return iarr;
}
}
I have only one doubt... how we will access the length of the returned array in the main function.....
Int arr =allindices() ; here what is the use of int arr and how it's work here
Beta, I regret to inform you that, I won't be able to answer/solve the personal doubts of each and every student over here. For clearing your doubts, you can join our community on telegram - t.me/pepcoding.
can anyone provide the C++ code for this ???
C++ ki videos ban rhi hain beta jakal. jald aaega
Recieve nhi palle pada
Koi plz ye batado ki new array kaise li
Mai c++ ke liye puch rha hu
c++ me array nhi return kr skte
what happened to "faith" ?!
beta, purana ho gya. ab to aa gya na samajh, shuru shuru mei bolte hain. Infact 2 variation hain, ek faith wali doosri level and options wali. PrintSubsequence se doosri start hogi.
Aur, yahan comment kyun kar rhi ho, nados.pepcoding.com pe padho, wahan feed mei question poochogi to jwaab bhi milega.
aaj pta chla ki रायता boht Zaruri h🤣..
Hey! I have 2 doubts, I'd be glad if anyone could answer them for me.
(According to code visible at 8:34)
1) How come the (code)lines 33,34,35,37 and 38 realize the fact that the array created at line number 29(when recursion hits its base case) is the same array as "iarr" in which they have to fill the indices. As there is no mention of the name of "iarr" in line 29.
(According to DRY run at 12:59)
2) When we are "iterating back" from recursion, we see that the value of fsf decreases when we jump from the index 8 to 7 or from index 6 to 5. I totally understand why the value of fsf increases in the first place but when we are coming out of the recursion there is no statement to decrease the value of fsf when the favourable case(arr[i]=x;) is met, what I understand is that the value of fsf should remain 3 throughout and certainly that is not the case.
Thanks in advance if anyone could help!
because we returned an array in base case , in 33 34 and 35, 'iarr' is just the name of the array which is receiving the refernce of the base case array .
Both point to same address .
This is same in main , how main function recieves the array ( name is different but refernce is same ).
I hope i was able to help .
As for 2nd , i would suggest you to draw euler tree of this function with values of parameter . It will become clear
def last(arr, ind, x, res) :
If ind==len(arr) :
Return
If arr[ind]==x:
Res. Append(ind)
Last(arr, ind+1, x, res)
Return res
My solution is different why
For better insight, visit nados.io, post your doubts, community will help you out there.
Because you are using stack not array in array we have be worry about size...
//Easy JAVA Solution with single Recursive Call
private static int[] alloccurences(int arr[],int idx,int fsf,int x){
if(idx==arr.length){
if(fsf==0) {//element x is not present in array
return new int[]{-1};//hence return a new array of size 1 containing a single element -1;
}
else return new int[fsf];// array of size fsf (no. of times element is found)
}
if(arr[idx]==x){//count Number of elements in upward Recursive Motion
fsf++;
}
int res[]=alloccurences(arr,idx+1,fsf,x);
if(arr[idx]==x){
res[fsf-1]=idx;//fill the array in downward Recursive Motion
fsf--;//decrease pointer to fill the resultant array
}
return res;
}
.
Hi Guys. I solved this question without using the fsf variable . I learnt everything from you sir, I am forever grateful to you as you proided this education free of cost.
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
int[] arr = new int[n];
for (int i = 0; i < n; i++) {
arr[i] = Integer.parseInt(br.readLine());
}
int x = Integer.parseInt(br.readLine());
int[] iarr = allIndices(arr, x, 0, 0);
if(iarr.length == 0){
System.out.println();
return;
}
for(int i = 0; i < iarr.length; i++){
System.out.println(iarr[i]);
}
}
public static int[] allIndices(int[] arr, int x, int idx, int fsf) {
// write ur code here
if(idx==arr.length){
return new int[0];
}
int[] returnedArray=allIndices(arr,x,idx+1,fsf);
if(returnedArray.length==0){
if(arr[idx]==x){
int[] returnCurrAray = new int[1];
returnCurrAray[0]=idx;
return returnCurrAray;
}else{
return new int[0];
}
}
else{
if(arr[idx]==x){
int[] returnCurrAray = new int[returnedArray.length+1];
returnCurrAray[0]=idx;
for(int i=0;i< returnedArray.length;i++){
returnCurrAray[i+1]= returnedArray[i];
}
//returnCurrAray[0]=idx;
return returnCurrAray;
}else{
return returnedArray;
}
}
}
}
Thank u sir🥺❤
Most welcome 😊Keep watching