# Data structure for efficient group lookup

I need a data structure, which allows efficient queries for 'give me the group of x'.

Let me give you an example:

Group 1: [a, b, c]
Group 2: [d, e]
Group 3: [f]

getGroupOf(d) -> [d, e]


There are no significant constraints on storage or construction time. I only need getGroupOf to be O(logn) or faster.

I am thinking about using a Dictionary<Element, Set<Element>> where entries for all elements in a group share the same set reference. This would make lookup effectively O(1) or O(logn) depending on the dictionary implementation, but would result in a lot of entries.

This feels fairly bloated, and I am wondering: is there is a more elegant data structure to accomplish this?

Edit: the elements in a group can be completely arbitrary and they have no ordering.

• In your example the groups are formed by contiguous sequences of elements. Is this always the case? If so you can get away by only saving at which points the groups change (in this case $d$ and $f$).
– orlp
Commented Jul 15, 2020 at 14:01
• @orlp No, the groups can be completely arbitrary. The elements do not have an ordering. Commented Jul 15, 2020 at 14:45
• It doesn't seem bloated to me -- both hashtables and BSTs need $O(n)$ space to store $n$ elements, which is optimal up to constant factors. You can use a single Element object and keep 2 references to it (one for the key, one for the unique Set containing it). If you want to avoid keeping 2 references per element, can order the elements somehow and don't mind $O(k)$ time to find a group having $k$ elements, another option would be to use a Dictionary<Element, Element>, where each entry points to the next element in the given order, or to the first if it is the last. Commented Jul 15, 2020 at 16:34
• What formal language are you using? The data-structure that you call a 'group' is more commonly known as a list. Commented Jul 15, 2020 at 22:07
• And if unordered, a set. Commented Jul 15, 2020 at 22:09