Given a 1-based indexing array arr[] of non-negative integers and an integer sum. Find the left and right indexes(1-based indexing) of that subarray that is equal to the given sum. In case of multiple subarrays, find the subarray indexes which come first on moving from left to right. If no such subarray exists return an array consisting of element -1.
Examples:
Input: arr[] = [15, 2, 4, 8, 9, 5, 10, 23], target = 23
Output: [2, 5]
Explanation: Sum of subarray arr[2...5] is 2 + 4 + 8 + 9 = 23.Input: arr[] = [1, 10, 4, 0, 3, 5], target = 7
Output: [3, 5]
Explanation: Sum of subarray arr[3...5] is 4 + 0 + 3 = 7.Input: arr[] = [1, 4], target = 0
Output: [-1]
Explanation: There is no subarray with 0 sum.
Try it on GfG Practice
Table of Content
[Naive Approach] Using Nested loop - O(n^2) Time and O(1) Space
- Use a nested loop where the outer loop selects the starting index of the subarray.
- The inner loop keeps adding elements to a running sum starting from that index.
- If the sum equals the target, return the 1-based start and end indices; otherwise, return -1 if no subarray is found.
#include <iostream>
#include <vector>
using namespace std;
vector<int> subarraySum(vector<int> arr, int target) {
vector<int> res;
int n = arr.size();
// Pick a starting point for a subarray
for (int s = 0; s < n; s++) {
int curr = 0;
// Consider all ending points
// for the picked starting point
for (int e = s; e < n; e++) {
curr += arr[e];
if (curr == target) {
res.push_back(s + 1);
res.push_back(e + 1);
return res;
}
}
}
// If no subarray is found
return {-1};
}
int main() {
vector<int> arr = {15, 2, 4, 8, 9, 5, 10, 23};
int target = 23;
vector<int> res = subarraySum(arr, target);
for (int ele : res)
cout << ele << " ";
return 0;
}
import java.util.ArrayList;
import java.util.List;
class GfG {
static ArrayList<Integer> subarraySum(int[] arr, int target) {
ArrayList<Integer> res = new ArrayList<>();
int n = arr.length;
// Pick a starting point for a subarray
for (int s = 0; s < n; s++) {
int curr = 0;
// Consider all ending points
// for the picked starting point
for (int e = s; e < n; e++) {
curr += arr[e];
if (curr == target) {
res.add(s + 1);
res.add(e + 1);
return res;
}
}
}
// If no subarray is found
res.add(-1);
return res;
}
public static void main(String[] args) {
int[] arr = {15, 2, 4, 8, 9, 5, 10, 23};
int target = 23;
ArrayList<Integer> res = subarraySum(arr, target);
for (int ele : res)
System.out.print(ele + " ");
}
}
def subarraySum(arr, target):
res = []
n = len(arr)
# Pick a starting point for a subarray
for s in range(n):
curr = 0
# Consider all ending points
# for the picked starting point
for e in range(s, n):
curr += arr[e]
if curr == target:
res.append(s + 1)
res.append(e + 1)
return res
# If no subarray is found
return [-1]
if __name__ == "__main__":
arr = [15, 2, 4, 8, 9, 5, 10, 23]
target = 23
res = subarraySum(arr, target)
for ele in res:
print(ele, end=" ")
using System;
using System.Collections.Generic;
class GfG {
static List<int> subarraySum(int[] arr, int target) {
List<int> res = new List<int>();
int n = arr.Length;
// Pick a starting point for a subarray
for (int s = 0; s < n; s++) {
int curr = 0;
// Consider all ending points
// for the picked starting point
for (int e = s; e < n; e++) {
curr += arr[e];
if (curr == target) {
res.Add(s + 1);
res.Add(e + 1);
return res;
}
}
}
// If no subarray is found
res.Add(-1);
return res;
}
static void Main() {
int[] arr = {15, 2, 4, 8, 9, 5, 10, 23};
int target = 23;
List<int> res = subarraySum(arr, target);
foreach (var ele in res)
Console.Write(ele + " ");
}
}
function subarraySum(arr, target) {
let res = [];
let n = arr.length;
// Pick a starting point for a subarray
for (let s = 0; s < n; s++) {
let curr = 0;
// Consider all ending points
// for the picked starting point
for (let e = s; e < n; e++) {
curr += arr[e];
if (curr === target) {
res.push(s + 1);
res.push(e + 1);
return res;
}
}
}
// If no subarray is found
return [-1];
}
// Driver Code
let arr = [15, 2, 4, 8, 9, 5, 10, 23];
let target = 23;
let res = subarraySum(arr, target);
console.log(res.join(' '));
Output
2 5
[Expected Approach] Sliding Window - O(n) Time and O(1) Space
- Since all elements are positive, subarray (or window) sum increases subarray is expanded.
- Expand the window while the sum is less than the target. If the sum exceeds the target, shrink from the left; if equal, return the subarray.
#include <iostream>
#include <vector>
using namespace std;
vector<int> subarraySum(vector<int>& arr, int target) {
// Initialize window
int s = 0, e = 0;
vector<int> res;
int curr = 0;
for (int i = 0; i < arr.size(); i++) {
curr += arr[i];
// If current sum becomes more or equal,
// set end and try adjusting start
if (curr >= target) {
e = i;
// While current sum is greater,
// remove starting elements of current window
while (curr > target && s < e) {
curr -= arr[s];
++s;
}
// If we found a subraay
if (curr == target) {
res.push_back(s + 1);
res.push_back(e + 1);
return res;
}
}
}
// If no subarray is found
return {-1};
}
int main() {
vector<int> arr = {15, 2, 4, 8, 9, 5, 10, 23};
int target = 23;
vector<int> res = subarraySum(arr, target);
for (int ele : res)
cout << ele << " ";
return 0;
}
import java.util.ArrayList;
import java.util.List;
class GfG {
static ArrayList<Integer> subarraySum(int[] arr, int target) {
// Initialize window
int s = 0, e = 0;
ArrayList<Integer> res = new ArrayList<>();
int curr = 0;
for (int i = 0; i < arr.length; i++) {
curr += arr[i];
// If current sum becomes more or equal,
// set end and try adjusting start
if (curr >= target) {
e = i;
// While current sum is greater,
// remove starting elements of current window
while (curr > target && s < e) {
curr -= arr[s];
++s;
}
// If we found a subarray
if (curr == target) {
res.add(s + 1);
res.add(e + 1);
return res;
}
}
}
// If no subarray is found
res.add(-1);
return res;
}
public static void main(String[] args) {
int[] arr = {15, 2, 4, 8, 9, 5, 10, 23};
int target = 23;
ArrayList<Integer> res = subarraySum(arr, target);
for (int ele : res)
System.out.print(ele + " ");
}
}
def subarraySum(arr, target):
# Initialize window
s, e = 0, 0
res = []
curr = 0
for i in range(len(arr)):
curr += arr[i]
# If current sum becomes more or equal,
# set end and try adjusting start
if curr >= target:
e = i
# While current sum is greater,
# remove starting elements of current window
while curr > target and s < e:
curr -= arr[s]
s += 1
# If we found a subarray
if curr == target:
res.append(s + 1)
res.append(e + 1)
return res
# If no subarray is found
return [-1]
if __name__ == "__main__":
arr = [15, 2, 4, 8, 9, 5, 10, 23]
target = 23
res = subarraySum(arr, target)
print(" ".join(map(str, res)))
using System;
using System.Collections.Generic;
class GfG {
static List<int> subarraySum(int[] arr, int target) {
// Initialize window
int s = 0, e = 0;
List<int> res = new List<int>();
int curr = 0;
for (int i = 0; i < arr.Length; i++) {
curr += arr[i];
// If current sum becomes more or equal,
// set end and try adjusting start
if (curr >= target) {
e = i;
// While current sum is greater,
// remove starting elements of current window
while (curr > target && s < e) {
curr -= arr[s];
++s;
}
// If we found a subarray
if (curr == target) {
res.Add(s + 1);
res.Add(e + 1);
return res;
}
}
}
// If no subarray is found
res.Add(-1);
return res;
}
static void Main() {
int[] arr = {15, 2, 4, 8, 9, 5, 10, 23};
int target = 23;
List<int> res = subarraySum(arr, target);
foreach (var ele in res)
Console.Write(ele + " ");
}
}
function subarraySum(arr, target) {
// Initialize window
let s = 0, e = 0;
let res = [];
let curr = 0;
for (let i = 0; i < arr.length; i++) {
curr += arr[i];
// If current sum becomes more or equal,
// set end and try adjusting start
if (curr >= target) {
e = i;
// While current sum is greater,
// remove starting elements of current window
while (curr > target && s < e) {
curr -= arr[s];
s++;
}
// If we found a subarray
if (curr === target) {
res.push(s + 1);
res.push(e + 1);
return res;
}
}
}
// If no subarray is found
return [-1];
}
// Driver Code
let arr = [15, 2, 4, 8, 9, 5, 10, 23];
let target = 23;
let res = subarraySum(arr, target);
console.log(res.join(' '));
Output
2 5
[Alternate Approach] Hashing + Prefix Sum - O(n) Time and O(n) Space
- The above sliding window solution fails when negative numbers are present, so we use prefix sum with hashing.
- Store the prefix sum at each index in a hashmap while traversing the array.
- If at any index currSum - target exists in the hashmap, then a subarray with the required sum exists.
To know more about the implementation, please refer Subarray with Given Sum – Handles Negative Numbers.