Subarray Sum Equals K

Introduction

Have you ever wondered how computers solve tricky puzzles with numbers? One such puzzle is called "Subarray Sum Equals K," and it's both interesting and challenging. Don't worry if it sounds complicated at first – we're here to break it down in simple terms.

Imagine you have a list of numbers, and you want to find out how many times a specific total, let's call it K, can be made by adding up some consecutive numbers in the list. That's the essence of the Subarray Sum Equals K problem.

What is Subarray Sum?

The subarray sum is the sum of elements in a subarray. A subarray is a contiguous part of an array (a sequence of elements in an array next to each other). For example, the subarrays of the array [1, 2, 3, 4] are [1, 2, 3, 4], [1, 2], [2, 3], [3, 4], [1], [2], [3], and [4]. The subarray sum for subarray [1, 2, 3, 4] is 10. Subarrays can be used to solve multiple problems, including problems that do not involve arrays. Thus, they are powerful tools for solving different problems.

Let's discuss one such problem today. We want to find the number of subarrays whose sum equals k.

Problem Statement

Given an array and an integer, K. Count the number of subarrays with sum equal to k.

Example

Let's take a simple example to understand the problem better.

Input

arr = {1, 2, 3, 1, 5}, k = 6

Output

Explanation

There are three subarrays with sum equal to 6

Subarray from index 0 to index 2 {1, 2, 3}

Subarray from index 1 to index 3 {2, 3, 1}

Subarray from index 3 to index 4 {1, 5}

Approach of Subarray Sum

Brute Force Approach

This is the simple approach where we use nested loops to perform our task.

Algorithm

Here is the algorithm to implement the naive approach:

Initialize a counter variable to 0.
Generate all subarrays of the given array using two nested loops.
Calculate the sum of each subarray.
If the sum of a subarray is equal to k, increment the counter by 1.
Return the counter, which represents the number of subarrays with a sum equal to k.

Note: The time complexity of this approach will be O(n^3), where n is the size of the input array. Therefore, it is not an efficient solution for large inputs.

Dry Run

We have , arr = {1, 2, 3, 1, 5} and k = 6
Now we call getCountSubarraysWithSumK(arr, k) with the above values.
We have count = 0;
Now while generating the subarray we start with i = 0;
1. For j = 0, the sum is the sum of the subarray formed from index 0 to 0, which is 1.
2. Similarly for j = 1 , sum = 1 + 2 = 3
3. Similarly for j = 2 , sum = 1 + 2 + 3 = 6. The sum is equal to k, so increment the count by 1, count = 1.
4. Similarly for j = 3 , sum = 1 + 2 + 3 + 1 = 7
5. Similarly for j = 4 , sum = 1 + 2 + 3 + 1 + 5 = 12
Likewise, we generate for i=1 to n and repeat the same procedure.

Implementation in Java

Java

Java

import java.util.*;
public class Main {
	// function to count subarrays with sum K
	public static int getCountSubarraysWithSumK(List<Integer> arr, int K) {
		int n = arr.size();
		int count = 0;
		// iterate through all possible subarrays
		for (int i = 0; i < n; i++) {
			for (int j = i; j < n; j++) {
				// calculate sum of subarray
				int sum = 0;
				for (int k = i; k <= j; k++) {
					sum += arr.get(k);
				}
				// increment count if sum is equal to K
				count += (sum == K ? 1 : 0);
			}
		}
		return count;
	}

	public static void main(String[] args) {
		int k = 6;
		List<Integer> arr = new ArrayList<Integer>(Arrays.asList(1, 2, 3, 1, 5));
		// call function and print result
		int ans = getCountSubarraysWithSumK(arr, k);
		System.out.println("Count of subarrays with sum k is " + ans);
	}
}

You can also try this code with Online Java Compiler

Run Code

Output

Count of subarrays with sum k is 3

Implementation in C++

C++

#include <bits/stdc++.h>
using namespace std;
// function to count subarrays with sum K
int getCountOfSubarryWithSumK(vector<int> &arr, int K) {
	int n = arr.size();
	int count = 0;
	// iterate through all possible subarrays
	for (int i = 0; i < n; i++) {
		for (int j = i; j < n; j++) {
			// calculate sum of subarray
			int sum = 0;
			for (int k = i; k <= j; k++) {
				sum += arr[k];
			}
			// increment count if sum is equal to K
			count += (sum == K);
		}
	}
	return count;
}
int main() {
	int k = 6;
	vector<int> arr{1, 2, 3, 1, 5};
	// call function and print result
	int ans = getCountOfSubarryWithSumK(arr, k);
	cout << "Count of subarray with sum k is " << ans << endl;
	return 0;
}

