Hackerrank “Almost Equal” solution











up vote
1
down vote

favorite












I've spent the best part of a day on this question. It is marked as Expert which is way above my level but I gave it my best attempt. 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;
}









share|improve this question









New contributor




Mark Peter Mc Adam is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
























    up vote
    1
    down vote

    favorite












    I've spent the best part of a day on this question. It is marked as Expert which is way above my level but I gave it my best attempt. 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;
    }









    share|improve this question









    New contributor




    Mark Peter Mc Adam is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
    Check out our Code of Conduct.






















      up vote
      1
      down vote

      favorite









      up vote
      1
      down vote

      favorite











      I've spent the best part of a day on this question. It is marked as Expert which is way above my level but I gave it my best attempt. 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;
      }









      share|improve this question









      New contributor




      Mark Peter Mc Adam is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
      Check out our Code of Conduct.











      I've spent the best part of a day on this question. It is marked as Expert which is way above my level but I gave it my best attempt. 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;
      }






      java performance algorithm sorting quick-sort






      share|improve this question









      New contributor




      Mark Peter Mc Adam is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
      Check out our Code of Conduct.











      share|improve this question









      New contributor




      Mark Peter Mc Adam is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
      Check out our Code of Conduct.









      share|improve this question




      share|improve this question








      edited 5 mins ago









      Jamal

      30.2k11115226




      30.2k11115226






      New contributor




      Mark Peter Mc Adam is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
      Check out our Code of Conduct.









      asked 2 hours ago









      Mark Peter Mc Adam

      62




      62




      New contributor




      Mark Peter Mc Adam is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
      Check out our Code of Conduct.





      New contributor





      Mark Peter Mc Adam is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
      Check out our Code of Conduct.






      Mark Peter Mc Adam is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
      Check out our Code of Conduct.






















          1 Answer
          1






          active

          oldest

          votes

















          up vote
          0
          down vote













          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).






          share|improve this answer





















            Your Answer





            StackExchange.ifUsing("editor", function () {
            return StackExchange.using("mathjaxEditing", function () {
            StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
            StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["\$", "\$"]]);
            });
            });
            }, "mathjax-editing");

            StackExchange.ifUsing("editor", function () {
            StackExchange.using("externalEditor", function () {
            StackExchange.using("snippets", function () {
            StackExchange.snippets.init();
            });
            });
            }, "code-snippets");

            StackExchange.ready(function() {
            var channelOptions = {
            tags: "".split(" "),
            id: "196"
            };
            initTagRenderer("".split(" "), "".split(" "), channelOptions);

            StackExchange.using("externalEditor", function() {
            // Have to fire editor after snippets, if snippets enabled
            if (StackExchange.settings.snippets.snippetsEnabled) {
            StackExchange.using("snippets", function() {
            createEditor();
            });
            }
            else {
            createEditor();
            }
            });

            function createEditor() {
            StackExchange.prepareEditor({
            heartbeatType: 'answer',
            convertImagesToLinks: false,
            noModals: true,
            showLowRepImageUploadWarning: true,
            reputationToPostImages: null,
            bindNavPrevention: true,
            postfix: "",
            imageUploader: {
            brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
            contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
            allowUrls: true
            },
            onDemand: true,
            discardSelector: ".discard-answer"
            ,immediatelyShowMarkdownHelp:true
            });


            }
            });






            Mark Peter Mc Adam is a new contributor. Be nice, and check out our Code of Conduct.










            draft saved

            draft discarded


















            StackExchange.ready(
            function () {
            StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcodereview.stackexchange.com%2fquestions%2f209489%2fhackerrank-almost-equal-solution%23new-answer', 'question_page');
            }
            );

            Post as a guest















            Required, but never shown

























            1 Answer
            1






            active

            oldest

            votes








            1 Answer
            1






            active

            oldest

            votes









            active

            oldest

            votes






            active

            oldest

            votes








            up vote
            0
            down vote













            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).






            share|improve this answer

























              up vote
              0
              down vote













              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).






              share|improve this answer























                up vote
                0
                down vote










                up vote
                0
                down vote









                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).






                share|improve this answer












                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).







                share|improve this answer












                share|improve this answer



                share|improve this answer










                answered 1 hour ago









                Eran

                311312




                311312






















                    Mark Peter Mc Adam is a new contributor. Be nice, and check out our Code of Conduct.










                    draft saved

                    draft discarded


















                    Mark Peter Mc Adam is a new contributor. Be nice, and check out our Code of Conduct.













                    Mark Peter Mc Adam is a new contributor. Be nice, and check out our Code of Conduct.












                    Mark Peter Mc Adam is a new contributor. Be nice, and check out our Code of Conduct.
















                    Thanks for contributing an answer to Code Review Stack Exchange!


                    • Please be sure to answer the question. Provide details and share your research!

                    But avoid



                    • Asking for help, clarification, or responding to other answers.

                    • Making statements based on opinion; back them up with references or personal experience.


                    Use MathJax to format equations. MathJax reference.


                    To learn more, see our tips on writing great answers.





                    Some of your past answers have not been well-received, and you're in danger of being blocked from answering.


                    Please pay close attention to the following guidance:


                    • Please be sure to answer the question. Provide details and share your research!

                    But avoid



                    • Asking for help, clarification, or responding to other answers.

                    • Making statements based on opinion; back them up with references or personal experience.


                    To learn more, see our tips on writing great answers.




                    draft saved


                    draft discarded














                    StackExchange.ready(
                    function () {
                    StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcodereview.stackexchange.com%2fquestions%2f209489%2fhackerrank-almost-equal-solution%23new-answer', 'question_page');
                    }
                    );

                    Post as a guest















                    Required, but never shown





















































                    Required, but never shown














                    Required, but never shown












                    Required, but never shown







                    Required, but never shown

































                    Required, but never shown














                    Required, but never shown












                    Required, but never shown







                    Required, but never shown







                    Popular posts from this blog

                    404 Error Contact Form 7 ajax form submitting

                    How to know if a Active Directory user can login interactively

                    TypeError: fit_transform() missing 1 required positional argument: 'X'