4
\$\begingroup\$

I've spent the best part of a day on this question. It is marked as Expert level. There are about fifteen submission test cases and my solution manages to satisfy the first four. However, from there on in it hits timeouts due to performance issues.

Hackerrank question

There doesn't seem to be much information or solutions for this question around, so I would appreciate if anyone had any suggestion on how I can improve the performance. Maybe I need to go back to the drawing board with my approach.

  • N = number of elements in the array
  • K = The height difference allowed
  • H = Array of heights
  • queries = 2D array of ranges within which you must find the number of matching pairs (i.e. how many fighters in this range meet the height requirements to fight each other)

My approach is to copy the subset (I know this is slow and would like to get around it somehow)and then run a quicksort over this new subset.

With this we can now quickly figure out what heights are within range of each other (i.e. if we get height = 1 and we know k = 2, then the maximum height he can fight against is going to be 3).

    static int[] solve(int n, int k, int[] h, int[][] queries) {
    // N = no. heights
    // K = Difference
    // L & R = First and Last fighters
    int[] results = new int[queries.length];
    int count = 1;
    int pairs = 0;
    int l, r =0;

    for(int j=0; j<queries.length; j++) {
        l = queries[j][0];
        r = queries[j][1];
        int[] range = Arrays.copyOfRange(h, l, r+1);

        int[] sortedSubset = sort(range);

        for(int i=0; i<sortedSubset.length-1; i++) {
            count = i+1;
            while((count != sortedSubset.length) && sortedSubset[count] <= (sortedSubset[i]+k)) { 

                // While the current number is still in range of the number we are checking i.e. (number + k)
                pairs++;
                count++;
           }
        }
        results[j] = pairs;
        pairs = 0;
    }

    return results;
}

A Sumo wrestling championship is scheduled to be held this winter in the HackerCity where N wrestlers from different parts of the world are going to participate.
The rules state that two wrestlers can fight against each other if and only if the difference in their height is less than or equal to K, (i.e.)
wrestler A and wrestler B can fight if and only if |height(A)-height(B)|≤K.

Given an array H[], where H[i] represents the height of the ith fighter, for a given l, r where 0 <= l <= r < N, can you count the number of pairs of fighters between l and r (both inclusive) who qualify to play a game?

Input Format
The first line contains an integer N and K separated by a single space representing the number of Sumo wrestlers who are going to participate and the height difference K.
The second line contains N integers separated by a single space, representing their heights H[0] H[1] ... H[N - 1].
The third line contains Q, the number of queries. This is followed by Q lines each having two integers l and r separated by a space.

Output Format
For each query Q, output the corresponding value of the number of pairs of fighters for whom the absolute difference of height is not greater that K.

Constraints
1 <= N <= 100000
0 <= K <= 109
0 <= H[i] <= 109
1 <= Q <= 100000
0 <= l <= r < N

Sample Input

5 2  
1 3 4 3 0  
3  
0 1  
1 3  
0 4  

Sample Output

1  
3  
6  

Explanation
Query #0: Between 0 and 1 we have i,j as (0,1) and |H[0]-H[1]|=2 therefore output is 1.
Query #1: The pairs (H[1],H[2]) (H[1],H[3]) and (H[2],H[3]) are the pairs such that |H[i]-H[j]| <=2. Hence output is 3.
Query #2: Apart from those in Query #1, we have (H[0],H[1]), (H[0], H[3]), (H[0], H[4]), hence 6.

Timelimits

Timelimits are given here

\$\endgroup\$
  • 1
    \$\begingroup\$ In any programming challenge, if you get time limit exceeded then it's back to the drawing board as that means you have the wrong time complexity. Unless you've REALLY messed up the implementation. \$\endgroup\$ – Emily L. Dec 12 '18 at 9:50
  • 2
    \$\begingroup\$ Please reproduce the problem formulation in whole in your question, links rot and you cannot view that page without being registered on HR. \$\endgroup\$ – Emily L. Dec 12 '18 at 17:21
  • \$\begingroup\$ Where is sort() defined? \$\endgroup\$ – Eric Stein Dec 12 '18 at 17:58
  • \$\begingroup\$ It's just a quicksort method to arrange the number. \$\endgroup\$ – Mark Mc Adam Dec 13 '18 at 13:17
