How can I write this algorithm that returns the count between x and y in a list?

I am given this algorithmic problem, and need to find a way to return the count in a list S and another list L that is between some variable x and some variable y, inclusive, that runs in O(1) time:

I've issued a challenge against Jack. He will submit a list of his favorite years (from 0 to 2020). If Jack really likes a year, he may list it multiple times. Since Jack comes up with this list on the fly, it is in no particular order. Specifically, the list is not sorted, nor do years that appear in the list multiple times appear next to each other in the list.

I will also submit such a list of years.

I then will ask Jack to pick a random year between 0 and 2020. Suppose Jack picks the year x.

At the same time, I will also then pick a random year between 0 and 2020. Suppose I pick the year y. Without loss of generality, suppose that x ≤ y.

Once x and y are picked, Jack and I get a very short amount of time (perhaps 5 seconds) to decide if we want to re-do the process of selecting x and y.

If no one asks for a re-do, then we count the number of entries in Jack's list that are between x and y inclusively and the number of entries in my list that are between x and y inclusively.

More technically, here is the situation. You are given lists S and L of m and n integers, respectively, in the range [0, k], representing the collections of years selected by Jack and I. You may preprocess S and L in O(m+n+k) time. You must then give an algorithm that runs in O(1) time – so that I can decide if I need to ask for a re-do – that solves the following problem:

Input: Two integers, x as a member of [0,k] and y as a member of [0,k]

Output: the number of entries in S in the range [x, y], and the number of entries in L in [x, y].

For example, suppose S = {3, 1, 9, 2, 2, 3, 4}. Given x = 2 and y = 3, the returned count would be 4.

I would prefer pseudocode; it helps me understand the problem a bit easier.

Solution

Implementing the approach of user3386109 taking care of edge case of x = 0.

user3386109 : Make a histogram, and then compute the accumulated sum for each entry in the histogram. Suppose S={3,1,9,2,2,3,4} and k is 9. The histogram is H={0,1,2,2,1,0,0,0,0,1}. After accumulating, H={0,1,3,5,6,6,6,6,6,7}. Given x=2 and y=3, the count is H[y] - H[x-1] = H[3] - H[1] = 5 - 1 = 4. Of course, x=0 is a corner case that has to be handled.

# INPUT

S = [3, 1, 9, 2, 2, 3, 4]
L = [2, 9, 4, 6, 8, 5, 3]
k = 9

x = 2
y = 3

# Histogram for S
S_hist = [0]*(k+1)

for element in S:
    S_hist[element] = S_hist[element] + 1

# Storing prefix sum in S_hist 
sum = S_hist[0]
for index in range(1,k+1):
    sum = sum + S_hist[index]
    S_hist[index] = sum


# Similar approach for L

# Histogram for L
L_hist = [0] * (k+1)

for element in L:
    L_hist[element] = L_hist[element] + 1
    
# Stroing prefix sum in L_hist
sum = L_hist[0]
for index in range(1,k+1):
    sum = sum + L_hist[index]
    L_hist[index] = sum
    
# Finding number of elements between x and y (inclusive) in S
print("number of elements between x and y (inclusive) in S:")
if(x == 0):
    print(S_hist[y])
else:
    print(S_hist[y] - S_hist[x-1])
    
# Finding number of elements between x and y (inclusive) in S
print("number of elements between x and y (inclusive) in L:")
if(x == 0):
    print(L_hist[y])
else:
    print(L_hist[y] - L_hist[x-1])