Java - Indexes of Subarray Sum
Problem Statement
Given an array arr[] of size N and an integer targetSum, find the indexes (0-based) of the subarray whose sum equals targetSum.
If multiple subarrays exist, return the first occurrence.
If no such subarray exists, return [-1, -1].
Example 1:
Input: arr[] = {1, 4, 20, 3, 10, 5}, targetSum = 33
Output: [2, 4]
Explanation:
The subarray {20, 3, 10} (from index 2 to 4) has a sum of 33.
Example 2:
Input: arr[] = {10, 2, -2, -20, 10}, targetSum = -10
Output: [1, 3]
Explanation:
The subarray {2, -2, -20} (from index 1 to 3) has sum -10.
Approach 1: Brute Force (O(N²))
Iterate over all subarrays.
Compute sum for each subarray.
Stop when sum == targetSum.
Code Implementation
public class SubarraySumBruteForce {
public static int[] findSubarray(int[] arr, int targetSum) {
int n = arr.length;
for (int i = 0; i < n; i++) {
int sum = 0;
for (int j = i; j < n; j++) {
sum += arr[j];
if (sum == targetSum) {
return new int[]{i, j}; // Found subarray
}
}
}
return new int[]{-1, -1}; // No subarray found
}
public static void main(String[] args) {
int[] arr = {1, 4, 20, 3, 10, 5};
int targetSum = 33;
int[] result = findSubarray(arr, targetSum);
System.out.println("Indexes: [" + result[0] + ", " + result[1] + "]");
}
}
Time Complexity
O(N²) (nested loops).
Not efficient for large N.
Approach 2: Using HashMap (O(N))
Uses prefix sum and HashMap:
Compute prefix sum and store it in a HashMap.
If prefixSum - targetSum exists in the map, we found a valid subarray.
Code Implementation
import java.util.*;
public class SubarraySumHashMap {
public static int[] findSubarray(int[] arr, int targetSum) {
Map<Integer, Integer> prefixSumMap = new HashMap<>();
int prefixSum = 0;
for (int i = 0; i < arr.length; i++) {
prefixSum += arr[i];
// If prefixSum itself is the targetSum
if (prefixSum == targetSum) {
return new int[]{0, i};
}
// If (prefixSum - targetSum) exists in map, we found a subarray
if (prefixSumMap.containsKey(prefixSum - targetSum)) {
return new int[]{prefixSumMap.get(prefixSum - targetSum) + 1, i};
}
// Store current prefixSum with index
prefixSumMap.put(prefixSum, i);
}
return new int[]{-1, -1}; // No subarray found
}
public static void main(String[] args) {
int[] arr = {10, 2, -2, -20, 10};
int targetSum = -10;
int[] result = findSubarray(arr, targetSum);
System.out.println("Indexes: [" + result[0] + ", " + result[1] + "]");
}
}
