5 Ways To Solve Subarray Sum Equals K

Quick Links :

The problem of finding subarrays with a sum equal to a given value K is a classic problem in computer science and mathematics. It has numerous applications in various fields, including data analysis, computer networks, and algorithm design. In this article, we will explore five different ways to solve this problem efficiently.

Understanding the Problem

The problem statement is straightforward: given an array of integers and a target sum K, find all subarrays whose elements sum up to K. A subarray is a contiguous segment of the original array. The problem can be solved using various techniques, ranging from simple iterative approaches to more complex algorithmic solutions.

Method 1: Brute Force Approach

The brute force approach involves iterating over all possible subarrays of the given array and checking if their sum equals the target value K. This approach has a time complexity of O(n^3), where n is the size of the array.

Here is a simple implementation of the brute force approach in Python:

def find_subarrays_brute_force(arr, K):
    n = len(arr)
    for i in range(n):
        for j in range(i, n):
            subarray_sum = sum(arr[i:j+1])
            if subarray_sum == K:
                print(arr[i:j+1])

# Example usage:
arr = [1, 2, 3, 4, 5]
K = 5
find_subarrays_brute_force(arr, K)

Method 2: Hash Table Approach

The hash table approach involves using a hash table to store the cumulative sum of the array elements. The cumulative sum is the sum of all elements up to a given index. We can then iterate over the array and check if the difference between the current cumulative sum and the target sum K is present in the hash table.

Here is a Python implementation of the hash table approach:

def find_subarrays_hash_table(arr, K):
    n = len(arr)
    cumulative_sum = 0
    hash_table = {}
    for i in range(n):
        cumulative_sum += arr[i]
        if cumulative_sum == K:
            print(arr[:i+1])
        if cumulative_sum - K in hash_table:
            for j in range(hash_table[cumulative_sum - K], i+1):
                print(arr[j:i+1])
        if cumulative_sum not in hash_table:
            hash_table[cumulative_sum] = i

# Example usage:
arr = [1, 2, 3, 4, 5]
K = 5
find_subarrays_hash_table(arr, K)

Method 3: Prefix Sum Approach

The prefix sum approach involves calculating the prefix sum of the array, which is the sum of all elements up to a given index. We can then iterate over the array and check if the difference between the current prefix sum and the target sum K is present in the prefix sum array.

Here is a Python implementation of the prefix sum approach:

def find_subarrays_prefix_sum(arr, K):
    n = len(arr)
    prefix_sum = [0] * (n+1)
    for i in range(n):
        prefix_sum[i+1] = prefix_sum[i] + arr[i]
    for i in range(n):
        for j in range(i, n):
            if prefix_sum[j+1] - prefix_sum[i] == K:
                print(arr[i:j+1])

# Example usage:
arr = [1, 2, 3, 4, 5]
K = 5
find_subarrays_prefix_sum(arr, K)

Method 4: Sliding Window Approach

The sliding window approach involves maintaining a window of elements that sum up to the target value K. We can then slide the window to the right by removing the leftmost element and adding the next element to the right.

Here is a Python implementation of the sliding window approach:

def find_subarrays_sliding_window(arr, K):
    n = len(arr)
    window_sum = 0
    left = 0
    for right in range(n):
        window_sum += arr[right]
        while window_sum > K:
            window_sum -= arr[left]
            left += 1
        if window_sum == K:
            print(arr[left:right+1])

# Example usage:
arr = [1, 2, 3, 4, 5]
K = 5
find_subarrays_sliding_window(arr, K)

Method 5: Two Pointer Approach

The two pointer approach involves using two pointers, one at the beginning and one at the end of the array. We can then move the pointers towards each other while checking if the sum of the elements between the pointers is equal to the target value K.

Here is a Python implementation of the two pointer approach:

def find_subarrays_two_pointer(arr, K):
    n = len(arr)
    left = 0
    right = n-1
    while left < right:
        window_sum = sum(arr[left:right+1])
        if window_sum == K:
            print(arr[left:right+1])
            left += 1
            right -= 1
        elif window_sum < K:
            left += 1
        else:
            right -= 1

# Example usage:
arr = [1, 2, 3, 4, 5]
K = 5
find_subarrays_two_pointer(arr, K)

We hope this article has provided you with a comprehensive overview of the different approaches to solve the subarray sum equals K problem. Each approach has its own strengths and weaknesses, and the choice of approach depends on the specific requirements of the problem. By understanding the different approaches, you can develop efficient solutions to solve this problem and other related problems in the field of computer science and mathematics.