Subarray with Sum k

Posted in /  

Subarray with Sum k

Vinay Khatri
Last updated on November 14, 2022

    Problem

    Given an unsorted array arr of size N , find a contiguous subarray that adds to a given number k .

    Brute Force Approach

    An easy approach is to go through all subarrays one by one and calculate the total of each subarray. The programme that follows implements the basic solution. Run two loops: the outer loop selects a starting point i , while the inner loop attempts all subarrays beginning with i . This approach will take O(N2) time and O(1) auxiliary space.

    Efficient Approach

    The concept is to store the sum of the elements of each prefix of the array in a hashmap, where the key is the sum of each prefix and the index is the most recent index with that sum. So, to see if there is a subarray with a sum equal to k , look at each index I and add up to that index and keep it in the hashmap. Let’s say sum is sum . If a prefix in a hash map has a sum equal to sum k , the subarray with the specified sum is discovered. The steps for algorithm are:

    1. Create a hashmap to hold a key-value pair, i.e., key = prefix sum of each prefix and value = its index, and a variable to record the current sum as sum .
    2. Traverse through the array.
    3. Update the sum for each entry, i.e. sum = sum + array[i].
    4. If some prefix has a sum equal to k , display it.
    5. If the ( sum-k ) is found in hashmap, display the subarray with the provided sum.
    6. Put sum and current index in the hashmap as a key-value pair.

    C++ Programming

    #include<bits/stdc++.h>
    using namespace std;
    
    void subArrayequalsK(int arr[], int n, int k)
    {
        unordered_map<int, int> mp;
    
        // Maintains prefix sum of elements
        int sum = 0;
    
        for (int i = 0; i < n; i++)
        {
            // add current element to k
            sum = sum + arr[i];
    
            // if any prefix sum is equal to target k
            if (sum == k)
            {
                cout << "Found b/w"
                    << 0 << " and " << i << endl;
                return;
            }
    
            // If sum - k already exists in mp
            if (mp.find(sum - k) != mp.end())
            {
                cout << "Found b/w "
                    << mp[sum - k] + 1
                    << " to " << i << endl;
                return;
            }
    
            mp[sum] = i;
        }
    }
    int main(){
        int a[5] = {1, 3, -4, 2, 5};
        int n=sizeof(a)/sizeof(a[0]);
        int k =4;
        subArrayequalsK(a, n, k);
    }

    Output

    Found b/w 0 and 1

    C# Programming

    using System;
    using System.Collections.Generic;
    public class Solution
    {
    
        public static void subArrayequalsK(int[] arr, int n, int k)
        {
            int sum = 0;
            int begin = 0;
            int finish = -1;
            Dictionary<int, int> mp = new Dictionary<int, int>();
    
            for (int i = 0; i < n; i++)
            {
                sum = sum + arr[i];
                //check if some prefix sum is equal to k
                if (sum == k)
                {
                    begin = 0;
                    finish = i;
                    break;
                }
                //if mp already has the sum, we already
                // have subarray with the k
                if (mp.ContainsKey(sum - k))
                {
                    begin = mp[sum - k] + 1;
                    finish = i;
                    break;
                }
                mp[sum] = i;
    
            }
            Console.WriteLine("Found b/w " + begin + " to " + finish);
    
        }
        static void Main(string[] args){
            int[] arr = {1, 2, 3, 4};
            int k = 3;
            int n = 4;
            subArrayequalsK(arr, n, k);
        }
    }

    Output

    Found b/w 0 and 1

    Python Programming

    def subArrayequalsK(arr, n, k):
        mp = {}
        sum = 0
    
        for i in range(0,n):
        
            # add current element to sum
            sum = sum + arr[i]
    
            # if prefix sum is equal to target
            if sum == k:
            
                print("Found b/w 1 and", i+1)
                return
            
    
            # If sum - sum already exists in map
            if (sum - k) in mp:
            
                print("Found b/w", \
                    mp[sum - k] + 1, "and", i+1)
                
                return
    
            mp[sum] = i+1
    
    l = [1, 2, 3, 4]
    n= len(l)
    k = 3
    subArrayequalsK(l, n, k)

    Output

    Found b/w 1 and 2
    

    People are also reading:

    Tags:
    array subarray

    Leave a Comment on this Post

    0 Comments