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 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:

• Maximum Difference Between Two Elements Such that Larger Element Appears After the Smaller Number
• Find Maximum Subarray Sum
• Maximum Sum Circular Subarray
• Longest? ?Bitonic? ?Subarray? ?Problem?
• Replace Every Array Element With The Product of Every Other Element
• Dutch National Flag Problem
• Find Maximum Length Subarray Having an Equal Number of 0’s and 1’s
• Merge Two Sorted Arrays in-place
• Print all subarrays with 0 sum
• Longest subarray with sum as K