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 <ritugarg.c...@gmail.com>
To: Algorithm Geeks <algogeeks@googlegroups.com>
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 <aman.goya...@gmail.com> 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 <aman.goya...@gmail.com> 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 <smartvee...@gmail.com>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 <may.i.answ...@gmail.com> wrote:
> >> > Guys please check correctness of your algorithm before posting
>
> >> > On Mon, Jan 31, 2011 at 11:47 PM, ritu <ritugarg.c...@gmail.com> 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 <rpbol...@gmail.com> wrote:
> >> > > > On Jan 30, 11:00 pm, ritu <ritugarg.c...@gmail.com> 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 algogeeks@googlegroups.com.
> >> > > To unsubscribe from this group, send email to
> >> > >
>algogeeks+unsubscr...@googlegroups.com<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 algogeeks@googlegroups.com.
> >> To unsubscribe from this group, send email to
> >>
>algogeeks+unsubscr...@googlegroups.com<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 algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@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 algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
