Given an integer array nums and an integer k, return the maximum length of a subarray that sums to k. If there is no such subarray, return 0.

A subarray is a contiguous non-empty sequence of elements within an array.

Examples

Example 1:

Input: nums = [1,-1,5,-2,3], k = 3
Output: 4
Explanation: The subarray [1, -1, 5, -2] sums to 3 and is the longest.

Example 2:

Input: nums = [-2,-1,2,1], k = 1
Output: 2
Explanation: The subarray [-1, 2] sums to 1 and is the longest.

Example 3:

Input: nums = [2,0,0,3], k = 3
Output: 3
Explanation: The subarray [0, 0, 3] sums to 3 and is the longest.

Constraints

  • 1 <= nums.length <= 2 * 10^5
  • -10^4 <= nums[i] <= 10^4
  • -10^9 <= k <= 10^9

Thinking Process

  1. Prefix Sum Technique: Convert subarray sum problem to prefix sum difference problem
  • Clarify if the array is sorted, has negatives, or allows duplicates.
  • Prefix sums answer range queries; hash maps answer pair/count queries.
  • In-place tricks use swap/write index instead of extra arrays.
Array + hash map 2 7 11 map hash map for O(1) lookups

Common Approaches

Typical techniques for this pattern:

Approach Time Space Notes
Prefix sum (this problem) O(n) O(n) Range queries, subarray sum
Sort + scan O(n log n) O(1) Intervals, meeting rooms
Kadane’s algorithm O(n) O(1) Maximum subarray
Hash map counting O(n) O(n) Frequency, two-sum variants

Solution

class Solution:
    def maxSubArrayLen(self, nums, k):
        max_len = 0
        
        for i in range(len(nums)):
            s = 0
            
            for j in range(i, len(nums)):
                s += nums[j]
                
                if s == k:
                    max_len = max(max_len, j - i + 1)
        
        return max_len

Solution Explanation

Approach: Prefix sum (this problem)

Key idea: 1. Prefix Sum Technique: Convert subarray sum problem to prefix sum difference problem

How the code works:

  1. Prefix Sum Technique: Convert subarray sum problem to prefix sum difference problem
    • Clarify if the array is sorted, has negatives, or allows duplicates.
    • Prefix sums answer range queries; hash maps answer pair/count queries.
    • In-place tricks use swap/write index instead of extra arrays.

Walkthrough — input nums = [1,-1,5,-2,3], k = 3, expected output 4:

The subarray [1, -1, 5, -2] sums to 3 and is the longest.

Algorithm Breakdown:

  1. Outer Loop: Iterate through all possible starting positions i
  2. Inner Loop: For each starting position, iterate through all ending positions j >= i
  3. Sum Calculation: Accumulate sum from i to j
  4. Check and Update: If sum equals k, update maximum length

Why This Works:

  • Exhaustive Search: Checks all possible subarrays
  • Correctness: Guaranteed to find the maximum length subarray
  • Simple Logic: Straightforward implementation

Solution 1 (Brute-Force):

  • Time Complexity: O(n²) - Two nested loops, each checking O(n) positions
  • Space Complexity: O(1) - Only using a constant amount of extra space

Solution 2 (Prefix Sum with Hash Map):

Common Mistakes

  • Skipping edge cases (empty input, single element, boundaries).
  • Off-by-one errors in loops and index ranges.
  • Forgetting to handle the case when no valid answer exists.

Key Takeaways

  1. Prefix Sum Technique: Convert subarray sum problem to prefix sum difference problem
  2. Hash Map Lookup: Use hash map to find previous prefix sums in O(1) time
  3. First Occurrence: Store only the first occurrence of each prefix sum to maximize subarray length
  4. Direct Match: Check if current prefix sum equals k (subarray from index 0)
  5. Overflow Prevention: Use long long to handle large sums and prevent integer overflow
  6. Edge Cases: Handle cases where prefix sum equals k directly, and cases with zeros in the array

References

Template Reference