Subarray Sum Patterns: Prefix Sum, Kadane, and Sliding Window

Subarray sum problems are among the most frequently asked interview questions. They appear simple — “find a contiguous subarray with some sum property” — but the efficient solutions require knowing the right technique. This post covers the three pillars: prefix sums, Kadane’s algorithm, and sliding window.

---

1. Prefix Sum — The Foundation

The prefix sum (or cumulative sum) of an array arr is a new array where prefix[i] = arr[0] + arr[1] + ... + arr[i-1]. With prefix sums, you can compute the sum of any subarray in O(1).

def build_prefix_sum(arr):
    """
    Build a prefix sum array.

    prefix[0] = 0 (sum of zero elements)
    prefix[i] = arr[0] + arr[1] + ... + arr[i-1]

    Time: O(n), Space: O(n)
    """
    n = len(arr)
    prefix = [0] * (n + 1)

    for i in range(n):
        prefix[i + 1] = prefix[i] + arr[i]

    return prefix


def range_sum(prefix, left, right):
    """
    Sum of arr[left..right] (inclusive) in O(1).

    sum(arr[left..right]) = prefix[right+1] - prefix[left]
    """
    return prefix[right + 1] - prefix[left]


arr = [3, 1, -2, 5, 4, -1, 2, 1]
prefix = build_prefix_sum(arr)
print(f"Prefix array: {prefix}")
# [0, 3, 4, 2, 7, 11, 10, 12, 13]

print(f"Sum of arr[2..4] = {range_sum(prefix, 2, 4)}")  # -2+5+4 = 7
print(f"Sum of arr[0..7] = {range_sum(prefix, 0, 7)}")  # 13
print(f"Sum of arr[5..6] = {range_sum(prefix, 5, 6)}")  # -1+2 = 1

---

2. 2D Prefix Sum

For matrices, extend prefix sums to 2D for O(1) submatrix sum queries.

def build_2d_prefix(matrix):
    """
    Build a 2D prefix sum matrix.

    prefix[i][j] = sum of all elements in matrix[0..i-1][0..j-1]

    Time: O(mn), Space: O(mn)
    """
    m, n = len(matrix), len(matrix[0])
    prefix = [[0] * (n + 1) for _ in range(m + 1)]

    for i in range(1, m + 1):
        for j in range(1, n + 1):
            prefix[i][j] = (
                matrix[i - 1][j - 1]
                + prefix[i - 1][j]
                + prefix[i][j - 1]
                - prefix[i - 1][j - 1]
            )

    return prefix


def submatrix_sum(prefix, r1, c1, r2, c2):
    """
    Sum of matrix[r1..r2][c1..c2] (inclusive) in O(1).
    Uses inclusion-exclusion.
    """
    return (
        prefix[r2 + 1][c2 + 1]
        - prefix[r1][c2 + 1]
        - prefix[r2 + 1][c1]
        + prefix[r1][c1]
    )


matrix = [
    [1, 2, 3],
    [4, 5, 6],
    [7, 8, 9],
]
prefix = build_2d_prefix(matrix)
print(submatrix_sum(prefix, 0, 0, 1, 1))  # 1+2+4+5 = 12
print(submatrix_sum(prefix, 1, 1, 2, 2))  # 5+6+8+9 = 28

---

3. Subarray Sum Equals K

Problem: count the number of contiguous subarrays with sum equal to k.

Key insight: if prefix[j] - prefix[i] == k, then sum(arr[i..j-1]) == k. So we need to count how many previous prefix values equal prefix[j] - k.

from collections import defaultdict

def subarray_sum_equals_k(nums, k):
    """
    LeetCode 560: Subarray Sum Equals K.

    Use prefix sum + hash map.

    Time: O(n), Space: O(n)
    """
    count = 0
    prefix = 0
    prefix_count = defaultdict(int)
    prefix_count[0] = 1  # empty prefix has sum 0

    for num in nums:
        prefix += num

        # How many previous prefixes have value (prefix - k)?
        # Each such prefix marks the start of a subarray summing to k
        count += prefix_count[prefix - k]

        prefix_count[prefix] += 1

    return count


