I guess the part 1 can be solved in O(n) time and space both. Here is my
approach.
Assume: Array given is arr[] = {2,3,1,2,3,2,4,1,5,6}
1. Given an array, scan thru it, element by element and hash it on a
hashmap with key as the arr[i] as the key and i+1 as the index.
2. There would be two cases
a) arr[i] is already there in the hash map, if so, check if the
hashmap.get(arr[i]) is a negative or not. If it is negative , do nothing.
If its is not negative, negate it.
b) arr[i] is a new element, in such a case, hash key as arr[i] and i+1
as the value.
3. Scan thru the value set, the key corresponding to minimum of positive
values is the answer.
Example.
For {2,3,1,2,3,2,4,1, 5,6}
2 = not seen, hash 2,1 (arr[i], i+1)
3 = not seen, hash 3, 2
1 = not seen, hash 1,3
2 = seen -> is the value corresponding to key 2 negative = No. So negate
it- hash entry now becomes 2,-1
3 = similar to above -> Hash entry is 3,-2
2 = seen, is the value negative = yes, do nothing
4 = not seen, hash 4,8
1 = seen, is the value corresponding to key 1 -ve? No, negate it, hashentry
= 1,-3
5 = not seen, hash 5,10
6= not seen, hash 6,11
Hasmap ready. Whats the value set (the values only) ? -1,-2,-3,8,10,11
Whats the *least minimum of positive values*? 8
Whats the key corresponding to value 8? Its 4.
*4 is the first unique number!*
Please let me know if you need the code, shall send you ova :)
Cheers,
*Pralay*
*MS,Comp Sci, *
*University of California, Irvine*
On Tue, Feb 5, 2013 at 8:30 PM, navneet singh gaur <
navneet.singhg...@gmail.com> wrote:
> nice algo ankit, so it will be nlogn using O (n) space only. What abt
> 2nd Q., which have a big online stream.
>
> On Mon, Feb 4, 2013 at 9:30 PM, kumar ankit <k.anki...@gmail.com> wrote:
> > For 1:
> > i think you can use sorting, sort the array and keep the indices of the
> > numbers in the sorted list.
> > Now traverse the sorted list and in the sorted list you need to find the
> > unique number with the
> > minimum index which is easy to find.
> >
> > Eg: Array: 5 3 1 2 4 1 4
> > Indices: 0 1 2 3 4 5 6
> >
> >
> > After sorting : Array: 1 1 2 3 4 4 5
> > Indices: 2 5 3 1 4 6 1
> >
> > Now you can see the unique number with lowest index is 3(index=1). So ,
> you
> > have your answer.
> >
> >
> > On Mon, Feb 4, 2013 at 3:45 PM, navneet singh gaur
> > <navneet.singhg...@gmail.com> wrote:
> >>
> >> 1. Given a array,find a first unique integer.
> >> 2. Integers are coming as online stream,have to find a kth unique
> integer
> >> till now.
> >>
> >> For 1.
> >>
> >> Even we cannot use sorting for solving this as if we sort it than our
> >> first number which is non-repetitive changes.
> >>
> >> The best I am able to do is nlogn using a space of O( n ).
> >>
> >> For 2. No idea
> >>
> >> --
> >> You received this message because you are subscribed to the Google
> Groups
> >> "Algorithm Geeks" group.
> >> To unsubscribe from this group and stop receiving emails from it, send
> an
> >> email to algogeeks+unsubscr...@googlegroups.com.
> >> For more options, visit https://groups.google.com/groups/opt_out.
> >>
> >>
> >
> >
> >
> >
> > --
> > Kumar Ankit
> > Senior Undergraduate
> > Department of Computer Engineering
> > Institute of Technology
> > Banaras Hindu University
> > Varanasi
> > Ph: +91 9473629892
> >
> > --
> > You received this message because you are subscribed to the Google Groups
> > "Algorithm Geeks" group.
> > To unsubscribe from this group and stop receiving emails from it, send an
> > email to algogeeks+unsubscr...@googlegroups.com.
> > For more options, visit https://groups.google.com/groups/opt_out.
> >
> >
>
>
>
> --
> navneet singh gaur
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To unsubscribe from this group and stop receiving emails from it, send an
> email to algogeeks+unsubscr...@googlegroups.com.
> For more options, visit https://groups.google.com/groups/opt_out.
>
>
>
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to algogeeks+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.
