Problem Overview & Intuition

Using the prefix sum property, if the cumulative sum up to index i is S, and the sum up to index j is S - K, then the subarray from j + 1 to i has sum K. By caching the earliest occurrence of each prefix sum in a hash map, we maximize i - j in O(N) time.

Step-by-Step Approach

1. Initialize prefixMap = new Map(), currentSum = 0, and maxLen = 0.
2. Iterate through the array with index i.
3. Accumulate currentSum += arr[i].
4. If currentSum === K, update maxLen = i + 1.
5. If prefixMap.has(currentSum - K), update maxLen = Math.max(maxLen, i - prefixMap.get(currentSum - K)).
6. Only store prefixMap.set(currentSum, i) if currentSum is not already present (we want the earliest index for maximum length).
7. Return maxLen.

Optimal Implementation (JavaScript)

function longestSubarrayWithSumK(arr, K) {
  const prefixMap = new Map();
  let currentSum = 0;
  let maxLen = 0;

  for (let i = 0; i < arr.length; i++) {
    currentSum += arr[i];

    if (currentSum === K) {
      maxLen = i + 1;
    }

    const needed = currentSum - K;
    if (prefixMap.has(needed)) {
      maxLen = Math.max(maxLen, i - prefixMap.get(needed));
    }

    if (!prefixMap.has(currentSum)) {
      prefixMap.set(currentSum, i);
    }
  }

  return maxLen;
}

Complexity Analysis