Class TreeMap<K,V> | Lower and Upper Count Support

[mayank bansal]

Hi Remi,

Thank you for pointing that out. This is providing the same feature but it
is not the optimal approach for calculating the size.

AscendingSubMap().size() is actually iterating each and every element using
Iterator to calculate the size resulting in the O(N) time complexity which
can be reduced to O(logN) and this will be a huge improvement. Code snippet
for the reference -
https://github.com/openjdk/jdk/blob/master/src/java.base/share/classes/java/util/TreeMap.java#L1937-L1950

I am coming from the fact that I was trying to solve one coding problem, I
tried using own Balanced BST
<https://leetcode.com/submissions/detail/418028305/> (AVL tree) and it
executed in ~180ms and when I tried using TreeSet headSet().size()
<https://leetcode.com/submissions/detail/418070375/>, it resulted in a TLE
- Time Limit Exceeded.



On Sun, Nov 8, 2020 at 4:09 PM Remi Forax <forax at univ-mlv.fr> wrote:

> Is it different from
>  headMap(key, true).size() / tailMap(key, true).size() ?
>
>
> https://docs.oracle.com/en/java/javase/15/docs/api/java.base/java/util/NavigableMap.html#headMap(K,boolean)
>
> https://docs.oracle.com/en/java/javase/15/docs/api/java.base/java/util/NavigableMap.html#tailMap(K,boolean)
>
> cheers,
> Rémi
>
> ----- Mail original -----
> > De: "mayank bansal" <mayankbansal933 at gmail.com>
> > À: "core-libs-dev" <core-libs-dev at openjdk.java.net>
> > Envoyé: Dimanche 8 Novembre 2020 11:22:01
> > Objet: Class TreeMap<K,V> | Lower and Upper Count Support
>
> > Hi Everyone,
> >
> > I would like to propose and work on a feature request of supporting the
> > lower and higher count in java class TreeMap.
> > "lower count" is the number of elements that are strictly less than the
> > given value.
> > "upper count" is the number of elements that are strictly greater than
> the
> > given value.
> >
> > *Method definitions-*
> > int getLowerCount(K key);
> > int getHigherCount(K key);
> >
> > *Follow-up feature -*
> > Class TreeSet<E> constructor initializes the TreeMap<K,V> in the TreeSet
> > constructor.
> > It puts the dummy value as *new Object()* whenever we add the entry in
> > TreeSet.
> > I would like to work on the feature to provide the *Duplicate count* in
> > case of the same Key and the same Value.
> >
> > I will be happy to work on both and raise a PR. I need some guidance if
> the
> > proposed feature looks good and I can start working on it and also would
> > like to know about the process whether I can directly raise the PR.
> >
> > Thanks
> > --
> > Regards,
> > Mayank Bansal
>


-- 
Regards,
Mayank Bansal