print(subarray_sum_equals_k([1, 1, 1], 2))      # 2 ([1,1] at indices 0-1 and 1-2)
print(subarray_sum_equals_k([1, 2, 3], 3))       # 2 ([1,2] and [3])
print(subarray_sum_equals_k([1, -1, 0], 0))      # 3 ([1,-1], [-1,0], [1,-1,0])

Why Not Sliding Window?

Sliding window works only when all elements are positive (or when you need a contiguous window of fixed/variable size with monotonic behavior). With negative numbers, shrinking the window can increase the sum, breaking the sliding window invariant.

---

4. Kadane’s Algorithm — Maximum Subarray

Problem: find the contiguous subarray with the largest sum.

def max_subarray(nums):
    """
    LeetCode 53: Maximum Subarray (Kadane's Algorithm).

    At each position, decide: start a new subarray here,
    or extend the previous one.

    Time: O(n), Space: O(1)
    """
    max_sum = nums[0]
    current_sum = nums[0]

    for i in range(1, len(nums)):
        # Either start fresh at nums[i] or extend previous subarray
        current_sum = max(nums[i], current_sum + nums[i])
        max_sum = max(max_sum, current_sum)

    return max_sum


print(max_subarray([-2, 1, -3, 4, -1, 2, 1, -5, 4]))
# 6 (subarray [4, -1, 2, 1])

print(max_subarray([1]))           # 1
print(max_subarray([5, 4, -1, 7, 8]))  # 23 (entire array)

Finding the Subarray Itself

def max_subarray_with_indices(nums):
    """Return the maximum subarray sum and its start/end indices."""
    max_sum = nums[0]
    current_sum = nums[0]
    start = end = 0
    temp_start = 0

    for i in range(1, len(nums)):
        if nums[i] > current_sum + nums[i]:
            current_sum = nums[i]
            temp_start = i
        else:
            current_sum += nums[i]

        if current_sum > max_sum:
            max_sum = current_sum
            start = temp_start
            end = i

    return max_sum, start, end


nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
total, s, e = max_subarray_with_indices(nums)
print(f"Max sum: {total}, subarray: {nums[s:e+1]}")
# Max sum: 6, subarray: [4, -1, 2, 1]

Kadane’s for Minimum Subarray

def min_subarray(nums):
    """Find the contiguous subarray with the smallest sum."""
    min_sum = nums[0]
    current_sum = nums[0]

    for i in range(1, len(nums)):
        current_sum = min(nums[i], current_sum + nums[i])
        min_sum = min(min_sum, current_sum)

    return min_sum


print(min_subarray([3, -4, 2, -3, -1, 7, -5]))
# -6 (subarray [-4, 2, -3, -1])

---

5. Maximum Subarray Sum with Circular Array

Problem: the array is circular — the subarray can wrap around.

def max_subarray_circular(nums):
    """
    LeetCode 918: Maximum Sum Circular Subarray.

    Two cases:
    1. Max subarray does NOT wrap — use Kadane's
    2. Max subarray WRAPS — total_sum - min_subarray

    Take the max of both cases.

    Edge case: if all elements are negative, min_subarray = total,
    so case 2 gives 0. Return case 1 (the least negative element).

    Time: O(n), Space: O(1)
    """
    total_sum = sum(nums)

    # Case 1: normal Kadane's
    max_kadane = nums[0]
    curr_max = nums[0]
    for i in range(1, len(nums)):
        curr_max = max(nums[i], curr_max + nums[i])
        max_kadane = max(max_kadane, curr_max)

    # Case 2: wrapping = total - min subarray
    min_kadane = nums[0]
    curr_min = nums[0]
    for i in range(1, len(nums)):
        curr_min = min(nums[i], curr_min + nums[i])
        min_kadane = min(min_kadane, curr_min)

    # If all negative, min_kadane == total_sum, and wrapping gives 0
    if total_sum == min_kadane:
        return max_kadane

    return max(max_kadane, total_sum - min_kadane)


print(max_subarray_circular([1, -2, 3, -2]))     # 3
print(max_subarray_circular([5, -3, 5]))          # 10 (wraps: [5, 5])
print(max_subarray_circular([-3, -2, -3]))        # -2 (all negative)

