Subarray with Given Sum | Sliding Window Technique

A subarray with a given sum is a common problem in computer science and programming, often encountered in the context of algorithmic interviews and competitive programming. The problem statement usually goes like this:

Problem Statement:
Given an array of integers and a target sum, find a contiguous subarray (a subarray with consecutive elements) within the array such that the sum of its elements equals the target sum. If no such subarray exists, return an indication that the target sum cannot be achieved using any subarray.

Example:
Input:
Array: [1, 4, 20, 3, 10, 5]
Target Sum: 33

Output:
Subarray: [20, 3, 10]

In this example, the subarray [20, 3, 10] has a sum of 33, which matches the target sum.

Approaches:
There are multiple approaches to solving the subarray with given sum problem, each with varying levels of efficiency. Let’s discuss a couple of common approaches:

1. Brute Force Approach:
   The simplest approach is to consider all possible subarrays and calculate their sums. For each starting index i, iterate through all ending indices j (where j >= i), and calculate the sum of the subarray arr[i:j]. If the sum matches the target sum, return the subarray. This approach has a time complexity of O(n^2), where n is the length of the input array. It’s not very efficient and might not be suitable for larger arrays.
2. Sliding Window Approach:
   This approach uses two pointers, start and end, to create a sliding window that represents the current subarray being considered. The end pointer moves forward, extending the window, while the start pointer moves forward when the sum exceeds the target. This approach works well for arrays with positive elements. Here’s a basic algorithm:

• Initialize start and end pointers to 0.
• Initialize a variable currentSum to track the sum of the current subarray.
• Iterate through the array using the end pointer:
  • Add arr[end] to currentSum.
  • If currentSum is greater than the target, subtract arr[start] from currentSum and increment start.
  • If currentSum equals the target, return the subarray from start to end.
• If the loop finishes without finding a subarray, return an indication that no subarray with the target sum exists. This approach has a time complexity of O(n) since each element is processed at most twice (when added and when removed).

Optimizations:
There are further optimizations that can be applied, depending on the specific problem constraints. For example, if the array contains negative numbers, the sliding window approach might not work as expected. In such cases, a hashmap-based approach can be used to keep track of cumulative sums and their indices to efficiently find subarrays.

Remember that when solving algorithmic problems, it’s essential to consider edge cases and optimize for both time and space complexity.

Sure, I can provide you with example code in both Java and Python for the “Subarray with Given Sum” problem using the sliding window approach. Let’s start with Java:

Java Code:

import java.util.ArrayList;
import java.util.List;

public class SubarrayWithGivenSum {
    public static List<Integer> findSubarrayWithSum(int[] arr, int targetSum) {
        List<Integer> subarray = new ArrayList<>();
        int start = 0, end = 0;
        int currentSum = 0;

        while (end < arr.length) {
            currentSum += arr[end];

            while (currentSum > targetSum) {
                currentSum -= arr[start];
                start++;
            }

            if (currentSum == targetSum) {
                for (int i = start; i <= end; i++) {
                    subarray.add(arr[i]);
                }
                return subarray;
            }

            end++;
        }

        return subarray; // Return an empty list if no subarray is found
    }

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

        List<Integer> subarray = findSubarrayWithSum(arr, targetSum);
        if (!subarray.isEmpty()) {
            System.out.println("Subarray with target sum found: " + subarray);
        } else {
            System.out.println("No subarray with target sum found.");
        }
    }
}

And now, the Python code:

Python Code:

def find_subarray_with_sum(arr, target_sum):
    subarray = []
    start, end = 0, 0
    current_sum = 0

    while end < len(arr):
        current_sum += arr[end]

        while current_sum > target_sum:
            current_sum -= arr[start]
            start += 1

        if current_sum == target_sum:
            subarray = arr[start:end + 1]
            return subarray

        end += 1

    return subarray  # Return an empty list if no subarray is found

