@all Does the problem remain unsolved? @ritu Did you come across the solution under the constraints ?
On Tue, Feb 15, 2011 at 12:47 AM, Abhishek Biswas < [email protected]> wrote: > Hi Ritu, > I was following this problem & I believe I was lost in between. Would > you please let me know what was the original problem? > > This is what my understanding is & the code I have written. It is of O(n) > time complexity & constant space complexity. Let me know if I have mistaken > anything. > > /* > You are given an array (unsorted) and for every element i, find the > first occurrence of an element j (in the remaining array) that is > greater than or equal to i. If no such j occurs then print -1. > Eg: Input---> A={1,3,5,7,6,4,8} > Output---> 3 5 7 8 8 8 -1 > Time Complexity :O(n) > Space Complexity :O(n) > > */ > > #include<iostream> > > using namespace std; > > int main() > { > int input[] = > {8,3,5,1,9,2,4,7,0};//{1,3,5,7,6,4,8};//{7,6,5,10,8,6,4,7,9}; > int size = sizeof(input)/sizeof(input[0]); > int *output = new int[size]; > int abs_greater, imd_greater; > abs_greater = imd_greater = input[size-1]; > output[size-1] = -1; > std::cout << "Input : "; > for(int i = 0; i < size; i++) > std::cout << input[i] << " "; > std::cout << endl; > while(--size) > { > if(input[size-1] <= input[size]) > { > imd_greater = input[size]; > output[size-1] = input[size]; > } > else > { > if(input[size-1] <= imd_greater) > { > output[size-1] = imd_greater; //{7,6,5,10,8,6,4,7,9} > } > else if (input[size-1] <= abs_greater) > { > output[size-1] = abs_greater; > imd_greater = input[size-1]; > } > else > { > output[size-1] = -1; > abs_greater = input[size-1]; > } > } > } > std::cout << "Output : "; > size = sizeof(input)/sizeof(input[0]); > for(int i = 0; i < size; i++) > std::cout << output[i] << " "; > getchar(); > return 0; > } > > > Thanks, > Abhishek > > > ------------------------------ > *From:* ritu <[email protected]> > *To:* Algorithm Geeks <[email protected]> > *Sent:* Wed, February 2, 2011 9:13:08 AM > *Subject:* [algogeeks] Re: first larger element in unsorted array... > > @Aman > can u explain how creation of tree ll take O(n) time > also ...what abt nodes not having right child > > On Feb 1, 7:22 pm, Aman Goyal <[email protected]> wrote: > > we can create a height balanced tree with all nodes having their value > and > > also their index value.. can be done in o(n) > > then we need to look to d right side of the node and check for > index(greater > > ).. which will be o(log(n)) > > correct me if i m wrong.. > > > > > > > > On Tue, Feb 1, 2011 at 7:50 PM, Aman Goyal <[email protected]> > wrote: > > > this code will work only for this test case, it is wrong for all > > > cases...eg 3 4 9 8 6 7 10 > > > there will be -1 output for 8 and 9 which is actually wrong.. > > > > > On Tue, Feb 1, 2011 at 6:01 PM, Veenus Gupta <[email protected] > >wrote: > > > > >> #define N 7 > > >> int main() > > > > >> { > > >> int a[N]={1,3,5,7,6,4,8}; > > >> int m[N]; > > >> m[N-1]=-1; > > >> for(int i=N-2;i>=0;i--) > > >> { > > >> if(a[i]<=a[i+1]) > > >> m[i]=a[i+1]; > > >> else > > >> m[i]=m[i+1]; > > >> } > > >> for(int i=0;i<N;i++) > > >> cout<<m[i]<<"\t"; > > >> system("pause"); > > >> } > > > > >> On Feb 1, 1:06 pm, abc abc <[email protected]> wrote: > > >> > Guys please check correctness of your algorithm before posting > > > > >> > On Mon, Jan 31, 2011 at 11:47 PM, ritu <[email protected]> > wrote: > > >> > > @Ralph > > >> > > "Build a data structure on array B[1..n] in O(n) time such that > > >> > > > the following problem can be solved in O(log n) time: > > >> > > > Given an index i and value v, find the index j of the > first > > >> > > > element in B such that j >= i and B[j] > v. > > >> > > > Return -1 if no such j exists. > > >> > > > " > > > > >> > > then it ll take n*lg(n) time ... while a o(n) solution exists > > > > >> > > On Jan 31, 9:25 pm, Ralph Boland <[email protected]> wrote: > > >> > > > On Jan 30, 11:00 pm, ritu <[email protected]> wrote: > > > > >> > > > > You are given an array (unsorted) and for every element i, > find > > >> the > > >> > > > > first occurance of an element j (in the remaining array) that > is > > >> > > > > greater than or equal to i. If no such j occurs then print -1. > > >> > > > > Eg: Input---> A={1,3,5,7,6,4,8} > > >> > > > > Output---> 3 5 7 8 8 8 -1 > > >> > > > > Time Complexity:O(n) > > >> > > > > Space Complexity:O(n) > > > > >> > > > I solved a version of this problem in my thesis. > > > > >> > > > Build a data structure on array B[1..n] in O(n) time such that > > >> > > > the following problem can be solved in O(log n) time: > > >> > > > Given an index i and value v, find the index j of the > first > > >> > > > element in B such that j >= i and B[j] > v. > > >> > > > Return -1 if no such j exists. > > > > >> > > > I have an application of this data structure in my thesis (which > > >> > > > is why I invented it) but I would love to hear other > applications. > > > > >> > > > Ralph Boland > > > > >> > > -- > > >> > > You received this message because you are subscribed to the Google > > >> Groups > > >> > > "Algorithm Geeks" group. > > >> > > To post to this group, send email to [email protected]. > > >> > > To unsubscribe from this group, send email to > > >> > > [email protected] > <algogeeks%2Bunsubscribe@googlegroups.com> > > >> <algogeeks%2Bunsubscribe@googlegroups .com> > > >> > > . > > >> > > For more options, visit this group at > > >> > >http://groups.google.com/group/algogeeks?hl=en. > > > > >> -- > > >> You received this message because you are subscribed to the Google > Groups > > >> "Algorithm Geeks" group. > > >> To post to this group, send email to [email protected]. > > >> To unsubscribe from this group, send email to > > >> [email protected] > <algogeeks%2Bunsubscribe@googlegroups.com> > > >> . > > >> For more options, visit this group at > > >>http://groups.google.com/group/algogeeks?hl=en.- Hide quoted text - > > > > - Show quoted text - > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to [email protected]. > To unsubscribe from this group, send email to algogeeks+ > [email protected]. > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to [email protected]. > To unsubscribe from this group, send email to > [email protected]. > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > -- Thanks & Regards Nikhil Agarwal Senior Undergraduate Computer Science & Engineering, National Institute Of Technology, Durgapur,India http://tech-nikk.blogspot.com http://beta.freshersworld.com/communities/nitd -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
