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 <rajkumar.cs...@gmail.com> 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, > 10it60...@iitkgp.ac.in -- 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.
