@Don: You certainly can get by with only one workspace of size O(n). One side of the partitioning is done in-place, with the other side accumulated in the workspace and then copied back into the input array. That's a lot better than the O(n^2) worst case workspace required by your original algorithm. Dave
On Tuesday, July 16, 2013 10:40:29 AM UTC-5, Don wrote: > It definitely complicates things. I think that I would replaced the vector > parameters with pointers to the beginning and end of each array. The > partition is tricky because you need to make sure that both subtrees end up > in the same order they started in, which is difficult because most > partition algorithms are not stable. That's really the question I was > asking. Can you do that partition in place? > > Don > > > On Sunday, July 14, 2013 2:48:46 PM UTC-4, sourabh wrote: >> >> You don't need to take vector for this you can have input in array also. >> You just need to check the elements in each partition . >> On 12-Jul-2013 8:27 PM, "Don" <[email protected]> wrote: >> >>> Can anyone modify this solution so that it does not duplicate the memory >>> at each level of recursion? >>> >>> (Here is my solution with the fix mentioned above) >>> >>> typedef std::vector<int> btree; >>> >>> bool sameBstFormed(btree t1, btree t2) >>> { >>> bool result; >>> if (t1.size() != t2.size()) result = false; >>> else if (t1.size() == 0) result = true; >>> else if (t1[0] != t2[0]) result = false; >>> else if (t1.size() == 1) result = true; >>> else >>> { >>> btree left1, right1, left2, right2; >>> for(int i = 1; i < t1.size(); ++i) >>> { >>> if (t1[i] < t1[0]) left1.push_back(t1[i]); >>> else right1.push_back(t1[i]); >>> if (t2[i] < t2[0]) left2.push_back(t2[i]); >>> else right2.push_back(t2[i]); >>> } >>> result = sameBstFormed(left1, left2) && sameBstFormed(right1, >>> right2); >>> } >>> return result; >>> } >>> >>> On Tuesday, July 9, 2013 5:41:57 PM UTC-4, Don wrote: >>>> >>>> Yes, you are right. Good catch. >>>> >>>> On Tuesday, July 9, 2013 2:13:47 PM UTC-4, Sambhavna Singh wrote: >>>>> >>>>> Amazing solution Don, thank you :) You missed a small check in the >>>>> code: if(t1[0] != t2[0]) return 0; >>>>> >>>>> >>>>> On Tue, Jul 9, 2013 at 11:27 PM, Don <[email protected]> wrote: >>>>> >>>>>> The trees would be the same if >>>>>> 1. The root is the same >>>>>> 2. The left and right subtrees are both the same >>>>>> >>>>>> bool sameBstFormed(intVector t1, intVector t2) >>>>>> { >>>>>> if (t1.size() != t2.size()) return false; // Trees with >>>>>> different number of nodes can't be the same >>>>>> if (t1.size() == 0) return true; // Two empty trees >>>>>> are equal >>>>>> if (t1.size() == 1) return t1[0] == t2[0]; // Single node trees >>>>>> >>>>>> // Partition left and right subtrees >>>>>> intVector left1, right1, left2, right2; >>>>>> for(int i = 1; i < n1; ++i) >>>>>> { >>>>>> if (t1[i] < t1[0]) left1.add(t1[i]); >>>>>> else right1.add(t1[i]); >>>>>> if (t2[i] < t2[0]) left2.add(t2[i]); >>>>>> else right2.add(t2[i]); >>>>>> } >>>>>> >>>>>> return sameBstFormed(left1, left2) && sameBstFormed(right1, >>>>>> right2); >>>>>> >>>>>> } >>>>>> >>>>>> On Thursday, June 6, 2013 1:57:49 AM UTC-4, Sambhavna Singh wrote: >>>>>>> >>>>>>> I came across this question on careercup: how do we go about finding >>>>>>> whether the BSTs formed by the given input order would be identical or >>>>>>> not >>>>>>> without actually forming the tree? >>>>>>> >>>>>>> Link: >>>>>>> http://www.careercup.**com**/question?id=19016700<http://www.careercup.com/question?id=19016700> >>>>>>> >>>>>> -- >>>>>> 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]**. >>>>>> >>>>>> >>>>>> >>>>> >>>>> -- >>> 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]. >>> >>> >>> >> -- 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].
