mbriskar
BAN USERIn the most voted answers you have to compute hash of each word (by that time you could already tell that the word is left/right) or there is quite complicated algorithm
My proposal is just to do this:
a) prepare set of left letter and right letters
a2) prepare String max, String min
b) scan every word
b1) for every single letter, prepare/initialize boolean isLeft =true; isRight=true;
b2) if the letter is from right, set isLeft=false, the same for the left
b3) after scanning the whole word, if isLeft || isRight is true, then check if it's length is bigger than max or smaller than min and in such case, set it there.
After getting through all of the words,you are done.
I will tell how it is possible to partly add BST to make it slightly faster, but still worst-case is O(n^2). It is not purely my idea, I saw it in some other thread with similar question.
You may sort it by height and take the heighest first, slowly building the BST, where each node has an information about the number of people that are in his left branch. So imagine we have already some BST built. Now we have a human X with T taller people that we want to put into this BST. In case T is lower than root.T, we go into the left branch adding +1 to the root.T. In case it is bigger, we add root.T into our variable that sums the parent.T and go into right branch.
I think this is wrong and works only for the arrays with the same size.
- mbriskar May 10, 2015Counterexample may be 1,2,3.....20 vs 10000,10001,10002,10003,10004,10005,10006. Median in the first is 10,5 and in both should be 14,5. However already after the second median check we will be looking for the median in 15-20 vs 10000 - 100001. This is because the jumps in each array are not the same and therefore you may end up skipping more elements in the first array that are contained in the second array.