Given an array, and a series of queries for indices `i j` how do I find out which index has been queried the most number of times efficiently?

Question

Given an array A, indexed from 0 to n-1 where n is the size of the array, and a series of queries of the form i j where i and j indicate indices (i and j inclusive), how do I find out which index has been queries the most number of times efficiently?

For example, consider an array [3,4,5,6,7,9]

And queries

0 3
3 5
1 2
2 4

Output
Index 0 has been queried 1 time.
Index 1 has been queried 2 times.
Index 2 has been queried 3 times.
Index 3 has been queried 3 times.
Index 4 has been queried 2 times.
Index 5 has been queried 1 time.

How do I make this as fast as possible?

Answer 1

You can do this in O(n+q) where n is size of array and q is the number of queries by:

1. Make empty array A with n entries
2. For each query i,j increase A[i] by 1 and decrease A[j+1] by 1
3. Loop over the array computing the cumulative total and keep track of the index with the highest cumulative total

The cumulative total will contain +1 for each interval where we have seen the start, and -1 for each interval where we have seen the end. This means that the total will give the count of current open intervals, or in other words the number of times that entry has been queried.