Indexes of Subarray Sum Problem in Java

To tackle the indexes of subarray sum problem in Java, we're on the hunt for those special indices of a continuous subarray that add up to a specific target. This problem is common in algorithm interviews, especially when discussing hash maps for optimizing time complexity.

Problem Statement

Given an integer array arr[] and an integer targetSum, determine the indices of a consecutive subarray that sums to targetSum. If found, return its beginning and end indices; otherwise, indicate its absence.

Solution to the Problem

We will employ a HashMap to store cumulative sums as keys and their corresponding indices as values. As we traverse the array, we maintain a running sum of the elements. At each iteration:

1. If the cumulative sum equals targetSum, we ascertain that a subarray commencing at index 0 and extending to the current index achieves the target sum.
2. If the difference between the current cumulative sum and targetSum exists within the HashMap, it signifies the presence of a subarray whose sum is targetSum. The starting index of this subarray is immediately following the index stored in the HashMap, while the ending index is the current index.

Let's implement the above approach in a Java program.

File Name: SubarraySum.java

Output:

 Subarray found from index 1 to index 3 

Explanation

The findSubarrayWithTargetSum() method starts by initializing a HashMap called cumulativeSumMap(), which will store the cumulative sums encountered so far as keys, with the corresponding indices as values. Additionally, we initialize a cumulativeSum variable to keep track of the sum of elements as we iterate through the array.

For each element in the array, we add it to cumulativeSum. If this cumulative sum matches targetSum, we immediately know that the subarray from the start (index 0) to the current index is the solution. Otherwise, we check if cumulativeSum - targetSum exists in the map. If it does, then we have identified a subarray with the desired sum, as the portion of the array after the stored index up to the current index must add up to targetSum.

We then return the indices of this subarray. If neither condition is met, we store the current cumulative sum and index in the map to check against future elements. If the loop completes without finding a solution, we return {-1, -1} to signify that no such subarray exists. The main method tests this function with an example array and target sum, displaying the indices if a solution is found.

Complexity Analysis

Time Complexity

The solution's time complexity is O(n), where n is the input array's length. Because:

1. We traverse the array once, updating the cumulative sum and traversing the HashMap in each iteration.
2. HashMap operations for insertion and retrieval (determining the existence of a key) are O(1) on average, ensuring the efficiency of our solution.

Therefore, the entire operation necessitates a single pass through the array, resulting in a linear time complexity of O(n).

Space Complexity

The space complexity of this solution is bounded by the size of the HashMap, which is proportional to the input array's length. The space complexity of the proposed solution is also O(n), as we utilize a HashMap to store cumulative sums along with their corresponding indices.

In the worst-case scenario, each element in the array could potentially have a unique cumulative sum, necessitating the storage of all such sums in the HashMap, resulting in an O(n) space usage.

Conclusion

This approach to solving the subarray sum problem using cumulative sums and a HashMap is optimal for this specific problem type due to its efficient time and space complexity. The key insight lies in recognizing that if the cumulative sum at any point, minus the targetSum, has been encountered previously, then a subarray with the required sum must exist between the stored index of this cumulative sum and the current index.

This method provides a substantial improvement over the naive (O(n^2)) approach that involves checking all possible subarrays, making it suitable for large datasets. The algorithm's linear time complexity and straightforward implementation make it an ideal choice for solving contiguous subarray sum problems efficiently.