Longest Subarray with Sum K

Given an array arr[] containing integers and an integer k, your task is to find the length of the longest subarray where the sum of its elements is equal to the given value k. If there is no subarray with sum equal to k, return 0.

Examples:

Input: arr[] = [10, 5, 2, 7, 1, -10], k = 15
Output: 6
Explanation: Subarrays with sum = 15 are [5, 2, 7, 1], [10, 5] and [10, 5, 2, 7, 1, -10]. The length of the longest subarray with a sum of 15 is 6.

Input: arr[] = [-5, 8, -14, 2, 4, 12], k = -5
Output: 5
Explanation: Only subarray with sum = 15 is [-5, 8, -14, 2, 4] of length 5.

Input: arr[] = [10, -10, 20, 30], k = 5
Output: 0
Explanation: No subarray with sum = 5 is present in arr[].

Constraints:
1 ≤ arr.size() ≤ 10⁵
-10⁴ ≤ arr[i] ≤ 10⁴
-10⁹ ≤ k ≤ 10⁹

Approach 01:

class Solution {
public:
    int longestSubarray(vector<int>& nums, int targetSum) {
        int size = nums.size();
        int currentPrefixSum = 0;
        unordered_map<int, int> prefixIndexMap = {{0, -1}};
        int maxLength = 0;

        // Traverse the array and calculate the prefix sum
        for (int i = 0; i < size; ++i) {
            currentPrefixSum += nums[i];
            int requiredSum = currentPrefixSum - targetSum;

            // Check if the required prefix sum exists
            if (prefixIndexMap.find(requiredSum) != prefixIndexMap.end()) {
                maxLength = max(maxLength, i - prefixIndexMap[requiredSum]);
            }

            // Store the current prefix sum in the map if not already present
            if (prefixIndexMap.find(currentPrefixSum) == prefixIndexMap.end()) {
                prefixIndexMap[currentPrefixSum] = i;
            }
        }

        return maxLength;
    }
};

class Solution:
    def longestSubarray(self, nums, targetSum):
        size = len(nums)
        currentPrefixSum = 0
        prefixIndexMap = {0: -1}
        maxLength = 0

        # Traverse the array and calculate the prefix sum
        for i in range(size):
            currentPrefixSum += nums[i]
            requiredSum = currentPrefixSum - targetSum

            # Check if the required prefix sum exists
            if requiredSum in prefixIndexMap:
                maxLength = max(maxLength, i - prefixIndexMap[requiredSum])

            # Store the current prefix sum in the map if not already present
            if currentPrefixSum not in prefixIndexMap:
                prefixIndexMap[currentPrefixSum] = i

        return maxLength

Time Complexity:

• Array Traversal:

  We traverse the array once, which takes \( O(n) \), where \( n \) is the size of the array.

• Prefix Sum Map Operations:

  For each element in the array, we perform \( O(1) \) operations for insertion and lookup in the hash map. This adds up to \( O(n) \) for all elements.

• Overall Time Complexity:

  The total time complexity is \( O(n) \).

Space Complexity:

• Hash Map:

  The hash map stores at most \( n + 1 \) entries (one for each prefix sum plus the initial zero sum). This takes \( O(n) \) space.

• Overall Space Complexity:

  The total space complexity is \( O(n) \).