HelloKoding

Practical coding guides

Subarray Sum Equals K

In this article, you will learn to resolve the Subarray Sum Equals K problems by using Brute force, Sliding window, and Hash table algorithms

Problem 1

  • Given an unsorted array of non-negative integers a[n] and an integer k
  • Find a continuous subarray whose sum equals to k

Example 1

  • Input: a = [4, 0, 11, 6, 1, 7] and k = 8
  • Output: [1, 7]

Approach 1.1: Brute Force

  • Consider the sum of every continuous subarray
  • Return the first subarray when its sum equals to k

SubarrayGivenSumBruteforce.java

package com.hellokoding.algorithm;

import java.util.Arrays;

public class SubarrayGivenSumBruteforce {
    public static int[] findSubarray(int[] a, int k) {
        for(int i = 0; i < a.length; i++) {

            int currentSum = a[i];

            for(int j = i + 1; j <= a.length; j++) {

                if (currentSum == k) {
                    return Arrays.copyOfRange(a, i, j);
                } else if (currentSum > k || j == a.length) {
                    break;
                }

                currentSum += a[j];
            }
        }

        return null;
    }

    public static void main (String[] args) {
        int[] a = {4, 0, 11, 6, 1, 7};
        int k = 8;
        System.out.println(Arrays.toString(findSubarray(a, k)));
    }
}
  • Time complexity: O(n2) as with each element in the given array, you iterate over the remaining elements to calculate the sum of possible subarrays
  • Space complexity: O(1)

Approach 1.2: Sliding Window

  • Find the sliding window sum, say ws, in the index range [i, j] of the given array a[n], that equals k by increasing j continuously from i to n-1
  • Return the result as ws as soon as it equals k, otherwise, reduce ws and increase i

SubarrayGivenSumWindowSliding.java

package com.hellokoding.algorithm;

import java.util.Arrays;

public class SubarrayGivenSumWindowSliding {
    public static int[] findSubarray(int[] a, int k) {
        int windowSum = 0, i = 0, j = 0;

        while (i < a.length) {
            while (j < a.length && windowSum < k) {
                windowSum += a[j++];
            }

            if (windowSum == k) {
                return Arrays.copyOfRange(a, i, j);
            }

            windowSum -= a[i++];
        }

        return null;
    }

    public static void main (String[] args) {
        int[] a = {4, 0, 11, 6, 1, 7};
        int k = 8;
        System.out.println(Arrays.toString(findSubarray(a, k)));
    }
}
  • Time complexity: O(n)
  • Space complexity: O(1)

Problem 2

  • Given an unsorted array of integers a[n] and an integer k
  • Find the total number of continuous subarrays whose sum equals to k

Example 2

  • Input: a = [-4, 12, -11, 6, 1, 7], k = 8
  • Output: 3
  • Explanation: [-4, 12], [12, -11, 6, 1], [1, 7] are 3 subarrays have sum equals to 8

Approach 2: Hash table

  • Say ci, cj is the cumulative sum at index i and j in the given array a[n]

Elements from i to j will form a subarray that satify the constraint if cj - k = ci ∀ 0 <= i < j < n

  • Use a hash table h with key = ci ∀ 0 <= i < n, value = count(ci) in h
  • The final result is count(h.getValueByKey(ci - k))

SubarrayGivenSumHashtable.java

package com.hellokoding.algorithm;

import java.util.HashMap;
import java.util.Map;

public class SubarrayGivenSumHashtable {
    public static int countSubArrays(int[] a, int k) {
        int count = 0;
        int cumulativeSum = 0;
        Map<Integer, Integer> map = new HashMap<>();
        map.put(0, 1);

        for (int value : a) {
            cumulativeSum += value;
            if (map.containsKey(cumulativeSum - k)) {
                count += map.get(cumulativeSum - k);
            }

            map.put(cumulativeSum, map.getOrDefault(cumulativeSum, 0) + 1);
        }

        return count;
    }

    public static void main (String[] args) {
        int[] a = {-4, 12, -11, 6, 1, 7};
        int k = 8;
        System.out.println(countSubArrays(a, k));
    }
}
  • Time complexity: O(n) as the given array is traversed through only once
  • Space complexity: O(n) as the hash table can hold up to n elements
Follow HelloKoding