Is there a data structure that is directly applicable to this problem? I've come up with a few different approaches but they are all too slow. With a little probing I found that O(NlogN + Z) [where Z is the sum of all r-l] is right at the edge of the 3-second limit, so I am led to believe that you need to be able to answer each query without looking at each node in the range. That means either some kind of precomputed fast lookup for the range, or a dynamic programming approach where you re-use the results of previous queries. I don't think dynamic programming is the answer because when you get a new query that overlaps with a previous one you might know how many pairs were within the previous range but you still have to consider pairs between the two ranges.

My last best attempt was to group the wrestlers into clusters where the difference between the shortest wrestler and tallest wrestler in the cluster was <= k. Then sort the wrestler indices within each cluster. Then for a given query, you can find how many wrestlers are in the query range in each cluster by using a binary search. You already know all those wrestlers are valid pairs with each other. There is additional complexity where you have a group of wrestlers that are close in height but the full range is greater than k. I had a plan to address that but just the internal clustering approach was too slow for some test cases.

My gut says that a kd-tree might be the right answer since the queries are essentially on two axes. But I'm not exactly sure what the handling of the height-axis would look like.

I'd love to hear if I'm on the right track or a push in the right direction. Thanks!

C++ doesn't include k in the solve function definition... Given code is incomplete.

Can anybody please explain solution?

A brute force solution, good to compare against a routine:

// Complete the solve function below.
static int[] solve(int[] h, int difference, int[][] queries) {
    List<int> ret = new List<int>();
    for(int query=0; query < queries.Length; query++)
    {
        int inicio = queries[query][0];
        int fim = queries[query][1];
        int total = 0;
        for(int iextertno = inicio; iextertno < fim; iextertno++)
        {
            for(int iinterno = iextertno+1; iinterno <= fim; iinterno++)
            {
                int diff = Math.Abs(h[iextertno] - h[iinterno]);
                if(diff <= difference)
                    total++;
            }
        }
        ret.Add(total);
    }
    return ret.ToArray();
}

I'm solving it in Java and I can see the solve method does not have the difference K value to calculate. So I'm changing the method definition, is it acceptable ?