Shohanur Rahman's blog

Find subarrays with given sum in an array

Shohanur Rahman's photo
Shohanur Rahman
·

4 min read

Naive Method:
The basic brute force approach to this problem would be generating all the subarrays of the given array, then looping through the generated subarray and calculating the sum and if this sum is equal to the given sum then printing this subarray as it is part of our solution.

public class Main {

    public static void main(String[] args) {
        int[] arr = {1, 4, 20, 3, 10, 5};
        int targetSum = 33;
        findSubArrays(arr, target);

    }

    public static void findSubArrays(int[] arr, int target) {
        for (int start = 0; start < arr.length; start++) {
            // initialize the sum of the current subarray to 0.
            int currSum = 0;
            for (int end = start; end < arr.length; end++) {
                // add every element of the current subarray
                // to the current running sum.
                currSum += arr[end];

               // print the starting and ending indices once we get
               // subarray with given sum
                if (currSum == target) {
                     System.out.println("starting index : " +
                                 start + ", " + "Ending index : " + end);

                }
            }
        }
    }

}

Efficient Approach:

We can maintain two pointers, start and end pointers which represents a subarray and also we have to take a variable that stores the current sum of the subarray starting from the start pointer and ending at the end pointer

package com.shohan;

import java.util.Arrays;

public class Main {
    public static void main(String[] args) {
        int[] arr = {1, 4, 20, 3, 10, 5};
        int targetSum = 33;
        findSubArrays(arr, targetSum);
    }

    public static void findSubArrays(int[] arr, int targetSum) {
        // Edge case: empty array
        if (arr.length == 0) {
            return;
        }

        // Initialize variables to keep track of the current sum and window    boundaries
        int currentSum = 0;
        int start = 0;
        int end = 0;

        // Keep expanding the window until the end of the array is reached
        while (end < arr.length) {
            // If the sum is less than the target sum, add the next element to the window
            if (currentSum < targetSum) {
                currentSum += arr[end];
                end++;
            }
            // If the sum is equal to the target sum, print the subarray
            else if (currentSum == targetSum) {
                printSubArray(arr, start, end);
                // Shrink the window by removing the first element
                currentSum -= arr[start];
                start++;
            }
            // If the sum is greater than the target sum, shrink the window             by removing the first element
            else {
                currentSum -= arr[start];
                start++;
            }
        }
    }

    // Helper method to print a subArray
    public static void printSubArray(int[] arr, int start, int end) {
        System.out.println(Arrays.toString(Arrays.copyOfRange(arr, start, end)));
    }
}

An efficient approach to finding subarrays with a given sum in an array is to use a HashMap to store the cumulative sum of the elements and their corresponding indices. Here's how it works:

  1. Initialize a variable sum_so_far to 0 and a HashMap map to store the cumulative sum of the elements and their corresponding indices.

  2. Iterate through the array, for each element, add it to the sum_so_far and check if sum_so_far - given_sum already exists in the HashMap.

  3. If it exists, it means that there is a subarray with the given sum between the index in the HashMap and the current index.

  4. If it doesn't exist, add the sum_so_far to the HashMap with the current index.

  5. Repeat steps 2-4 until the end of the array is reached

int[] arr = {1, 4, 20, 3, 10, 5};
int sum = 33;
int n = arr.length;
int sum_so_far = 0;
HashMap<Integer, Integer> map = new HashMap<>();
map.put(0, -1);

for (int i = 0; i < n; i++) {
    sum_so_far += arr[i];
    if (map.containsKey(sum_so_far - sum)) {
        int start = map.get(sum_so_far - sum) + 1;
        int end = i;
        System.out.println("Subarray found from index " + start + " to " + end);
    }
    if (!map.containsKey(sum_so_far)) {
        map.put(sum_so_far, i);
    }
}

In this approach, we have one loop which runs n times. The time complexity is O(n) and space complexity is O(n) in the worst case, where all elements in the array are distinct. This approach is more efficient than the previous approaches because it only needs to iterate through the array once and it uses a HashMap to store the cumulative sum of the elements and their corresponding indices, so it doesn't need to generate all possible subarrays.

Javainterview