DFS + Memoization explanation
1) the only importent thing to remember is the position of first and second player. \n2) if the positions are same than the actual content of array is not impor
1) the only importent thing to remember is the position of first and second player. \n2) if the positions are same than the actual content of array is not importent and can be avoided in recursion.\n3) there will be n*(n-1)/2 pairs of first and second players positions and for each pair recursive fuction will take 2^(n/2) time. Hence the time complexity.  \n\nTime Complexity : **( n ^ 2 * ( 2 ^ (n/2) ) )**\nMemory Complexity : **n ^ 2**\n\n\n\'\'\'\n\n\tint mn=1e9,mx=-1;\n\tset<array<int,3>> st; \n\tvoid recur(int n,int fp, int sp,int cnt){\n\n\t\tif(st.find({n,fp,sp})!=st.end()){ //if the state is already processed \n\t\t\treturn ;\n\t\t}\n\t\tst.insert({n,fp,sp});\n\n\t\tif(sp==n-1-fp){ // if first and second are against each other in this round \n\t\t\tmn=min(mn,cnt);\n\t\t\tmx=max(mx,cnt);\n\t\t\treturn ;\n\t\t}\n\t\t\n\t\tfor(int mask=0; mask<(1<<(n/2)); mask++){\n\t\t\tint nfp=fp,nsp=sp; // new positions. \n\t\t\tfor(int i=0;i<(n/2);i++){\n\t\t\t\tint j=i;\n\t\t\t\tif(mask&(1<<i)){\n\t\t\t\t\tj=n-1-i;\n\t\t\t\t}\n\t\t\t\t// handling the case that first and second \n\t\t\t\t// always win before competing each other .\n\t\t\t\tif(j==fp)\n\t\t\t\t\tj=n-1-j;\n\t\t\t\tif(j==sp)\n\t\t\t\t\tj=n-1-j;\n\n\t\t\t\t// finding the new index of first and second player .\n\t\t\t\t// decrease the index if removed element was before it. \n\t\t\t\tif(j<fp )\n\t\t\t\t\tnfp-=1;\n\t\t\t\tif(j<sp )\n\t\t\t\t\tnsp-=1;\n\t\t\t}\n\t\t\t// recursive step \n\t\t\trecur(n/2+n%2, nfp,nsp,cnt+1);\n\t\t}\n\t}\n\n\n\tclass Solution {\n\tpublic:\n\t\tvector<int> earliestAndLatest(int n, int fp, int sp) {        \n\t\t\tmn=1e9,mx=-1;\n\t\t\tst.clear(); \n\t\t\tfp-=1;\n\t\t\tsp-=1;\n\t\t\trecur(n,fp,sp,0);\n\t\t\treturn {mn+1,mx+1};\n\t\t}\n\t};\n\n\'\'\'
[]