<?xml version="1.0" encoding="UTF-8"?><rss xmlns:dc="http://purl.org/dc/elements/1.1/" xmlns:content="http://purl.org/rss/1.0/modules/content/" xmlns:atom="http://www.w3.org/2005/Atom" version="2.0" xmlns:cc="http://cyber.law.harvard.edu/rss/creativeCommonsRssModule.html">
    <channel>
        <title><![CDATA[Stories by Koustavjr on Medium]]></title>
        <description><![CDATA[Stories by Koustavjr on Medium]]></description>
        <link>https://medium.com/@koustavjr11?source=rss-811469f895f0------2</link>
        <image>
            <url>https://cdn-images-1.medium.com/fit/c/150/150/0*VR5fhr6ezX8GMjyo</url>
            <title>Stories by Koustavjr on Medium</title>
            <link>https://medium.com/@koustavjr11?source=rss-811469f895f0------2</link>
        </image>
        <generator>Medium</generator>
        <lastBuildDate>Fri, 20 Nov 2026 10:14:00 GMT</lastBuildDate>
        <atom:link href="https://medium.com/@koustavjr11/feed" rel="self" type="application/rss+xml"/>
        <webMaster><![CDATA[yourfriends@medium.com]]></webMaster>
        <atom:link href="http://medium.superfeedr.com/" rel="hub"/>
        <item>
            <title><![CDATA[Subarray Sum Equals K]]></title>
            <link>https://medium.com/@koustavjr11/subarray-sum-equals-k-e51e8c2f388d?source=rss-811469f895f0------2</link>
            <guid isPermaLink="false">https://medium.com/p/e51e8c2f388d</guid>
            <category><![CDATA[data-structure-algorithm]]></category>
            <category><![CDATA[leetcode]]></category>
            <dc:creator><![CDATA[Koustavjr]]></dc:creator>
            <pubDate>Sat, 23 Nov 2024 15:37:22 GMT</pubDate>
            <atom:updated>2024-11-23T15:37:22.227Z</atom:updated>
            <content:encoded><![CDATA[<p>Given an array of integers nums and an integer k, return <em>the total number of subarrays whose sum equals to</em> k.</p><p>Note: A subarray is a contiguous <strong>non-empty</strong> sequence of elements within an array.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*Uf1YxM3GAwYaaBk2gf3Lyw.png" /></figure><p><strong>Example 1:</strong></p><pre>Input: nums = [1,1,1], k = 2<br>Output: 2</pre><p><strong>Example 2:</strong></p><pre>Input: nums = [1,2,3], k = 3<br>Output: 2</pre><p><strong>Constraints</strong></p><ol><li>Array length should be between 1 to 10⁴.</li><li>The elements in the array should be between -1000 to 1000.</li><li>The value of ‘K’ should lie in the range of -10⁷ to 10⁷.</li></ol><p>There are a couple of ways that we can solve this problem. One is the extremely naive and brute force solution and the other is the prefix sum concept. Let us examine both approaches one by one.</p><h3>Brute Force Approach</h3><p>First, we will try to generate every possible sub-array and add the elements of the sub-array and whenever the sum becomes equal to ‘K’ we increase the counter.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/624/1*DNIdZq6u7aPk3F3px8BJlw.png" /></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/601/1*krZPT8RKaOKBQBzbGrMaqQ.png" /></figure><p>Algorithm:</p><ol><li>First, we will run an outside loop (say i) from the 0th index to the end of the array which will mark the starting element of each sub-array.</li><li>Next, we will keep a sum = 0 for calculating the sum of elements in each sub-array and a counter to count the number of the sub-array sum that becomes equal to ‘k’.</li><li>Inside the loop, run another loop (say j) that will run from ‘i’ to the end of the array length and will mark the ending of sub-array.</li><li>Inside the ‘j’ loop we will add the current element to the sum of the previous sub-array i.e. sum=sum+arr[j].</li><li>Lastly, after each addition, we will check whether the sum is equal to ‘k’ or not. If it is true, then increase the counter.</li></ol><h3>Code</h3><pre>class Solution {<br>    public int subarraySum(int[] nums, int k) {<br>    int n = nums.length;<br>        int count = 0; <br>        for (int i = 0 ; i &lt; n; i++) { <br>            int sum = 0;<br>            for (int j = i; j &lt; n; j++) { <br>                sum += nums[j];<br>                if (sum == k)<br>                    count++;<br>            }<br>        }<br>        return count;<br>    }<br>}</pre><h3>Dry Run</h3><p>arr=[1,2,3], k= 3 , count=0</p><p>For i=0, j =0:</p><p>sum=1 is not equal to k, count stays 0.</p><p>for i=0, j =1:</p><p>sum=1+2=3 which is equal to k, hence count increases to 1.</p><p>for i=0, j=2:</p><p>sum =1+2+3=6 which is not equal to k, so the count stays 1.</p><p>For i=1, j=1:</p><p>sum=2 which is not equal to k, so the count stays 1.</p><p>for i=1, j=2:</p><p>sum= 2+3=5 which is not equal to k, so the count stays 1.</p><p>For i= 2, j=2:</p><p>sum= 3 which is equal to k, hence the count increases to 2 and we get our answer.</p><h3>Time Complexity:</h3><p>O(n²), where n= size of the array.</p><p>Reason: We are using two nested loops here. As each of them is running for exactly N times, the time complexity will be approximately O(N2).</p><h3>Space Complexity:</h3><p>O(1) as we are not using any extra space or data structure.</p><h3>Optimal Approach</h3><p>Before getting into the optimal approach let us first understand the concept of prefix sum. If we have an array with the sum of its elements up to index ‘i’ is x, and if we can find that there exists an index ‘j’ such that sum of elements till index ‘j’ is “x-k” then we can say there exists a sub-array with sum equals to k.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/469/1*enxP_WoJsPNTeSJSMfFLcg.png" /></figure><h3>Dry Run</h3><p>Let us understand it by a dry run on the array [1,2,3,-3,1,1,1] with k=3. We will use a hashmap data structure to store the prefix sum and how many times it has occurred. Also, we will have two variable to store prefix sum and count.</p><p>arr=[1,2,3,-3,1,1,1], k=3</p><p>Initialize the hashmap with a key-value pair as (0,1)</p><p>map={(0,1)}</p><p>Initialize two variables prefix-sum=0, count=0.</p><p>Now, for arr[0]=1,</p><p>prefix-sum=1, count=0, map={(0,1), (1,1)}</p><p>Checking in the map if (prefix-sum — k) i.e. 1–3= — 2 is present in the map or not. And since it is not present on the map, so the count remains 0.</p><p>for arr[1]=2,</p><p>prefix-sum=1+2=3, count=0, map={(0,1),(1,1),(3,1)}</p><p>Checking in the map if (prefix-sum — k) i.e. 3–3=0 is present in the map or not. And since it is present on the map, so add to the count the number of times 0 has occurred in the map which is once,i.e. count=0+1</p><p>for arr[2]=3,</p><p>prefix-sum=1+2+3=6, count=1, map={(0,1),(1,1),(3,1),(6,1)}</p><p>Checking in the map if (prefix-sum — k) i.e. 6–3=3 is present in the map or not. And since it is present on the map, so add to the count the number of times 3 has occurred in the map which is once,i.e. count=1+1</p><p>for arr[3]= — 3,</p><p>prefix-sum=1+2+3–3=3, count=2, map={(0,1),(1,1),(3,2),(6,1)}</p><p>Checking in the map if (prefix-sum — k) i.e. 3–3=0 is present in the map or not. And since it is present on the map, so add to the count the number of times 0 has occurred in the map which is once,i.e. count=2+1</p><p>for arr[4]=1,</p><p>prefix-sum=1+2+3–3+1=4, count=3, map={(0,1),(1,1),(3,2),(6,1),(4,1)}</p><p>Checking in the map if (prefix-sum — k) i.e. 4–3=1 is present in the map or not. And since it is present on the map, so add to the count the number of times 1 has occurred in the map which is once,i.e. count=3+1</p><p>for arr[5]=1,</p><p>prefix-sum=1+2+3–3+1+1=5, count=4, map={(0,1),(1,1),(3,2),(6,1),(4,1),(5,1)}</p><p>Checking in the map if (prefix-sum — k) i.e. 5–3=2 is present in the map or not. And since it is not present on the map, so count remains 4.</p><p>for arr[6]=1,</p><p>prefix-sum=1+2+3–3+1+1+1=6, count=4, map={(0,1),(1,1),(3,2),(6,1),(4,1),(5,1),(6,1)}</p><p>Checking in the map if (prefix-sum — k) i.e. 6–3=3 is present in the map or not. And since it is present on the map, so add to the count the number of times 3 has occurred in the map which is twice,i.e. count=4+2.</p><p>The final answer is count=6.</p><p><em>Note: We took (0,1) as starting in the map because we can see that at some point prefix-sum becomes 3 which is equal to the value of k. so prefix-sum minus k becomes equal to 0 and to add it to our count we took 0 in our hashmap.</em></p><h3>Algorithm</h3><ol><li>Declare a hashmap data structure to store prefix-sum and their occurrence.</li><li>Initialize to variables to store prefix sums and number of sub-arrays whole sum is equal to k.</li><li>Store 0 and 1 as key-value pairs in the hashmap.</li><li>Run a loop (say i) from 0 to end of the array</li><li>For each array element perform the following operation:</li></ol><p>5.1 Add the current array element to prefix sum variable</p><p>5.2 Then we will check prefix-sum — k is present in our hashmap or not.</p><p>5.3 If it is present we will add the occurrence of (prefix sum — k) to our counter variable.</p><p>5.4 We will add the prefix-sum to our map and increase its occurrence value by 1.</p><h3>Code</h3><pre>class Solution {<br>    public int subarraySum(int[] nums, int k) {<br>     HashMap&lt;Integer,Integer&gt;map=new HashMap&lt;&gt;();<br>     int ans=0,sum=0;<br>     map.put(0,1);<br>     for(int i=0;i&lt;nums.length;i++)<br>     {<br>        sum+=nums[i];<br>        if(map.containsKey(sum-k))<br>        {<br>            ans+=map.get(sum-k);<br><br>        }<br>        map.put(sum,map.getOrDefault(sum,0)+1);<br>     }   <br>     return ans;<br>    }<br>}</pre><h3>Time Complexity</h3><p>It can be O(N) or O(NLogN) depending on the type of hashmap data structure we are using.</p><h3>Space Complexity</h3><p>It will be O(N) for using the map data structure.</p><p><strong><em>Key Concept Learned: Prefix-Sum</em></strong></p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=e51e8c2f388d" width="1" height="1" alt="">]]></content:encoded>
        </item>
    </channel>
</rss>