Problem Description

Given an integer array nums and an integer k, find the length of the longest subarray that sums to exactly k. The subarray must be contiguous (elements must be consecutive in the array), and you cannot reuse elements from non-overlapping positions. If there is no such subarray, return 0.

• Input: nums (an array of integers), k (an integer target sum)
• Output: The maximum length of a contiguous subarray whose sum equals k
• Constraints: The array may contain positive, negative, or zero values. There may be multiple valid subarrays; return the length of the longest one.

Thought Process

At first glance, you might think to check every possible subarray, calculate its sum, and track the maximum length if the sum matches k. However, this brute-force approach would require checking every start and end index pair, resulting in a time complexity of O(n²), which is inefficient for large arrays.

To optimize, we can use the concept of prefix sums. The idea is that if the sum of elements from index 0 to i is sum_i, and the sum from 0 to j is sum_j, then the sum of the subarray from i+1 to j is sum_j - sum_i. If we can find two indices where this difference equals k, we've found a valid subarray.

To make this efficient, we use a hash map to record the earliest index where each prefix sum occurs. This allows us to check in constant time whether a subarray ending at the current index sums to k.

Solution Approach

• Step 1: Initialize a hash map (prefix_sum_indices) to store the first occurrence of each prefix sum. Also initialize current_sum to 0 and max_length to 0.
• Step 2: Loop through the array, updating current_sum by adding the current number.
• Step 3: If current_sum is exactly k, update max_length to the current index + 1 (since the subarray starts from the beginning).
• Step 4: If current_sum - k exists in the hash map, it means there is a previous prefix sum such that the subarray between that index + 1 and the current index sums to k. Calculate the length and update max_length if it's longer.
• Step 5: If current_sum is not already in the hash map, store it with the current index. (We only store the first occurrence to maximize the subarray length.)
• Step 6: After the loop, return max_length.

Using a hash map for prefix sums ensures O(1) lookups, making the solution efficient.

Example Walkthrough

Let's consider nums = [1, -1, 5, -2, 3] and k = 3.

• Initialize: prefix_sum_indices = {}, current_sum = 0, max_length = 0
• Index 0: Add 1 → current_sum = 1. Not equal to k. Store 1:0 in map.
• Index 1: Add -1 → current_sum = 0. Not equal to k. Store 0:1 in map.
• Index 2: Add 5 → current_sum = 5. 5 - 3 = 2 not in map. Store 5:2 in map.
• Index 3: Add -2 → current_sum = 3. Now current_sum == k, so max_length = 4 (from index 0 to 3).
• Index 4: Add 3 → current_sum = 6. 6 - 3 = 3 is in map at index 3. So subarray from 3+1 to 4 (just index 4) sums to k, length is 1. max_length remains 4.

The answer is 4, corresponding to subarray [1, -1, 5, -2].

Time and Space Complexity

• Brute-force:
  • Time Complexity: O(n²) — For each start index, check all possible end indices and sum the subarray.
  • Space Complexity: O(1) — Only a few variables needed.
• Optimized (Prefix Sum + Hash Map):
  • Time Complexity: O(n) — Each element is processed once; hash map lookups and inserts are O(1).
  • Space Complexity: O(n) — In the worst case, all prefix sums are unique and stored in the hash map.

Summary

This problem is elegantly solved with prefix sums and a hash map. By storing the earliest occurrence of each prefix sum, we can instantly check if a previous sum allows us to form a subarray summing to k. This approach reduces the time complexity from O(n²) to O(n), making it suitable for large arrays. The key insight is recognizing that the difference between two prefix sums gives the sum of the subarray between them.

Code Implementation

class Solution:
    def maxSubArrayLen(self, nums, k):
        prefix_sum_indices = {}
        current_sum = 0
        max_length = 0
        for i, num in enumerate(nums):
            current_sum += num
            if current_sum == k:
                max_length = i + 1
            if (current_sum - k) in prefix_sum_indices:
                max_length = max(max_length, i - prefix_sum_indices[current_sum - k])
            if current_sum not in prefix_sum_indices:
                prefix_sum_indices[current_sum] = i
        return max_length
    

class Solution {
public:
    int maxSubArrayLen(vector<int>& nums, int k) {
        unordered_map<int, int> prefix_sum_indices;
        int current_sum = 0, max_length = 0;
        for (int i = 0; i < nums.size(); ++i) {
            current_sum += nums[i];
            if (current_sum == k) {
                max_length = i + 1;
            }
            if (prefix_sum_indices.find(current_sum - k) != prefix_sum_indices.end()) {
                max_length = max(max_length, i - prefix_sum_indices[current_sum - k]);
            }
            if (prefix_sum_indices.find(current_sum) == prefix_sum_indices.end()) {
                prefix_sum_indices[current_sum] = i;
            }
        }
        return max_length;
    }
};
    

class Solution {
    public int maxSubArrayLen(int[] nums, int k) {
        Map<Integer, Integer> prefixSumIndices = new HashMap<>();
        int currentSum = 0, maxLength = 0;
        for (int i = 0; i < nums.length; i++) {
            currentSum += nums[i];
            if (currentSum == k) {
                maxLength = i + 1;
            }
            if (prefixSumIndices.containsKey(currentSum - k)) {
                maxLength = Math.max(maxLength, i - prefixSumIndices.get(currentSum - k));
            }
            if (!prefixSumIndices.containsKey(currentSum)) {
                prefixSumIndices.put(currentSum, i);
            }
        }
        return maxLength;
    }
}
    

var maxSubArrayLen = function(nums, k) {
    let prefixSumIndices = new Map();
    let currentSum = 0, maxLength = 0;
    for (let i = 0; i < nums.length; i++) {
        currentSum += nums[i];
        if (currentSum === k) {
            maxLength = i + 1;
        }
        if (prefixSumIndices.has(currentSum - k)) {
            maxLength = Math.max(maxLength, i - prefixSumIndices.get(currentSum - k));
        }
        if (!prefixSumIndices.has(currentSum)) {
            prefixSumIndices.set(currentSum, i);
        }
    }
    return maxLength;
};