Geeksforgeeks: Longest Subarray with Sum K

 Longest Subarray with Sum K

Difficulty: Medium

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() ≤ 105
-104 ≤ arr[i] ≤ 104
-109 ≤ k ≤ 109

To solve the problem of finding the length of the longest subarray with a sum equal to a given value k, we can use a hash map (or dictionary) to track the cumulative sum of elements as we traverse the array. This approach allows us to efficiently find the required subarray in O(n) time.

Approach:

1. Cumulative Sum (Prefix Sum):

   • As we iterate through the array, we keep a running sum of the elements.
   • For each element, we check if the difference between the current sum and k has been encountered before in the hash map. If it has, it means there is a subarray whose sum equals k.
   • We also store the first occurrence of each cumulative sum to maximize the length of the subarray when we find a match.

2. Hash Map:

   • The key in the hash map is the cumulative sum, and the value is the first index at which that cumulative sum occurs.
   • If we encounter a cumulative sum that has been seen before, the subarray between the current index and the first occurrence of that cumulative sum has a sum equal to k.

Detailed Steps:

• Initialize the cumulative sum to 0.
• Iterate through the array, updating the cumulative sum.
• For each cumulative sum, check if the difference between the cumulative sum and k exists in the hash map.
  • If it does, calculate the length of the subarray.
  • If it doesn’t exist, add the cumulative sum to the hash map with its index.
• Keep track of the maximum length found.

Code Implementation (C#):

using System;
using System.Collections.Generic;

public class Solution {
    public int LongestSubarrayWithSumK(int[] arr, int k) {
        // Dictionary to store the first occurrence of cumulative sum
        Dictionary<int, int> map = new Dictionary<int, int>();
        
        int maxLength = 0;
        int cumulativeSum = 0;
        
        // Iterate through the array
        for (int i = 0; i < arr.Length; i++) {
            cumulativeSum += arr[i];
            
            // Check if cumulative sum is equal to k
            if (cumulativeSum == k) {
                maxLength = i + 1;
            }
            
            // Check if the cumulative sum minus k has been seen before
            if (map.ContainsKey(cumulativeSum - k)) {
                // Update maxLength
                maxLength = Math.Max(maxLength, i - map[cumulativeSum - k]);
            }
            
            // Store the first occurrence of the cumulative sum
            if (!map.ContainsKey(cumulativeSum)) {
                map[cumulativeSum] = i;
            }
        }
        
        return maxLength;
    }
}

class Program {
    static void Main(string[] args) {
        Solution solution = new Solution();
        
        int[] arr1 = { 10, 5, 2, 7, 1, -10 };
        int k1 = 15;
        Console.WriteLine(solution.LongestSubarrayWithSumK(arr1, k1));  // Output: 6
        
        int[] arr2 = { -5, 8, -14, 2, 4, 12 };
        int k2 = -5;
        Console.WriteLine(solution.LongestSubarrayWithSumK(arr2, k2));  // Output: 5
        
        int[] arr3 = { 10, -10, 20, 30 };
        int k3 = 5;
        Console.WriteLine(solution.LongestSubarrayWithSumK(arr3, k3));  // Output: 0
    }
}

Explanation of the Code:

1. Initialize Variables:

   • maxLength: Keeps track of the length of the longest subarray found with sum k.
   • cumulativeSum: The sum of elements from the start of the array to the current index.
   • map: A dictionary that stores the first occurrence of each cumulative sum.

2. Main Logic:

   • For each element in the array, we add it to cumulativeSum.
   • If cumulativeSum equals k, it means the subarray from index 0 to the current index has a sum equal to k.
   • If cumulativeSum - k is found in the dictionary, it means the subarray from the index after the stored index to the current index has a sum equal to k.
   • The length of such a subarray is i - map[cumulativeSum - k], and we update maxLength if this length is greater than the current maxLength.
   • We store the first occurrence of each cumulativeSum to ensure we are always considering the longest subarray.

Time Complexity:

• Time Complexity: $O(n)$, where n is the number of elements in the array. This is because we are iterating through the array once and performing constant-time operations (hash map lookups and updates).
• Space Complexity: $O(n)$, since we are storing up to n unique cumulative sums in the hash map.

Edge Cases:

• If the entire array sums to k, the subarray would be the entire array.
• If no subarray sums to k, the result will be 0.
• The array can contain negative numbers, and the approach still works due to how cumulative sums are calculated and checked.

Examples:

1. Input: arr[] = [10, 5, 2, 7, 1, -10], k = 15

   • Output: 6
   • Subarrays with sum 15 are: [5, 2, 7, 1], [10, 5], and [10, 5, 2, 7, 1, -10].

2. Input: arr[] = [-5, 8, -14, 2, 4, 12], k = -5

   • Output: 5
   • Subarray with sum -5 is: [-5, 8, -14, 2, 4].

3. Input: arr[] = [10, -10, 20, 30], k = 5

   • Output: 0
   • No subarray with sum 5 is present.

This solution efficiently solves the problem with optimal time and space complexity.