Subarray with Given Sum

Problem Statement

Given an array of integers and a target sum S, find a contiguous subarray whose elements add up to S.

You need to:

• Print the starting and ending indices
  OR
• Print the subarray itself (as per problem requirement)

If no such subarray exists, print "No subarray found".

Key Difference from Two Sum

Example 1 (Positive Numbers)

Input

arr = [1, 4, 20, 3, 10, 5]
S = 33

Output

Subarray found from index 2 to 4

Explanation

20 + 3 + 10 = 33

Example 2

Input

arr = [1, 2, 3, 7, 5]
S = 12

Output

Subarray found from index 1 to 3

Important Observation

The approach depends on array type:

1. Only Positive Numbers → Sliding Window
2. Contains Negative Numbers → Prefix Sum + Hash Map

Approach 1: Sliding Window (For Positive Numbers Only)

Core Idea

• Expand window by moving end
• If sum becomes greater than target, shrink window from start
• Stop when sum equals target

Algorithm

1. Initialize:
   • start = 0
   • currentSum = 0
2. Traverse array using end
3. Add arr[end] to currentSum
4. While currentSum > S, subtract arr[start] and increment start
5. If currentSum == S, print indices

Time and Space Complexity

• Time Complexity: O(n)
• Space Complexity: O(1)

Below are the Subarray with Given Sum solutions, given one by one, clearly separated.

C Implementation

#include<stdio.h>

int main() {
    int arr[] = {1, 4, 20, 3, 10, 5};
    int n = 6;
    int S = 33;

    int start = 0, currSum = 0;

    for (int end = 0; end < n; end++) {
        currSum += arr[end];

        while (currSum > S && start <= end) {
            currSum -= arr[start];
            start++;
        }

        if (currSum == S) {
            printf("Subarray found from index %d to %d", start, end);
            return 0;
        }
    }

    printf("No subarray found");
    return 0;
}

Output

Subarray found from index 2 to 4

C++ Implementation

#include<iostream>
using namespace std;

int main() {
    int arr[] = {1, 4, 20, 3, 10, 5};
    int n = 6, S = 33;

    int start = 0, currSum = 0;

    for (int end = 0; end < n; end++) {
        currSum += arr[end];

        while (currSum > S && start <= end) {
            currSum -= arr[start++];
        }

        if (currSum == S) {
            cout << "Subarray found from index " << start << " to " << end;
            return 0;
        }
    }

    cout << "No subarray found";
    return 0;
}

Output

Subarray found from index 2 to 4

Java Implementation

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

        int start = 0, currSum = 0;

        for (int end = 0; end < arr.length; end++) {
            currSum += arr[end];

            while (currSum > S && start <= end) {
                currSum -= arr[start++];
            }

            if (currSum == S) {
                System.out.println("Subarray found from index " + start + " to " + end);
                return;
            }
        }

        System.out.println("No subarray found");
    }
}

Python Implementation

arr = [1, 4, 20, 3, 10, 5]
S = 33

start = 0
curr_sum = 0

for end in range(len(arr)):
    curr_sum += arr[end]

    while curr_sum > S and start <= end:
        curr_sum -= arr[start]
        start += 1

    if curr_sum == S:
        print("Subarray found from index", start, "to", end)
        break

JavaScript Implementation

let arr = [1, 4, 20, 3, 10, 5];
let S = 33;

let start = 0, currSum = 0;

for (let end = 0; end < arr.length; end++) {
    currSum += arr[end];

    while (currSum > S && start <= end) {
        currSum -= arr[start++];
    }

    if (currSum === S) {
        console.log("Subarray found from index", start, "to", end);
        break;
    }
}
.

Dry Run (Sliding Window)

arr = [1, 4, 20, 3, 10, 5], S = 33

end=0 → sum=1
end=1 → sum=5
end=2 → sum=25
end=3 → sum=28
end=4 → sum=38 (greater than 33)
Remove arr[0]=1 → sum=37
Remove arr[1]=4 → sum=33 → FOUND

Approach 2: Prefix Sum + Hash Map (Handles Negative Numbers)

When to Use

• Array contains negative numbers
• Sliding window fails because sum may decrease unexpectedly

Core Idea

If:

prefixSum[j] - prefixSum[i] = S

Then:

prefixSum[i] = prefixSum[j] - S

Store prefix sums in a hash map.

Algorithm

1. Initialize:
   • sum = 0
   • Hash map to store prefix sum and index
2. Traverse array:
   • Add current element to sum
3. If sum == S, subarray found from 0 to i
4. If (sum - S) exists in map:
   • Subarray exists from map[sum-S]+1 to i
5. Store sum in map if not already present

Time and Space Complexity

• Time Complexity: O(n)
• Space Complexity: O(n)

C++ Implementation

#include<iostream>
#include<unordered_map>
using namespace std;

int main() {
    int arr[] = {10, 2, -2, -20, 10};
    int n = 5, S = -10;

    unordered_map<int,int> mp;
    int sum = 0;

    for (int i = 0; i < n; i++) {
        sum += arr[i];

        if (sum == S) {
            cout << "Subarray found from index 0 to " << i;
            return 0;
        }

        if (mp.find(sum - S) != mp.end()) {
            cout << "Subarray found from index "
                 << mp[sum - S] + 1 << " to " << i;
            return 0;
        }

        mp[sum] = i;
    }

    cout << "No subarray found";
    return 0;
}

Output

Subarray found from index 0 to 3

Java Implementation

import java.util.*;

public class SubarrayPrefixSum {
    public static void main(String[] args) {
        int[] arr = {10, 2, -2, -20, 10};
        int S = -10;

        Map<Integer, Integer> map = new HashMap<>();
        int sum = 0;

        for (int i = 0; i < arr.length; i++) {
            sum += arr[i];

            if (sum == S) {
                System.out.println("Subarray found from index 0 to " + i);
                return;
            }

            if (map.containsKey(sum - S)) {
                System.out.println("Subarray found from index " +
                        (map.get(sum - S) + 1) + " to " + i);
                return;
            }

            map.put(sum, i);
        }

        System.out.println("No subarray found");
    }
}

Python Implementation

arr = [10, 2, -2, -20, 10]
S = -10

mp = {}
sum_val = 0

for i, num in enumerate(arr):
    sum_val += num

    if sum_val == S:
        print("Subarray found from index 0 to", i)
        break

    if (sum_val - S) in mp:
        print("Subarray found from index", mp[sum_val - S] + 1, "to", i)
        break

    mp[sum_val] = i

JavaScript Implementation

let arr = [10, 2, -2, -20, 10];
let S = -10;

let map = new Map();
let sum = 0;

for (let i = 0; i < arr.length; i++) {
    sum += arr[i];

    if (sum === S) {
        console.log("Subarray found from index 0 to", i);
        break;
    }

    if (map.has(sum - S)) {
        console.log(
            "Subarray found from index",
            map.get(sum - S) + 1,
            "to",
            i
        );
        break;
    }

    map.set(sum, i);
}

Summary

Key Takeaways

• Subarray means continuous
• Sliding window is fastest but limited
• Prefix sum handles all cases
• Common interview problem after Two Sum & Kadane

Next Problems in the Series

Longest Subarray with Sum K