You can also try this code with Online C++ Compiler

Run Code

Output

Count of subarrays with sum k is 3

Time Complexity

This approach has a Time Complexity of O(N ^ 3). The code uses three nested loops that can go upto N, to generate subarrays and calculates the sum. You can optimize it to O(N ^ 2) by calculating the sum while generating the Subarray.

Space Complexity

The code has Space Complexity of O(1) as only a single counter variable is involved.

Optimal Approach - Hashing

The optimal approach involves usage of hashmaps. We put the prefix sums in the hashmap.

Algorithm

Here is simple algorithm to implement the optimal approach:

Initialize a hashmap to store the frequency of the sum values obtained so far, and a variable count to keep track of the number of subarrays with a sum equal to k.
Initialize a variable sum to 0.
Traverse through the array and for each element:
1. Update the value of sum by adding the current element.
  1. If sum equals k, increment count by 1.
  2. If the value sum - k is present in the hashmap, increment count by the frequency of sum - k in the hashmap.
  3. Increment the frequency of the current value of sum in the hashmap.
Return count, which represents the number of subarrays with a sum equal to k.

Dry Run

1. Initially, the function initialises an empty unordered_map and two integers, count and sum, to 0. It then iterates through the input array, arr, and at each iteration, it adds the current element to the sum variable.

2. For the first iteration, the sum is 1, which is not equal to K, so nothing happens.

3. For the second iteration, the sum is 3, which is not equal to K, so nothing happens.

4. For the third iteration, the sum is 6, which is equal to K, so the count variable is incremented by 1.

5. For the fourth iteration, the sum is 7, which is not equal to K, so nothing happens.

6. For the fifth iteration, the sum is 12, which is greater than K. The function checks if (sum - K) exists in the unordered_map. In this case, (sum - K) is equal to 6, which is in the map with a value of 1. So, the count variable is incremented by 1, making it equal to 2.

7. Finally, the function adds the current sum to the unordered_map with a value of 1, indicating that it has seen this sum once.

8. The function then returns the count variable, which is equal to 2 in this case, indicating that there are two subarrays with a sum equal to K.

9. Therefore, the output of this code with the given input values would be: "Count of subarray with sum k is 2".

Implementation in Java

Java

Java

import java.util.*;
public class Main {
	// function to count subarrays with sum K
	public static int getCountOfSubarrayWithSumK(List < Integer > arr, int K) {
		int n = arr.size();
		Map < Integer, Integer > map = new HashMap < > ();
		int count = 0, sum = 0;
		for (int i = 0; i < n; i++) {
			sum += arr.get(i);
			if (sum == K) {
				count++;
			}
			if (map.containsKey(sum - K)) {
				count += map.get(sum - K);
			}
			map.put(sum, map.getOrDefault(sum, 0) + 1);
		}
	return count;
}
	public static void main(String[] args) {
		int k = 6;
		List < Integer > arr = Arrays.asList(1, 2, 3, 1, 5);
		// call function and print result
		int ans = getCountOfSubarrayWithSumK(arr, k);
		System.out.println("Count of subarray with sum k is " + ans);
	}
}

You can also try this code with Online Java Compiler

Run Code

Output

Count of subarrays with sum k is 3

Implementation in C++

C++

#include <bits/stdc++.h>
using namespace std;
// function to count subarrays with sum K
int getCountOfSubarrayWithSumK(vector<int> &arr, int K) {
	int n = arr.size();
	unordered_map<int, int> mpp;
	int count = 0, sum = 0;
	for (int i = 0; i < n; i++) {
		sum += arr[i];
		if (sum == K) {
			count++;
		}
		if (mpp.find(sum - K) != mpp.end()) {
			count += mpp[sum - K];
		}
		mpp[sum]++;
	}
	return count;
}
int main() {
	int k = 6;
	vector<int> arr{1, 2, 3, 1, 5};
	// call function and print result
	int ans = getCountOfSubarrayWithSumK(arr, k);
	cout << "Count of subarray with sum k is " << ans << endl;
	return 0;
}

You can also try this code with Online C++ Compiler

Run Code

Output

Count of subarrays with sum k is 3

Time Complexity

