Here is another idea if space is available
Step 1: Go through the whole array, find the maximum. Create a hash table of
the maximum value.
Step 2: Hash the arrays, one by one and re-create them with only unique
elements. (discard on collision)
Step 3: Once you get the unique arrays, create another hash table, but this
time, use the same table for all three arrays.
Hash all entries with a count variable, which gets incremented
on a collision.
Step 4: Traverse the Hash table, display all entries whose count == K
Those are your intersections.
On Fri, Oct 28, 2011 at 8:43 PM, Dumanshu <[email protected]> wrote:
> I think Dan's solution is the best one here. TC O(n log n) and SC O(1)
> where n is the maximum no. of elements in any array
> Instead of starting with K given arrays, just take the first 2.
> Sort both of them - time is nlogn
> Now run two pointers on each array to save the common elements as they
> are and clear the rest in 1st array. Discard 2nd array now.
> We have 1st array with intersection elements only.
> Now continue the same thing - With 1st array and 3rd array. Sort 3rd
> array. Keep common elements in 1st array and clear the rest.
>
> Keeping common elements in 2 arrays and clearing the other elements
> can be done in O(n) TC.
>
> On Oct 25, 11:17 am, kumar raja <[email protected]> wrote:
> > Find intersection of K unsorted array of N elements each. Intersection
> > consists of elements that appear in all the K arrays.
> >
> > what data structure is useful here??
> >
> > --
> > Regards
> > Kumar Raja
> > M.Tech(SIT)
> > IIT Kharagpur,
> > [email protected]
>
> --
> 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.
>
>
--
Anup Ghatage
--
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.
