Also, for the part two of the question, you can simply go in for the *kth largest positive index *in the same hashmap (described earlier for part 1). That solves the part two of the problem :) Hth, *Pralay Biswas* *MS,Comp Sci, * *University of California, Irvine*
On Tue, Feb 5, 2013 at 8:46 PM, Pralay Biswas <[email protected]>wrote: > 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 < > [email protected]> 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 <[email protected]> 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 >> > <[email protected]> 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 [email protected]. >> >> 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 [email protected]. >> > 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 [email protected]. >> 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 [email protected]. For more options, visit https://groups.google.com/groups/opt_out.
