Logic behind O(n) solution for 'Maximum length sub-array having given sum'












3












$begingroup$


I am unable to understand the logic behind O(n) solution of this classical problem- Maximum length sub-array having given sum(Negative numbers included),



I read that it can be solved in O(n) time complexity and O(n) space complexity, but the logic behind it is still unclear to me. I have read the solution from below link,



https://www.geeksforgeeks.org/longest-sub-array-sum-k/



Could someone please elaborate on the solution provided for this problem. Thanks a lot in advance.










share|cite|improve this question







New contributor




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







$endgroup$








  • 1




    $begingroup$
    Your question should be self-contained, could you quote relevant parts? Thank you.
    $endgroup$
    – Evil
    7 hours ago
















3












$begingroup$


I am unable to understand the logic behind O(n) solution of this classical problem- Maximum length sub-array having given sum(Negative numbers included),



I read that it can be solved in O(n) time complexity and O(n) space complexity, but the logic behind it is still unclear to me. I have read the solution from below link,



https://www.geeksforgeeks.org/longest-sub-array-sum-k/



Could someone please elaborate on the solution provided for this problem. Thanks a lot in advance.










share|cite|improve this question







New contributor




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







$endgroup$








  • 1




    $begingroup$
    Your question should be self-contained, could you quote relevant parts? Thank you.
    $endgroup$
    – Evil
    7 hours ago














3












3








3


1



$begingroup$


I am unable to understand the logic behind O(n) solution of this classical problem- Maximum length sub-array having given sum(Negative numbers included),



I read that it can be solved in O(n) time complexity and O(n) space complexity, but the logic behind it is still unclear to me. I have read the solution from below link,



https://www.geeksforgeeks.org/longest-sub-array-sum-k/



Could someone please elaborate on the solution provided for this problem. Thanks a lot in advance.










share|cite|improve this question







New contributor




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







$endgroup$




I am unable to understand the logic behind O(n) solution of this classical problem- Maximum length sub-array having given sum(Negative numbers included),



I read that it can be solved in O(n) time complexity and O(n) space complexity, but the logic behind it is still unclear to me. I have read the solution from below link,



https://www.geeksforgeeks.org/longest-sub-array-sum-k/



Could someone please elaborate on the solution provided for this problem. Thanks a lot in advance.







algorithms time-complexity space-complexity






share|cite|improve this question







New contributor




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











share|cite|improve this question







New contributor




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









share|cite|improve this question




share|cite|improve this question






New contributor




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









asked 7 hours ago









Raj MalhotraRaj Malhotra

1162




1162




New contributor




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





New contributor





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






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








  • 1




    $begingroup$
    Your question should be self-contained, could you quote relevant parts? Thank you.
    $endgroup$
    – Evil
    7 hours ago














  • 1




    $begingroup$
    Your question should be self-contained, could you quote relevant parts? Thank you.
    $endgroup$
    – Evil
    7 hours ago








1




1




$begingroup$
Your question should be self-contained, could you quote relevant parts? Thank you.
$endgroup$
– Evil
7 hours ago




$begingroup$
Your question should be self-contained, could you quote relevant parts? Thank you.
$endgroup$
– Evil
7 hours ago










2 Answers
2






active

oldest

votes


















4












$begingroup$

This is an example of a dynamic algorithm. I will adapt the algorithm in the link, as I don't think that it is written in the most helpful way.




  1. Initialise sum = 0 and maxLen = 0.

  2. Create a hash table having (sum, index) tuples.

  3. For i = 0 to n-1, perform the following steps:


    1. Set sum = sum + arr[i].

    2. If sum == k, update maxLen = i+1, continue from here to next iteration.

    3. Check whether sum is present in the hash table or not. If not present, then add it to the hash table as (sum, i) pair.

    4. Check if (sum-k) is present in the hash table or not. If present, then obtain index of (sum-k) from the hash table as index. Now check if maxLen < (i-index), then update maxLen = (i-index).
      Return maxLen.




If sum == k at case 3.3, then we know that the sub-array [a[0],...,a[i-1]] is the maximum-length sub-array whose sum is k. Otherwise, we continue to 3.3. If there was no sub-array until now whose sum we equal to the current sum, then we add (sum, i) to the hash table. The reason we don't overwrite existing entries will become apparent at the end.