---

6. Maximum Product Subarray

Problem: find the contiguous subarray with the largest product. Negatives make this tricky — multiplying two negatives gives a positive.

def max_product(nums):
    """
    LeetCode 152: Maximum Product Subarray.

    Track both max and min products ending at each position.
    A negative number can flip min to max.

    Time: O(n), Space: O(1)
    """
    result = nums[0]
    curr_max = nums[0]
    curr_min = nums[0]

    for i in range(1, len(nums)):
        # If nums[i] is negative, max and min swap
        if nums[i] < 0:
            curr_max, curr_min = curr_min, curr_max

        curr_max = max(nums[i], curr_max * nums[i])
        curr_min = min(nums[i], curr_min * nums[i])

        result = max(result, curr_max)

    return result


print(max_product([2, 3, -2, 4]))     # 6 ([2, 3])
print(max_product([-2, 0, -1]))       # 0
print(max_product([-2, 3, -4]))       # 24 ([-2, 3, -4])
print(max_product([2, -5, -2, -4, 3])) # 24 ([-2, -4, 3]? No: [-5,-2,-4,3]=120? Let's check: -5*-2=10, 10*-4=-40, -40*3=-120. Actually [2,-5,-2,-4] = 2*-5*-2*-4 = -80. Hmm, [-2,-4,3]=24.)

---

7. Minimum Size Subarray Sum (Sliding Window)

Problem: find the minimal length subarray whose sum is > k. All elements are positive.

def min_subarray_len(target, nums):
    """
    LeetCode 209: Minimum Size Subarray Sum.

    Sliding window — works because all elements are positive.

    Time: O(n), Space: O(1)
    """
    n = len(nums)
    min_len = float('inf')
    window_sum = 0
    left = 0

    for right in range(n):
        window_sum += nums[right]

        while window_sum >= target:
            min_len = min(min_len, right - left + 1)
            window_sum -= nums[left]
            left += 1

    return min_len if min_len != float('inf') else 0


print(min_subarray_len(7, [2, 3, 1, 2, 4, 3]))  # 2 ([4, 3])
print(min_subarray_len(4, [1, 4, 4]))             # 1 ([4])
print(min_subarray_len(11, [1, 1, 1, 1, 1, 1]))  # 0 (impossible)

---

8. Subarray Sum Divisible by K

def subarrays_div_by_k(nums, k):
    """
    LeetCode 974: Subarray Sums Divisible by K.

    If prefix[j] % k == prefix[i] % k, then sum(arr[i..j-1]) is divisible by k.

    Time: O(n), Space: O(k)
    """
    count = 0
    prefix_mod = 0
    mod_count = defaultdict(int)
    mod_count[0] = 1

    for num in nums:
        prefix_mod = (prefix_mod + num) % k
        count += mod_count[prefix_mod]
        mod_count[prefix_mod] += 1

    return count


print(subarrays_div_by_k([4, 5, 0, -2, -3, 1], 5))  # 7
print(subarrays_div_by_k([5], 9))                     # 0

---

9. Longest Subarray with Sum at Most K

def longest_subarray_sum_at_most_k(nums, k):
    """
    Find the longest subarray with sum <= k.
    Works for non-negative elements (sliding window).

    Time: O(n), Space: O(1)
    """
    n = len(nums)
    max_len = 0
    window_sum = 0
    left = 0

    for right in range(n):
        window_sum += nums[right]

        while window_sum > k and left <= right:
            window_sum -= nums[left]
            left += 1

        max_len = max(max_len, right - left + 1)

    return max_len


print(longest_subarray_sum_at_most_k([1, 2, 1, 0, 1, 1, 0], 4))
# 5 (subarray [1, 0, 1, 1, 0] or [2, 1, 0, 1] etc.)

---

10. Prefix XOR — Subarray XOR Queries

Prefix sums work with any associative operation. XOR is a common variant.

