Search between a Gas Station

Finding kth frequency letter in a string of characters I have a string say "aaabbacccd" here count[a]=4 count[b]=2 count[c]=3 and count[d]=1 . I have to find character with nth largest frequency. In the above string the character with 3rd highest frequency is b (because 1<2<3<4) and count[b]=2 The straight forward solution is storing character Vs frequency in a map and sorting the values using sorting collection by value method like below public class MapUtil { public static <K, V extends Comparable<? super V>> Map<K, V> sortByValue(Map<K, V> map) { List<Map.Entry<K, V>> list = new LinkedList<Map.Entry<K, V>>(map.entrySet()); Collections.sort( list, new Comparator<Map.Entry<K, V>>() { public int compare(Map.Entry<K, V> o1, Map.Entry<K, V> o2) { return (o1.getValue()).compareTo( o2.getValue() ); } }); Map<K, V> result = new LinkedHashMap<K, ...

Count greater elements to the right of self This question below given is driving me nuts.If anyone can help, please. "Given an array Num of 'n' elements return an array A of length 'n' in which A[i] contains number of elements greater than Num[i] to its right in the initial array" I saw an SO answer here but its contains solution of O(n^2). I need a solution of O(nlogn) . I have solution for "Count smaller elements to left of self". But modifying it didn't give me the required solution(refer for code below). Any help is appreciated:) class BinarySearchTreeNode(object): def __init__(self, val): self.val = val self.left = None self.right = None self.count = 1 self.leftTreeSize = 0 class BinarySearchTree(object): def __init__(self): self.root = None def insert(self, val, root): if not root: self.root = BinarySearchTreeNode(val) return 0 if val == root.val: root.count += 1 retur...