We now continue to 3.4. If we came across a sub-array S whose sum was sum - k, then there must be pair of the form (sum - k, index) in the hash table. S is therefore the sub-array of the form [a[0], ..., a[index]].



We obtain a new sub-array [a[index + 1], ..., a[i]] whose sum is k and whose length is i - index as follows: Remove all elements in S from the sub-array [a[0], ..., a[i]]. Its sum must be sum - (sum - k) = k. Now the question is whether the length of the new sub-array i - index > maxLen. If it is, set maxLen = i - index.



Now we can see why we didn't update existing entries in 3.3. We do not want to add larger arrays (greater index) for a given sum. This would have made i - index smaller.



This is a polynomial-time algorithm, as we look at each element exactly once, and the hash table accesses are also constant time.






share|cite|improve this answer









$endgroup$





















    3












    $begingroup$

    A sum of consecutive elements in a list can be expressed as:



    $a_j + a_{j+1} + ldots +a_k = (a_1 + ldots + a_k) - (a_1 + ldots + a_{j-1})$



    Let's write



    $S_n := a_1 + ldots + a_n$



    Then if we just go through the list calculating $S_i$ and remembering which numbers we got, we can check at each step whether there's a front part we can subtract off to get a given sum of consecutive elements.






    share|cite|improve this answer









    $endgroup$













      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.ready(function() {
      var channelOptions = {
      tags: "".split(" "),
      id: "419"
      };
      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',
      autoActivateHeartbeat: false,
      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
      });


      }
      });






      Raj Malhotra 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%2fcs.stackexchange.com%2fquestions%2f104257%2flogic-behind-on-solution-for-maximum-length-sub-array-having-given-sum%23new-answer', 'question_page');
      }
      );

      Post as a guest















      Required, but never shown

























      2 Answers
      2






      active

      oldest

      votes








      2 Answers
      2






      active

      oldest

      votes









      active

      oldest

      votes






      active

      oldest

      votes









      4












      $begingroup$

      This is an example of a dynamic algorithm. I will adapt the algorithm in the link, as I don't think that it is written in the most helpful way.




      1. Initialise sum = 0 and maxLen = 0.

      2. Create a hash table having (sum, index) tuples.

      3. For i = 0 to n-1, perform the following steps:


        1. Set sum = sum + arr[i].

        2. If sum == k, update maxLen = i+1, continue from here to next iteration.

        3. Check whether sum is present in the hash table or not. If not present, then add it to the hash table as (sum, i) pair.

        4. Check if (sum-k) is present in the hash table or not. If present, then obtain index of (sum-k) from the hash table as index. Now check if maxLen < (i-index), then update maxLen = (i-index).
          Return maxLen.




      If sum == k at case 3.3, then we know that the sub-array [a[0],...,a[i-1]] is the maximum-length sub-array whose sum is k. Otherwise, we continue to 3.3. If there was no sub-array until now whose sum we equal to the current sum, then we add (sum, i) to the hash table. The reason we don't overwrite existing entries will become apparent at the end.



      We now continue to 3.4. If we came across a sub-array S whose sum was sum - k, then there must be pair of the form (sum - k, index) in the hash table. S is therefore the sub-array of the form [a[0], ..., a[index]].



      We obtain a new sub-array [a[index + 1], ..., a[i]] whose sum is k and whose length is i - index as follows: Remove all elements in S from the sub-array [a[0], ..., a[i]]. Its sum must be sum - (sum - k) = k. Now the question is whether the length of the new sub-array i - index > maxLen. If it is, set maxLen = i - index.



      Now we can see why we didn't update existing entries in 3.3. We do not want to add larger arrays (greater index) for a given sum. This would have made i - index smaller.



      This is a polynomial-time algorithm, as we look at each element exactly once, and the hash table accesses are also constant time.






      share|cite|improve this answer









      $endgroup$


















        4












        $begingroup$

        This is an example of a dynamic algorithm. I will adapt the algorithm in the link, as I don't think that it is written in the most helpful way.




        1. Initialise sum = 0 and maxLen = 0.

        2. Create a hash table having (sum, index) tuples.

        3. For i = 0 to n-1, perform the following steps:


          1. Set sum = sum + arr[i].

          2. If sum == k, update maxLen = i+1, continue from here to next iteration.

          3. Check whether sum is present in the hash table or not. If not present, then add it to the hash table as (sum, i) pair.

          4. Check if (sum-k) is present in the hash table or not. If present, then obtain index of (sum-k) from the hash table as index. Now check if maxLen < (i-index), then update maxLen = (i-index).
            Return maxLen.




        If sum == k at case 3.3, then we know that the sub-array [a[0],...,a[i-1]] is the maximum-length sub-array whose sum is k. Otherwise, we continue to 3.3. If there was no sub-array until now whose sum we equal to the current sum, then we add (sum, i) to the hash table. The reason we don't overwrite existing entries will become apparent at the end.



        We now continue to 3.4. If we came across a sub-array S whose sum was sum - k, then there must be pair of the form (sum - k, index) in the hash table. S is therefore the sub-array of the form [a[0], ..., a[index]].



        We obtain a new sub-array [a[index + 1], ..., a[i]] whose sum is k and whose length is i - index as follows: Remove all elements in S from the sub-array [a[0], ..., a[i]]. Its sum must be sum - (sum - k) = k. Now the question is whether the length of the new sub-array i - index > maxLen. If it is, set maxLen = i - index.



        Now we can see why we didn't update existing entries in 3.3. We do not want to add larger arrays (greater index) for a given sum. This would have made i - index smaller.



        This is a polynomial-time algorithm, as we look at each element exactly once, and the hash table accesses are also constant time.






        share|cite|improve this answer









        $endgroup$
















          4












          4








          4





          $begingroup$

          This is an example of a dynamic algorithm. I will adapt the algorithm in the link, as I don't think that it is written in the most helpful way.




          1. Initialise sum = 0 and maxLen = 0.

          2. Create a hash table having (sum, index) tuples.

          3. For i = 0 to n-1, perform the following steps:


            1. Set sum = sum + arr[i].

            2. If sum == k, update maxLen = i+1, continue from here to next iteration.

            3. Check whether sum is present in the hash table or not. If not present, then add it to the hash table as (sum, i) pair.

            4. Check if (sum-k) is present in the hash table or not. If present, then obtain index of (sum-k) from the hash table as index. Now check if maxLen < (i-index), then update maxLen = (i-index).
              Return maxLen.




          If sum == k at case 3.3, then we know that the sub-array [a[0],...,a[i-1]] is the maximum-length sub-array whose sum is k. Otherwise, we continue to 3.3. If there was no sub-array until now whose sum we equal to the current sum, then we add (sum, i) to the hash table. The reason we don't overwrite existing entries will become apparent at the end.



          We now continue to 3.4. If we came across a sub-array S whose sum was sum - k, then there must be pair of the form (sum - k, index) in the hash table. S is therefore the sub-array of the form [a[0], ..., a[index]].



          We obtain a new sub-array [a[index + 1], ..., a[i]] whose sum is k and whose length is i - index as follows: Remove all elements in S from the sub-array [a[0], ..., a[i]]. Its sum must be sum - (sum - k) = k. Now the question is whether the length of the new sub-array i - index > maxLen. If it is, set maxLen = i - index.



          Now we can see why we didn't update existing entries in 3.3. We do not want to add larger arrays (greater index) for a given sum. This would have made i - index smaller.



          This is a polynomial-time algorithm, as we look at each element exactly once, and the hash table accesses are also constant time.






          share|cite|improve this answer









          $endgroup$



          This is an example of a dynamic algorithm. I will adapt the algorithm in the link, as I don't think that it is written in the most helpful way.




          1. Initialise sum = 0 and maxLen = 0.

          2. Create a hash table having (sum, index) tuples.

          3. For i = 0 to n-1, perform the following steps:


            1. Set sum = sum + arr[i].

            2. If sum == k, update maxLen = i+1, continue from here to next iteration.

            3. Check whether sum is present in the hash table or not. If not present, then add it to the hash table as (sum, i) pair.

            4. Check if (sum-k) is present in the hash table or not. If present, then obtain index of (sum-k) from the hash table as index. Now check if maxLen < (i-index), then update maxLen = (i-index).
              Return maxLen.




          If sum == k at case 3.3, then we know that the sub-array [a[0],...,a[i-1]] is the maximum-length sub-array whose sum is k. Otherwise, we continue to 3.3. If there was no sub-array until now whose sum we equal to the current sum, then we add (sum, i) to the hash table. The reason we don't overwrite existing entries will become apparent at the end.



          We now continue to 3.4. If we came across a sub-array S whose sum was sum - k, then there must be pair of the form (sum - k, index) in the hash table. S is therefore the sub-array of the form [a[0], ..., a[index]].



          We obtain a new sub-array [a[index + 1], ..., a[i]] whose sum is k and whose length is i - index as follows: Remove all elements in S from the sub-array [a[0], ..., a[i]]. Its sum must be sum - (sum - k) = k. Now the question is whether the length of the new sub-array i - index > maxLen. If it is, set maxLen = i - index.



          Now we can see why we didn't update existing entries in 3.3. We do not want to add larger arrays (greater index) for a given sum. This would have made i - index smaller.



          This is a polynomial-time algorithm, as we look at each element exactly once, and the hash table accesses are also constant time.







          share|cite|improve this answer












          share|cite|improve this answer



          share|cite|improve this answer










          answered 4 hours ago









          justinpcjustinpc

          22119




          22119























              3












              $begingroup$

              A sum of consecutive elements in a list can be expressed as:



              $a_j + a_{j+1} + ldots +a_k = (a_1 + ldots + a_k) - (a_1 + ldots + a_{j-1})$



              Let's write



              $S_n := a_1 + ldots + a_n$



              Then if we just go through the list calculating $S_i$ and remembering which numbers we got, we can check at each step whether there's a front part we can subtract off to get a given sum of consecutive elements.






              share|cite|improve this answer









              $endgroup$


















                3












                $begingroup$

                A sum of consecutive elements in a list can be expressed as:



                $a_j + a_{j+1} + ldots +a_k = (a_1 + ldots + a_k) - (a_1 + ldots + a_{j-1})$



                Let's write



                $S_n := a_1 + ldots + a_n$



                Then if we just go through the list calculating $S_i$ and remembering which numbers we got, we can check at each step whether there's a front part we can subtract off to get a given sum of consecutive elements.






                share|cite|improve this answer









                $endgroup$
















                  3












                  3








                  3





                  $begingroup$

                  A sum of consecutive elements in a list can be expressed as:



                  $a_j + a_{j+1} + ldots +a_k = (a_1 + ldots + a_k) - (a_1 + ldots + a_{j-1})$



                  Let's write



                  $S_n := a_1 + ldots + a_n$



                  Then if we just go through the list calculating $S_i$ and remembering which numbers we got, we can check at each step whether there's a front part we can subtract off to get a given sum of consecutive elements.






                  share|cite|improve this answer









                  $endgroup$



                  A sum of consecutive elements in a list can be expressed as:



                  $a_j + a_{j+1} + ldots +a_k = (a_1 + ldots + a_k) - (a_1 + ldots + a_{j-1})$



                  Let's write



                  $S_n := a_1 + ldots + a_n$



                  Then if we just go through the list calculating $S_i$ and remembering which numbers we got, we can check at each step whether there's a front part we can subtract off to get a given sum of consecutive elements.







                  share|cite|improve this answer












                  share|cite|improve this answer



                  share|cite|improve this answer










                  answered 4 hours ago









                  Daniel McLauryDaniel McLaury

                  39416




                  39416






















                      Raj Malhotra is a new contributor. Be nice, and check out our Code of Conduct.










                      draft saved

                      draft discarded


















                      Raj Malhotra is a new contributor. Be nice, and check out our Code of Conduct.













                      Raj Malhotra is a new contributor. Be nice, and check out our Code of Conduct.












                      Raj Malhotra is a new contributor. Be nice, and check out our Code of Conduct.
















                      Thanks for contributing an answer to Computer Science 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.




                      draft saved


                      draft discarded














                      StackExchange.ready(
                      function () {
                      StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcs.stackexchange.com%2fquestions%2f104257%2flogic-behind-on-solution-for-maximum-length-sub-array-having-given-sum%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

                      A CLEAN and SIMPLE way to add appendices to Table of Contents and bookmarks

                      Calculate evaluation metrics using cross_val_predict sklearn

                      Insert data from modal to MySQL (multiple modal on website)