def subarray_xor_equals_k(nums, k):
    """
    Count subarrays with XOR equal to k.

    prefix_xor[j] ^ prefix_xor[i] == k means subarray[i..j-1] has XOR = k.
    Equivalent to prefix_xor[i] == prefix_xor[j] ^ k.

    Time: O(n), Space: O(n)
    """
    count = 0
    prefix_xor = 0
    xor_count = defaultdict(int)
    xor_count[0] = 1

    for num in nums:
        prefix_xor ^= num
        count += xor_count[prefix_xor ^ k]
        xor_count[prefix_xor] += 1

    return count


print(subarray_xor_equals_k([4, 2, 2, 6, 4], 6))  # 4
print(subarray_xor_equals_k([5, 6, 7, 8, 9], 5))   # 2

---

11. Decision Guide — Which Technique to Use

Condition	Technique	Time
Range sum queries (offline)	Prefix sum	O(1) per query
Maximum/minimum subarray sum	Kadane’s	O(n)
Count subarrays with sum = K	Prefix sum + hash map	O(n)
Minimum length subarray > K (positive)	Sliding window	O(n)
Maximum length subarray <= K (positive)	Sliding window	O(n)
Subarray sum divisible by K	Prefix sum mod + hash map	O(n)
Maximum product subarray	Track max and min	O(n)
2D range sum queries	2D prefix sum	O(1) per query

Quick Decision Flowchart

1. All positive numbers? Try sliding window first.
2. Need exact count with target sum? Prefix sum + hash map.
3. Need maximum/minimum sum? Kadane’s algorithm.
4. Multiple range queries? Build prefix sum array upfront.
5. Has negatives + need window? Prefix sum + hash map (not sliding window).

---

12. Advanced: Difference Array

The difference array is the inverse of prefix sum. It allows O(1) range updates.

def range_update_example():
    """
    Apply multiple range updates, then compute final array.

    Update: add val to arr[l..r]
    Using difference array: O(1) per update, O(n) to reconstruct.
    """
    n = 5
    diff = [0] * (n + 1)

    def add_range(l, r, val):
        diff[l] += val
        diff[r + 1] -= val

    # Add 3 to arr[1..3]
    add_range(1, 3, 3)
    # Add 5 to arr[2..4]
    add_range(2, 4, 5)

    # Reconstruct with prefix sum
    result = [0] * n
    result[0] = diff[0]
    for i in range(1, n):
        result[i] = result[i - 1] + diff[i]

    print(result)  # [0, 3, 8, 8, 5]
    # arr[1..3] += 3 -> [0, 3, 3, 3, 0]
    # arr[2..4] += 5 -> [0, 3, 8, 8, 5]


range_update_example()

---

13. Practice Problems

Problem	Platform	Key Technique
Maximum Subarray (LC 53)	LeetCode	Kadane’s
Subarray Sum Equals K (LC 560)	LeetCode	Prefix + hash map
Minimum Size Subarray Sum (LC 209)	LeetCode	Sliding window
Maximum Product Subarray (LC 152)	LeetCode	Track max/min
Maximum Sum Circular Subarray (LC 918)	LeetCode	Kadane’s + wrapping
Subarray Sums Divisible by K (LC 974)	LeetCode	Prefix mod + hash map
Range Sum Query (LC 303)	LeetCode	Prefix sum
Range Sum Query 2D (LC 304)	LeetCode	2D prefix sum
Contiguous Array (LC 525)	LeetCode	Prefix sum (0/1)
Product of Array Except Self (LC 238)	LeetCode	Prefix/suffix products

---

Big-O Summary

Algorithm	Time	Space
Build prefix sum	O(n)	O(n)
Range sum query	O(1)	O(1)
2D prefix sum build	O(mn)	O(mn)
2D range query	O(1)	O(1)
Kadane’s (max subarray)	O(n)	O(1)
Prefix + hash map (count)	O(n)	O(n)
Sliding window	O(n)	O(1)
Max product subarray	O(n)	O(1)
Difference array update	O(1) per update	O(n)

Subarray sum problems are the bread and butter of array-based interviews. The three core techniques — prefix sum, Kadane’s, and sliding window — each handle different constraints. Know when to reach for each one, and these problems become mechanical.