Find the Subarray with given sum

Given an array of non-negative integers arr and an integer target_sum, find a continuous subarray that adds up to target_sum. Return the 1-indexed starting and ending positions of the subarray. If there is no such subarray, return -1.

Input/Output Examples

plaintext
Example 1:
Input:
arr = [1, 2, 3, 7, 5]
target_sum = 12
Output: [2, 4]
Explanation: The subarray [2, 3, 7] sums up to 12 and is located between indices 2 and 4.

Example 2:
Input:
arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
target_sum = 15
Output: [1, 5]
Explanation: The subarray [1, 2, 3, 4, 5] sums up to 15 and is located between indices 1 and 5.

Example 3:
Input:
arr = [1, 4, 20, 3, 10, 5]
target_sum = 33
Output: [3, 5]
Explanation: The subarray [20, 3, 10] sums up to 33 and is located between indices 3 and 5.

Approach to find the subarray with given sum

  1. Use a Sliding Window Technique:
    • Initialize two pointers, start and end, at the beginning of the array, and set the current_sum to 0.
  2. Expand and Contract the Window:
    • Add elements to current_sum by moving the end pointer. If current_sum exceeds target_sum, move the start pointer right to reduce the current_sum.
    • Continue adjusting start and end until current_sum equals target_sum or the end of the array is reached.
  3. Return the Indices:
    • If current_sum matches target_sum, return the 1-indexed positions of start and end. If no such subarray is found, return -1.

C++ Program to find the subarray with given sum

cpp
#include <iostream>
#include <vector>
using namespace std;

// Function to find the subarray with the given sum
vector<int> subarrayWithGivenSum(vector<int>& arr, int target_sum) {
    int start = 0, current_sum = 0;

    // Traverse the array with a sliding window
    for (int end = 0; end < arr.size(); end++) {
        current_sum += arr[end];

        // Shrink the window from the left if the current sum exceeds the target
        while (current_sum > target_sum && start < end) {
            current_sum -= arr[start];
            start++;
        }

        // Check if the current sum matches the target sum
        if (current_sum == target_sum) {
            return {start + 1, end + 1}; // Return 1-indexed positions
        }
    }

    return {-1}; // No subarray found
}

int main() {
    vector<int> arr = {1, 2, 3, 7, 5};
    int target_sum = 12;
    vector<int> result = subarrayWithGivenSum(arr, target_sum);

    if (result[0] != -1) {
        cout << "Subarray with given sum found at indices: " << result[0] << " to " << result[1] << endl;
    } else {
        cout << "No subarray with given sum found." << endl;
    }

    return 0;
}

Java Program to find the subarray with given sum

java
import java.util.Arrays;

public class SubarrayWithGivenSum {

    // Function to find the subarray with the given sum
    public static int[] subarrayWithGivenSum(int[] arr, int target_sum) {
        int start = 0, current_sum = 0;

        // Traverse the array with a sliding window
        for (int end = 0; end < arr.length; end++) {
            current_sum += arr[end];

            // Shrink the window from the left if the current sum exceeds the target
            while (current_sum > target_sum && start < end) {
                current_sum -= arr[start];
                start++;
            }

            // Check if the current sum matches the target sum
            if (current_sum == target_sum) {
                return new int[]{start + 1, end + 1}; // Return 1-indexed positions
            }
        }

        return new int[]{-1}; // No subarray found
    }

    public static void main(String[] args) {
        int[] arr = {1, 2, 3, 7, 5};
        int target_sum = 12;
        int[] result = subarrayWithGivenSum(arr, target_sum);

        if (result[0] != -1) {
            System.out.println("Subarray with given sum found at indices: " + result[0] + " to " + result[1]);
        } else {
            System.out.println("No subarray with given sum found.");
        }
    }
}

Python Program to find the subarray with given sum

python
# Function to find the subarray with the given sum
def subarray_with_given_sum(arr, target_sum):
    start = 0
    current_sum = 0

    # Traverse the array with a sliding window
    for end in range(len(arr)):
        current_sum += arr[end]

        # Shrink the window from the left if the current sum exceeds the target
        while current_sum > target_sum and start < end:
            current_sum -= arr[start]
            start += 1

        # Check if the current sum matches the target sum
        if current_sum == target_sum:
            return [start + 1, end + 1] # Return 1-indexed positions

    return [-1] # No subarray found

# Example usage
if __name__ == "__main__":
    arr = [1, 2, 3, 7, 5]
    target_sum = 12
    result = subarray_with_given_sum(arr, target_sum)

    if result[0] != -1:
        print("Subarray with given sum found at indices:", result[0], "to", result[1])
    else:
        print("No subarray with given sum found.")

Time Complexity:

  • O(n): The algorithm makes a single pass over the array with an adjustable window, leading to linear time complexity.

Space Complexity:

  • O(1): Only a few extra variables are used, resulting in constant space usage.

DSA

1103

560

Related Articles