1
\$\begingroup\$

Constraints
1 <= N <= 100000
0 <= K <= 109
0 <= H[i] <= 109
1 <= Q <= 100000
0 <= l <= r < N

My rule of thumb for this kind of challenge is that 109 operations is a limit. So, ignoring the hidden constant of Landau notation, we're looking at something which is \$O(N\sqrt N + Q\sqrt Q + Q\sqrt{N} + K)\$. In particular, each query shouldn't take more than \$\sqrt N\$ time. That would seem to push us towards a preprocessing step which is \$O(N\sqrt N + K)\$ and which allows us to process individual queries fast. Alternatively, we might have a preprocessing step which takes into account the queries, but that's likely to be more complicated.

Since your approach takes (in the worst case) \$O(QN\lg N)\$ time, it's definitely nowhere near complying with my rule of thumb.


If we consider first the idea of a preprocessing step which takes into account the queries, it's quite easy to construct a really nasty case where we have boundaries between every consecutive pair of wrestlers, and each one contributes to multiple queries. E.g. take the following 100000 queries:

(0, 99999), (1, 99998), (2, 99997), ..., (49999,50000),
(0, 49999), (1, 50000), (2, 50001), ..., (49999, 99998)

I don't find that approach promising.


Ideas which might be more promising are bucketing the wrestlers in buckets of width \$K\$, so that each wrestler can only interact with those in the same bucket and some of those in the adjacent buckets - although the "some of" is a problem; and inclusion-exclusion, although I can't quite get that to work. It's "fast enough" to precompute tables \$C[a]\$ which is the number of valid fights between \$i \le a < j\$; \$L[a]\$ which is the number of valid fights between \$i < j \le a\$; and \$R[a]\$ which is the number of valid fights between \$a \le i < j\$. But the closest I can get to the number of valid fights between \$l \le i < j \le r\$ is the difference of that with the number of valid fights between \$i \le l\$ and \$j \ge r\$.

\$\endgroup\$
  • \$\begingroup\$ What about having 2 lanes of buckets; one with a phase of K/2 over the other. Each wrestler is in 2 buckets. Is this an idea to work with or am I completely missing the point here? \$\endgroup\$ – dfhwze 7 hours ago
  • \$\begingroup\$ @dfhwze, another, similar, idea I'm tossing around is building a quad tree in each bucket. \$\endgroup\$ – Peter Taylor 5 hours ago
  • \$\begingroup\$ I give you 200 rep if you solve this using Dancing Links :p \$\endgroup\$ – dfhwze 5 hours ago
0
\$\begingroup\$

I suggest you do the following:

  1. Sort the entire heights array once.
  2. Finds all the matching pairs for the full array (i.e. l=0; r=h.length-1;).
  3. For each matching pair you find, loop over the queries array, and add it to the counts of all the subsets that contain both fighters. For example, if the pair h[2],h[5] is matching, increment results[j] for all j such that queries[j][0] <=2 and 5 <= queries[j][1].

I believe running a single sort instead of queries.length sorts will improve the performance.

The only downside of this algorithm is that if all the queries cover a small subset of the full heights array, the algorithm will do a lot of unnecessary work (finding matching pairs for indices that we'll never need to count).

\$\endgroup\$
  • \$\begingroup\$ If you sort the entire array initially, wont you lose the ability to check between certain ranges? You have re-arranged the entire array and so when you read in the left and right values for the subset you are to check, they correspond to the old unsorted array and not the sorted one? \$\endgroup\$ – Mark Mc Adam Dec 12 '18 at 14:28
  • \$\begingroup\$ @Mark I guess my solution is not complete. You'll have to create a Map of the heights to their original indices \$\endgroup\$ – Eran Dec 12 '18 at 14:51
  • \$\begingroup\$ I will give it a try later, I'm not sure it will be an improvment though. For example, if the array of height's is >100,000 and you have only 1 query of indices {2, 6}. You do a lot of unnecessary work, its a tricky question. \$\endgroup\$ – Mark Mc Adam Dec 12 '18 at 15:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.