Re: [algogeeks] Re: Intersection of arrays

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

[algogeeks] Re: Intersection of arrays

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

[algogeeks] Re: Intersection of arrays

you didnt mention if duplicate elements should appear in the intersection or not. If no duplicates necessary, then your language may already have intersection between arrays built in. Or you should write an intersection operator/method between arrays (in ruby it is just the "&" operator). My

[algogeeks] Re: Intersection of arrays

sorry, i made a slight coding mistake in my last post (invisible 7th array) , but the logic remains the same...corrected sample output: arrays: 6 elements in each array: 20 range: 1 to 5 array #1: [3, 4, 3, 4, 5, 3, 2, 2, 1, 4, 2, 3, 4, 4, 3, 1, 3, 2, 4, 4] array #2: [1, 4, 5, 2, 1, 5, 1, 4, 3, 1,

Re: [algogeeks] Re: Intersection of arrays

How is it possible to create a hash map using elements as keys and their counts as values .If we give some key the value is automatically computed by hash function .If u are given an element/key its index/value is calculated by hash function.am i corrct?? On 27 October 2011 22:36, Nitin Garg wrot

Re: [algogeeks] Re: Intersection of arrays

The hashing solution is similar to the 1st answer here A sorting solution will take O(k.n.logn) time On Fri, Oct 28, 2011 at 9:51 AM, Anup Ghatage wrote: > Don, > As you said, the intersection set, won't really

Re: [algogeeks] Re: Intersection of arrays

Don, As you said, the intersection set, won't really be in sorted order as it depends on the elements of the second array, which are unsorted. Still, sorting them wouldn't be much different as it'd be worst case O(n logn).. [ Array 2 == Array 1 ] But sorting the First Array has already cost O(n log

[algogeeks] Re: Intersection of arrays

Hashing all of the K arrays seems like a bit much. How about this? You have K seperate arrays to start with, each array having N elements (is that correct?). 1) Sort the first array. 2) Step through the 2nd array, 1 element at a time say Array(2).element(i) Check to see if the v