def main():
    arr = [1, 4, 20, 3, 10, 5]
    target_sum = 33

    subarray = find_subarray_with_sum(arr, target_sum)
    if subarray:
        print("Subarray with target sum found:", subarray)
    else:
        print("No subarray with target sum found.")

if __name__ == "__main__":
    main()

Both of these programs use the sliding window approach to find a subarray with the given target sum. They should produce the same output:

Subarray with target sum found: [20, 3, 10]

Sliding Window Technique

Imagine you have a long row of numbers, and you want to find the maximum sum of a group of consecutive numbers within that row. The Sliding Window Technique is a strategy that helps you efficiently solve problems like this.

Here’s how it works:

1. Choosing the Window Size: You start by choosing a window size, which is the number of consecutive elements you want to consider at a time. Let’s say you choose a window size of 3. So, you’ll take the first 3 numbers from the row to begin with.
2. Calculating Initial Sum: You calculate the sum of the numbers within the first window. For example, if your row starts with the numbers 5, 2, and 8, the sum would be 5 + 2 + 8 = 15.
3. Sliding the Window: Now, instead of moving the whole window by one position, you slide it by just one number. So, you move the window one step to the right. If your row was [5, 2, 8, 6, 1], after sliding, your window would now cover the numbers 2, 8, and 6.
4. Updating the Sum: Instead of recalculating the sum from scratch, you can optimize the process by subtracting the leftmost number that left the window and adding the rightmost number that entered the window. This is the key idea of the Sliding Window Technique – you’re reusing calculations to avoid redundant work. So, your new sum would be 2 + 8 + 6 = 16.
5. Continue Sliding: You keep sliding the window one step at a time and updating the sum until the end of your row. After the previous step, your window would move to cover the numbers 8, 6, and 1, and the sum would be 8 + 6 + 1 = 15.
6. Tracking Maximum: While sliding the window and updating the sum, you also keep track of the maximum sum you’ve encountered so far. In this case, the maximum sum would be 16.

The Sliding Window Technique is especially useful when you want to find patterns or properties in a sequence of elements, such as maximizing or minimizing some value within a range. It’s efficient because it avoids redundant calculations and works in a linear or nearly linear time complexity, making it a great tool for solving various types of problems.

Java:

public class SlidingWindowMaxSum {

    public static int maxSum(int[] arr, int windowSize) {
        int maxSum = Integer.MIN_VALUE;
        int currentSum = 0;

        // Calculate the initial sum for the first window
        for (int i = 0; i < windowSize; i++) {
            currentSum += arr[i];
        }
        maxSum = Math.max(maxSum, currentSum);

        // Slide the window and update the sum
        for (int i = windowSize; i < arr.length; i++) {
            currentSum = currentSum - arr[i - windowSize] + arr[i];
            maxSum = Math.max(maxSum, currentSum);
        }

        return maxSum;
    }

    public static void main(String[] args) {
        int[] arr = {5, 2, 8, 6, 1};
        int windowSize = 3;
        int result = maxSum(arr, windowSize);
        System.out.println("Maximum sum of subarray: " + result);
    }
}

Python:

def max_sum(arr, window_size):
    max_sum = float("-inf")
    current_sum = sum(arr[:window_size])

    max_sum = max(max_sum, current_sum)

    for i in range(window_size, len(arr)):
        current_sum = current_sum - arr[i - window_size] + arr[i]
        max_sum = max(max_sum, current_sum)

    return max_sum

if __name__ == "__main__":
    arr = [5, 2, 8, 6, 1]
    window_size = 3
    result = max_sum(arr, window_size)
    print("Maximum sum of subarray:", result)

Both the Java and Python programs do the same thing: they calculate the maximum sum of a subarray using the sliding window technique. The maxSum (in Java) and max_sum (in Python) functions take the array and the window size as input and return the maximum sum. The programs slide the window and update the sum efficiently to find the maximum sum of a subarray.

Thank You!