@Saurabh: If you can use O(n) extra space, make a copy of the array and sort it: O(n log n). Then, if there is a solution, there will be a solution of the form (a[i], a[i+1], a[i+2]), where 0 <= i < n-2, which can be checked with a simple for loop: O(n). Thus, the complexity is O(n log n).
Dave On Aug 23, 12:04 am, saurabh agrawal <[email protected]> wrote: > Given an array, find out whether there exists a triplet which can form sides > of triangle. > You are not allowed to modify the array. > > PLease dont give o(n^3) solution > > there exists a solution with nlog(n) i think -- 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.
