# Storing $K$ numbers with ordering

Let $$S$$ be a sequence of $$k$$ many numbers. The position of the number in the $$S$$ matters. In the $$S$$ there are only $$j$$ many different numbers are there means $$S$$ contains many duplicates. Position is a query which needed to be answered, position(i) returns the element at position $$i$$ in $$S$$.

Trivial way to store them is using array which will takes $$O(S)$$ space and position can be solved in $$O(1)$$ time.

I am looking for a representation that takes $$O(j)$$ space (or somewhere near to it) and such that position can be solved in $$O(1)$$(even in more time is also ok)?

• @ Daniel Numbers are different and they are $1,2,\ldots, j$. I am looking for deterministic data str. – Shiv Oct 12 '19 at 9:51
• What is the element in position $i$ of a set? Sets do not have order. – orlp Oct 12 '19 at 10:32
What you ask is impossible, assuming you don't really mean sets (as sets are orderless), but ordered tuples. Consider $$j=2$$, then you effectively have $$k$$-length binary strings. And those require $$\Omega(k)$$ storage.
• Ok if space is say $\Omega(K)$ then what is position query time. – I_wil_break_wall Oct 12 '19 at 12:38