How to efficiently check whether x appears before y in a list

Question

Given a list L in Python, and two elements x and y that are guaranteed to be in L, I wish to know whether x appears before y in L.

If there is only one pair, I can simply loop over L until I find either x or y. This takes time linear in the length of L. But, I have to answer many such queries for the same L (for different x and y). Is there an efficient way, maybe a data structure or iterator in Python, that I can use to answer many queries on the same L quickly?

Answer 1

When it is guaranteed that an element will be found only once in L, you can use a simple dictionary which maps each element to its index. However when an element can appear multiple times, it requires two dictionaries, one for storing the first occurrence of the element, and another for storing the last of it.

L = ["n", "s", "t", "r", "i", "n", "g", "r"]
elem2index_first = {}
elem2index_last = {}

for index, elem in enumerate(L):
    if elem not in elem2index_first:  # Only update on the first occurrence
        elem2index_first[elem] = index
    elem2index_last[elem] = index  # Overwrite on whatever the previous index was

Then, it takes an average of a constant time complexity for each query, since it only requires two dictionary lookups.

print(elem2index_first[x] < elem2index_last[y])  # x comes before y