Indexes of Subarray Sum

Given an array arr[] containing only non-negative integers, your task is to find a continuous subarray (a contiguous sequence of elements) whose sum equals a specified value target. You need to return the 1-based indices of the leftmost and rightmost elements of this subarray. You need to find the first subarray whose sum is equal to the target.

Note: If no such array is possible then, return [-1].

Examples:

Input: arr[] = [1, 2, 3, 7, 5], target = 12
Output: [2, 4]
Explanation: The sum of elements from 2nd to 4th position is 12.

Input: arr[] = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10], target = 15
Output: [1, 5]
Explanation: The sum of elements from 1st to 5th position is 15.

Input: arr[] = [5, 3, 4], target = 2
Output: [-1]
Explanation: There is no subarray with sum 2.

Constraints:
1 <= arr.size()<= 10⁶
0 <= arr[i] <= 10³
0 <= target <= 10⁹

Approach 01:

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

class Solution {
public:
    vector<int> subarraySum(vector<int>& nums, int targetSum) {
        unordered_map<int, pair<int, int>> prefixSumMap; // Maps prefix sums to their frequency and last index
        int arraySize = nums.size();
        
        vector<int> prefixSums(arraySize, 0); // Stores the prefix sums of the array
        prefixSums[0] = nums[0];

        // Calculate prefix sums
        for (int i = 1; i < arraySize; i++) {
            prefixSums[i] = prefixSums[i - 1] + nums[i];
        }

        // Find the subarray with the given target sum
        for (int currentIndex = 0; currentIndex < arraySize; currentIndex++) {
            // Check if the prefix sum itself equals the target
            if (prefixSums[currentIndex] == targetSum) {
                return {1, currentIndex + 1}; // 1-based indexing
            }

            // Check if a previous prefix sum matches the required condition
            int requiredSum = prefixSums[currentIndex] - targetSum;
            if (prefixSumMap.find(requiredSum) != prefixSumMap.end()) {
                return {prefixSumMap[requiredSum].second + 1, currentIndex + 1}; // 1-based indexing
            }

            // Update the prefix sum map
            prefixSumMap[prefixSums[currentIndex]].first++;
            prefixSumMap[prefixSums[currentIndex]].second = currentIndex + 1; // Store 1-based index
        }

        return {-1}; // Return -1 if no subarray with the target sum is found
    }
};

class Solution:
    def subarraySum(self, nums, targetSum):
        prefixSumMap = {}  # Maps prefix sums to their frequency and last index
        prefixSums = [0] * len(nums)  # Stores the prefix sums of the array
        prefixSums[0] = nums[0]

        # Calculate prefix sums
        for i in range(1, len(nums)):
            prefixSums[i] = prefixSums[i - 1] + nums[i]

        # Find the subarray with the given target sum
        for currentIndex in range(len(nums)):
            # Check if the prefix sum itself equals the target
            if prefixSums[currentIndex] == targetSum:
                return [1, currentIndex + 1]  # 1-based indexing

            # Check if a previous prefix sum matches the required condition
            requiredSum = prefixSums[currentIndex] - targetSum
            if requiredSum in prefixSumMap:
                return [prefixSumMap[requiredSum][1] + 1, currentIndex + 1]  # 1-based indexing

            # Update the prefix sum map
            if prefixSums[currentIndex] not in prefixSumMap:
                prefixSumMap[prefixSums[currentIndex]] = (1, currentIndex + 1)  # Store 1-based index

        return [-1]  # Return -1 if no subarray with the target sum is found

Time Complexity:

• Prefix Sum Calculation:

  The prefix sums for the array are computed in a single pass, taking \( O(n) \), where \( n \) is the size of the array.

• Iterating Over the Array:

  The main loop iterates through the array once, resulting in \( O(n) \).

• Hash Map Operations:

  Each lookup and insertion in the hash map takes \( O(1) \) on average. Since there is one operation per iteration, this adds up to \( O(n) \).

• Overall Time Complexity:

  \( O(n) \).

Space Complexity:

• Prefix Sum Array:

  The array storing prefix sums has a size of \( n \), leading to \( O(n) \).

• Hash Map:

  The hash map stores at most \( n \) entries, where each entry corresponds to a unique prefix sum, contributing \( O(n) \) space.

• Overall Space Complexity:

  \( O(n) \).