Subarray with Sum k

By | October 29, 2021
Subarray with Sum k

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 sumk, 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

Vamware
Found b/w 1 and 2

People are also reading:

Author: Vinay Singh

I am a Full Stack Developer with a Bachelor's Degree in Computer Science, who also loves to write technical articles that can help fellow developers.

Leave a Reply

Your email address will not be published.