The above code has a time complexity of O(N), where ‘N’ is the number of elements in the array. Since we are iterating over all the elements of the array to calculate the prefix sums and check their sums, the complexity here grows by O(N).

Space Complexity

The above code has a space complexity of O(N), where ‘N’ is the number of elements in the array. Here, we require an O(N) amount of space for storing the respective sums in the map. Therefore, the space complexity is O(N).

Prefix Sums

Prefix sums, also known as cumulative sums, are a computational technique used in array manipulation. The idea is to compute the cumulative sum of elements up to a given index in an array, allowing for efficient retrieval of the sum of any subarray. For example

Java
C++

Java

import java.util.Arrays;

class PrefixSums {
    public static void main(String[] args) {
        int[] array = {1, 2, 3, 4, 5};

        // Calculate prefix sums
        int[] prefixSums = new int[array.length];
        prefixSums[0] = array[0];
        for (int i = 1; i < array.length; i++) {
            prefixSums[i] = prefixSums[i - 1] + array[i];
        }

        // Print the array and its prefix sums
        System.out.println("Original Array: " + Arrays.toString(array));
        System.out.println("Prefix Sums: " + Arrays.toString(prefixSums));
    }
}

You can also try this code with Online Java Compiler

Run Code

C++

#include <iostream>
#include <vector>

int main() {
    std::vector<int> array = {1, 2, 3, 4, 5};

    // Calculate prefix sums
    std::vector<int> prefixSums(array.size());
    prefixSums[0] = array[0];
    for (int i = 1; i < array.size(); i++) {
        prefixSums[i] = prefixSums[i - 1] + array[i];
    }

    // Print the array and its prefix sums
    std::cout << "Original Array: ";
    for (int num : array) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    std::cout << "Prefix Sums: ";
    for (int sum : prefixSums) {
        std::cout << sum << " ";
    }
    std::cout << std::endl;

    return 0;
}

You can also try this code with Online C++ Compiler

Run Code

Output:

Explanation: In this example, the prefix sums are calculated by iterating through the array and updating the prefix sum at each index. The resulting prefix sums array allows for quick retrieval of the sum of any subarray in constant time, providing an efficient solution for various computational tasks.

Check out this : Longest common subsequence

Frequently Asked Questions

Q1. What is the maximum length subarray with a sum greater than k?

The problem involves finding the longest contiguous part of an array whose elements sum to a value greater than k.

Q2. How many subarrays are possible?

For an array of n elements, n(n+1)22n(n+1) subarrays are possible, including all contiguous combinations of the array elements.

Q3. What is the maximum subarray sum problem to find the subarray?

The maximum subarray sum problem seeks the contiguous subarray within an array of numbers that has the largest possible sum.

Q4. What is the time complexity of the maximum sum Subarray?

The time complexity of finding the maximum sum subarray is O(n) using Kadane’s Algorithm, which is optimal for this problem.

Conclusion

Here we learned one of the most important and frequently asked questions in Amazon, Microsoft, and other product-based companies, i.e. Count Number of Subarrays with Sum K. We discussed various approaches ranging from brute force to optimal along with the C++ and JAVA code for your better understanding.

We hope this blog has helped you enhance your knowledge of the count of subarrays having sum equal to k. If you want to learn more, then check out our articles.

And many more on our platform Coding Ninjas Studio.

Refer to our Guided Path to upskill yourself in DSA, Competitive Programming, JavaScript, System Design, and many more! If you want to test your competency in coding, you may check out the mock test series and participate in the contests hosted on Coding Ninjas Studio!

But suppose you have just started your learning process and are looking for questions from tech giants like Amazon, Microsoft, Uber, etc. In that case, you must look at the problems, interview experiences, and interview bundles for placement preparations.

However, you may consider our paid courses to give your career an edge over others!

Happy Learning!

Introduction

What is Subarray Sum?

Problem Statement

Example

Approach of Subarray Sum

Brute Force Approach

Algorithm

Dry Run

Implementation in Java

Java

Implementation in C++

C++

Time Complexity

Space Complexity

Optimal Approach - Hashing

Algorithm

Dry Run

Implementation in Java

Java

Implementation in C++

C++

Time Complexity

Space Complexity

Prefix Sums

Java

C++

Frequently Asked Questions

Q1. What is the maximum length subarray with a sum greater than k?

Q2. How many subarrays are possible?

Q3. What is the maximum subarray sum problem to find the subarray?

Q4. What is the time complexity of the maximum sum Subarray?

Conclusion