Introduction

The Longest Subarray with Sum K problem involves finding the longest contiguous subarray whose sum is equal to a given value k.

Given an array arr[] of size n and an integer k, the task is to find the length of the longest subarray having sum equal to k.

This is one of the most important array problems and helps in understanding Prefix Sum, Hashing, and Sliding Window optimization techniques.

Example

Input: arr[] = [1, 2, 3, 1, 1, 1, 1]k = 6
Output: 4
Explanation:
Subarray [1, 2, 3] → Sum = 6
Length = 3
Subarray [3, 1, 1, 1] → Sum = 6
Length = 4
Longest Length = 4
Input: arr[] = [2, 1, 1, 1, 3, 2]
k = 5
Output: 4
Explanation:
Subarray [1, 1, 1, 2] → Sum = 5
Length = 4

Constraints

1 <= n <= 10^5-10^9 <= arr[i] <= 10^9
-10^9 <= k <= 10^9

Approach 1 : Brute Force

Explanation

The simplest way to solve this problem is:

  1. Generate all possible subarrays
  2. Calculate sum of every subarray
  3. Check whether the sum equals k
  4. Track the maximum length

This approach is easy to understand but recalculating sums repeatedly increases time complexity.

Steps

  1. Traverse all starting indices.
  2. For every starting index:
    • generate all subarrays
  3. Calculate current subarray sum.
  4. If sum equals k:
    • update maximum length
  5. Return the longest length.

Dry Run

Input Array: [1, 2, 3, 1, 1, 1, 1]k = 6
Subarray [1]:
Sum = 1
Subarray [1, 2]:
Sum = 3
Subarray [1, 2, 3]:
Sum = 6
Length = 3
Update Maximum Length = 3
Subarray [3, 1, 1, 1]:
Sum = 6
Length = 4
Update Maximum Length = 4
Final Result: 4

Brute Force Code 


Complexity Analysis

Time Complexity: O(n²)Explanation:
All possible subarrays are generated.

Space Complexity: O(1)
Explanation:
No extra data structures are used.

Approach 2 : Optimized Solution (Prefix Sum + HashMap)

Explanation

Instead of recalculating sums for every subarray, we can use:

  1. Prefix Sum
  2. HashMap

The idea is:

  • Store prefix sums and their indices
  • If (currentSum-k) exists in the map:
    • a valid subarray exists
  • Update maximum length accordingly

This avoids repeated traversals and improves efficiency.

Steps

  1. Initialize:
    • prefix sum = 0
    • hashmap
    • maximum length = 0
  2. Traverse the array.
  3. Add current element to prefix sum.
  4. If prefix sum equals k:
    • update maximum length
  5. If (prefixSum-k) exists:
    • calculate valid subarray length
  6. Store prefix sum if not already present.

Dry Run

Input Array: [1, 2, 3, 1, 1, 1, 1]k = 6
Traverse 1:
Prefix Sum = 1
Store:
1 → index 0
Traverse 2:
Prefix Sum = 3
Store:
3 → index 1
Traverse 3:
Prefix Sum = 6
Prefix Sum == k
Length = 3
Update Maximum Length = 3
Traverse 1:
Prefix Sum = 7
7 - 6 = 1 exists in map
Length = 4 - 0 = 4
Update Maximum Length = 4
Final Result: 4

Optimized Code

Complexity Analysis

Time Complexity: O(n)Explanation:
Each element is processed once using HashMap lookups.

Space Complexity: O(n)
Explanation:
HashMap stores prefix sums and indices.

Edge Cases

  1. Array contains negative numbers
  2. No valid subarray exists
  3. Entire array sum equals k
  4. Multiple valid subarrays exist
  5. Array contains zeros

Why This Problem is Important

This problem helps in understanding:

  1. Prefix Sum Technique
  2. HashMap optimization
  3. Subarray problems
  4. Efficient traversal
  5. Sliding Window concepts

It is one of the most important interview problems in arrays and hashing.

Real-World Applications

Prefix Sum techniques are used in:

  1. Financial analytics
  2. Data stream processing
  3. Time-series analysis
  4. Network traffic monitoring
  5. Large dataset optimization

Common Mistakes

  1. Incorrect prefix sum updates
  2. Forgetting hashmap checks
  3. Overwriting existing prefix sums
  4. Incorrect subarray length calculation

Interview Tips

Interviewers often expect:

  1. Prefix Sum optimization
  2. HashMap usage
  3. O(n) solution

Always explain why storing the first occurrence of prefix sums is important.

Related Questions

  1. Subarray Sum Equals K
  2. Count Subarrays with Sum K
  3. Maximum Size Subarray Sum Equals K
  4. Prefix Sum Problems
  5. Sliding Window Maximum

Final Takeaway

The Longest Subarray with Sum K problem is a fundamental Prefix Sum and Hashing problem that teaches efficient subarray optimization techniques. Understanding this problem builds a strong foundation for advanced hashing, prefix sum, and sliding window interview problems.