{"id":3698,"date":"2021-11-12T14:45:26","date_gmt":"2021-11-12T09:15:26","guid":{"rendered":"https:\/\/www.interviewbit.com\/blog\/?p=3698"},"modified":"2021-11-12T14:45:27","modified_gmt":"2021-11-12T09:15:27","slug":"subarray-sum-equals-k","status":"publish","type":"post","link":"https:\/\/www.interviewbit.com\/blog\/subarray-sum-equals-k\/","title":{"rendered":"Subarray Sum Equals K"},"content":{"rendered":"\n<div class=\"gutentoc tocactive nostyle\"><div class=\"gutentoc-toc-wrap\"><div class=\"gutentoc-toc-title-wrap\"><div class=\"gutentoc-toc-title\">Table Of Contents<\/div><div id=\"open\" class=\"toggletwo\">show<\/div><\/div><div id=\"toclist\"><div class=\"gutentoc-toc__list-wrap\"><ul class=\"gutentoc-toc__list\"><li><a href=\"#problem-statement\">Problem Statement<\/a><\/li><li><a href=\"#naive-approach\">Naive Approach<\/a><\/li><ul class=\"gutentoc-toc__list\"><li><a href=\"#c-code\">C++ Code<\/a><\/li><li><a href=\"#java-code\">Java Code<\/a><\/li><li><a href=\"#python-code\">Python Code<\/a><\/li><\/ul><li><a href=\"#optimal-approach\">Optimal Approach<\/a><\/li><ul class=\"gutentoc-toc__list\"><li><a href=\"#c-implementation\">C++ Implementation<\/a><\/li><li><a href=\"#java-implementation\">Java Implementation<\/a><\/li><li><a href=\"#python-implementation\">Python Implementation<\/a><\/li><\/ul><li><a href=\"#faqs\">FAQs<\/a><\/li><\/ul><\/div><\/div><\/div><\/div>\n\n\n\n<h2 id=\"problem-statement\">Problem Statement<\/h2>\n\n\n\n<p>Given an array <strong>a[]<\/strong>, find the number of subarrays in it, which have a sum of <strong>k<\/strong>.<\/p>\n\n\n\n<p><strong>Subarray: <\/strong>A subarray of an array is formed by deleting some(possibly zero) elements from the beginning or end of the array.<\/p>\n\n\n\n<figure class=\"wp-block-image size-full\"><img  loading=\"lazy\"  width=\"754\"  height=\"307\"  src=\"data:image\/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAAl21bKAAAAA1BMVEUAAP+KeNJXAAAAAXRSTlMAQObYZgAAAAlwSFlzAAAOxAAADsQBlSsOGwAAAApJREFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=\"  alt=\"\"  class=\"wp-image-3774 pk-lazyload\"  data-pk-sizes=\"auto\"  data-ls-sizes=\"(max-width: 754px) 100vw, 754px\"  data-pk-src=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Image-2-10.png\"  data-pk-srcset=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Image-2-10.png 754w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Image-2-10-300x122.png 300w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Image-2-10-380x155.png 380w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Image-2-10-550x224.png 550w\" ><\/figure>\n\n\n\n<p>The red region shows a subarray of the original array.<\/p>\n\n\n\n<p id=\"-sample-test-cases-\"><strong>Sample Test Cases<\/strong><\/p>\n\n\n\n<p><strong>Input 1:<\/strong> a = [10, 2, -2, -20, 10], k = -10<br><strong>Output 1:<\/strong> 3<br><strong>Explanation 1:<\/strong> The subarrays are listed as below (1 &#8211; Based Indexing):<\/p>\n\n\n\n<ul><li>[4, 5]<\/li><li>[1, 4]<\/li><li>[2, 5]<\/li><\/ul>\n\n\n\n<p><strong>Input 2:<\/strong> a = [1, 1, 1], k = 2<br><strong>Output 2:<\/strong> 2<br><strong>Explanation 2:<\/strong> All subarrays of length 2 are valid subarrays in this case, and there are a total of 2 such subarrays.<\/p>\n\n\n\n<h2 id=\"naive-approach\">Naive Approach<\/h2>\n\n\n\n<p>The naive approach is to generate all the subarrays of the array and calculate their sum. Whenever we find a subarray with a sum equal to <strong>k, <\/strong>we increment our counter by 1. Finally, we return the count which keeps track of the number of subarrays with a sum equal to <strong>k<\/strong>.<\/p>\n\n\n\n<p>Since there are a total of <strong>(n * (n + 1)) \/ 2<\/strong> subarrays of an array, and each subarray will take<strong> O(n)<\/strong> time to traverse and calculate their sum, the required time complexity of this approach will be cubic in nature.<\/p>\n\n\n\n<h3 id=\"c-code\">C++ Code<\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"cpp\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">int countSubarraysWithSumK(vector &lt; int > &amp; a, int K) {\n  int n = a.size();\n  int count = 0;\n  for (int i = 0; i &lt; n; i++) {\n    for (int j = i; j &lt; n; j++) {\n      int sum = 0;\n      for (int k = i; k &lt;= j; k++) {\n        sum += a[k];\n      }\n      count += (sum == K);\n    }\n  }\n  return count;\n}<\/pre>\n\n\n\n<h3 id=\"java-code\">Java Code<\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"java\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">public static int countSubarraysWithSumK(int[] a, int K) {\n  int n = a.length;\n  int count = 0;\n  for (int i = 0; i &lt; n; i++) {\n    for (int j = i; j &lt; n; j++) {\n      int sum = 0;\n      for (int k = i; k &lt;= j; k++) {\n        sum += a[k];\n      }\n      count += (sum == K ? 1 : 0);\n    }\n  }\n  return count;\n}<\/pre>\n\n\n\n<h3 id=\"python-code\">Python Code<\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"python\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">def countSubarrayswithSumK(a, K):\n    n = len(a)\n    count = 0\n    for i in range(n):\n        for j in range(i, n):\n            sum = 0\n            for k in range(i, j + 1):\n                sum += a[k]\n            count += sum == K\n    return count<\/pre>\n\n\n\n<p><strong>Complexity Analysis<\/strong><\/p>\n\n\n\n<ul><li>Time Complexity: O(n<sup>3<\/sup>)<\/li><li>Space Complexity: O(1)<\/li><\/ul>\n\n\n\n<h2 id=\"optimal-approach\">Optimal Approach<\/h2>\n\n\n\n<p>We can solve this problem in linear time complexity using a <strong>hashmap-based<\/strong> approach. The algorithm is described as follows:<\/p>\n\n\n\n<ul><li>Traverse the array, and keep track of the current running sum up to the <strong>ith<\/strong> index in a variable, say <strong>sum.<\/strong><\/li><li>Also, hash the different values of the <strong>sum<\/strong> obtained so far, into a hashmap.<\/li><li>If the <strong>sum <\/strong>equals <strong>k <\/strong>\u00a0at any point in the array, increment the count of subarrays by 1.<\/li><li>If this value of <strong>sum<\/strong> has exceeded <strong>k<\/strong> by a value of <strong>sum &#8211; k<\/strong>, we can find the number of subarrays, found so far with sum = <strong>sum &#8211; k, <\/strong>from our hashmap<strong>.<\/strong> Observe that if these subarrays are deleted from our current array, we will again obtain a sum of <strong>k<\/strong>. So, we add to our answer, the <strong>number of subarrays with sum = sum &#8211; k found so far<\/strong> from our hashmap.<\/li><li>After traversing through the entire array once and applying the above steps, return the calculated result.<\/li><\/ul>\n\n\n\n<figure class=\"wp-block-image size-large\"><img  loading=\"lazy\"  width=\"1024\"  height=\"327\"  src=\"data:image\/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAAl21bKAAAAA1BMVEUAAP+KeNJXAAAAAXRSTlMAQObYZgAAAAlwSFlzAAAOxAAADsQBlSsOGwAAAApJREFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=\"  alt=\"\"  class=\"wp-image-3775 pk-lazyload\"  data-pk-sizes=\"auto\"  data-ls-sizes=\"(max-width: 1024px) 100vw, 1024px\"  data-pk-src=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Image-1-12-1024x327.png\"  data-pk-srcset=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Image-1-12-1024x327.png 1024w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Image-1-12-300x96.png 300w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Image-1-12-768x246.png 768w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Image-1-12-380x122.png 380w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Image-1-12-550x176.png 550w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Image-1-12-800x256.png 800w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Image-1-12-1160x371.png 1160w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Image-1-12.png 1354w\" ><\/figure>\n\n\n\n<h3 id=\"c-implementation\">C++ Implementation<\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"cpp\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">int countSubarraysWithSumK(vector &lt; int > &amp; a, int K) {\n  int n = a.size();\n  unordered_map &lt; int, int > hash;\n  int count = 0, sum = 0;\n  for (int i = 0; i &lt; n; i++) {\n    sum += a[i];\n    if (sum == K) {\n      count++;\n    }\n    if (hash.find(sum - K) != hash.end()) {\n      count += hash[sum - K];\n    }\n    hash[sum]++;\n  }\n  return count;\n}<\/pre>\n\n\n\n<h3 id=\"java-implementation\">Java Implementation<\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"java\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">public static int countSubarraysWithSumK(int[] a, int K) {\n  int n = a.length;\n  HashMap &lt; Integer, Integer > hash = new HashMap &lt; > ();\n  int count = 0, sum = 0;\n  for (int i = 0; i &lt; n; i++) {\n    sum += a[i];\n    if (sum == K) {\n      count++;\n    }\n    if (hash.get(sum - K) != null) {\n      count += hash.get(sum - K);\n    }\n    if (hash.get(sum) != null) {\n      hash.put(sum, hash.get(sum) + 1);\n    } else {\n      hash.put(sum, 1);\n    }\n  }\n  return count;\n}<\/pre>\n\n\n\n<h3 id=\"python-implementation\">Python Implementation<\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"python\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">from collections import defaultdict\n\n\ndef countSubarrayswithSumK(a, K):\n    n = len(a)\n    hash = defaultdict(lambda: 0)\n    count = 0\n    sum = 0\n    for i in range(n):\n        sum += a[i]\n        if sum == K:\n            count += 1\n        if (sum - K) in hash:\n            count += hash[sum - K]\n        hash[sum] += 1\n    return count<\/pre>\n\n\n\n<p><strong>Complexity Analysis<\/strong><\/p>\n\n\n\n<ul><li>Time Complexity: O(n)<\/li><li>Space Complexity: O(1)<\/li><\/ul>\n\n\n\n<p id=\"-practice-problem-\"><strong>Practice Problem<\/strong><\/p>\n\n\n\n<p><a rel=\"noreferrer noopener\" href=\"https:\/\/www.interviewbit.com\/old\/problems\/subarray-with-given-xor\/\" target=\"_blank\">Subarray With Given XOR<\/a><\/p>\n\n\n\n<h2 id=\"faqs\">FAQs<\/h2>\n\n\n\n<p><strong>Q. What is the time complexity of lookup in a hashmap?<\/strong><br>A. The time complexity of lookup in a hashmap is <strong>O(1)<\/strong> amortized.<\/p>\n\n\n\n<p><strong>Q. Why is the number of subarrays of an array given by (n * (n + 1)) \/ 2?<\/strong><br>A. The number of subarrays of an array can be calculated as there are,<\/p>\n\n\n\n<ul><li>1 subarray of length n<\/li><li>2 subarrays of length n &#8211; 1<\/li><li>\u2026\u2026<\/li><li>n subarrays of length 1<\/li><\/ul>\n\n\n\n<p>So, the total number of subarrays count out to a total of <strong>1 + 2 + 3 + &#8230; n = (n * (n + 1)) \/ 2.<\/strong><\/p>\n","protected":false},"excerpt":{"rendered":"Problem Statement Given an array a[], find the number of subarrays in it, which have a sum of&hellip;\n","protected":false},"author":5,"featured_media":3777,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"_daextam_enable_autolinks":"","csco_singular_sidebar":"","csco_page_header_type":"","csco_appearance_grid":"","csco_page_load_nextpost":"","csco_post_video_location":[],"csco_post_video_location_hash":"","csco_post_video_url":"","csco_post_video_bg_start_time":0,"csco_post_video_bg_end_time":0},"categories":[145],"tags":[565],"amp_enabled":true,"_links":{"self":[{"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts\/3698"}],"collection":[{"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/users\/5"}],"replies":[{"embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/comments?post=3698"}],"version-history":[{"count":3,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts\/3698\/revisions"}],"predecessor-version":[{"id":3776,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts\/3698\/revisions\/3776"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/media\/3777"}],"wp:attachment":[{"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/media?parent=3698"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/categories?post=3698"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/tags?post=3698"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}