1.3 Prefix Sums & Kadane's Subarray Algorithm

1. What Are Prefix Sums & Kadane's Algorithm?

First, let's clarify a word that appears in hundreds of interviews:

• A Subarray is a contiguous (unbroken) slice of an array. For [3, 1, -2, 5], [1, -2, 5] is a subarray, but [3, -2, 5] is not (because it skipped 1).

When problems ask about sums of subarrays, two foundational techniques solve 90% of them:

1. Prefix Sum (P[]): A precomputed array of running totals from index 0 up to each index i.
2. Kadane's Algorithm: A single-pass greedy/DP rule that tracks the best subarray sum ending at the current index.

2. Why Do We Need Them & How Do They Work?

Part A: Why Prefix Sums Exist (O(1) Range Queries)

Suppose someone gives you an array of 100,000 numbers and asks 50,000 questions: "What is the sum from index L to index R?" Looping from L to R for every question takes O(N * Q) time. Instead, build a prefix array P of length N + 1 where P[0] = 0 and P[i + 1] = P[i] + nums[i]. Now, to find the sum from L to R, take the total up to R (P[R + 1]) and subtract the prefix before L (P[L]):

sum(L .. R) = P[R + 1] - P[L]

Part B: Prefix Sum + Hash Map (Subarray Sum Equals K)

What if the problem asks: "How many subarrays add up to k?" and the array has negative numbers? If curr_prefix - old_prefix == k, then old_prefix == curr_prefix - k! So as you walk through the array keeping a running sum curr, store how many times each prefix sum has appeared in a Hash Map (counts = {0: 1}). At each step, counts[curr - k] tells you in O(1) how many valid subarrays end right here!

Part C: Why Kadane's Algorithm Works (Maximum Subarray)

To find the contiguous subarray with the largest sum, ask one question as you stand at x: "Is my previous running sum curr positive or negative?"

• If curr < 0, adding a negative number to x only makes x smaller! Throw curr away and start fresh at x.
• If curr >= 0, keep extending: curr = curr + x.

In one formula: curr = max(x, curr + x).

Step Through the Visual Drawing: Prefix Range Queries & Kadane's Reset

Click Next below to step through both O(1) range subtraction and Kadane's negative-prefix reset rule:

3. Basic Operations & Walkthroughs (All 4 Languages)

# 1. Build 1D Prefix Sum & Query Any Range [L..R] in O(1)
nums = [3, 1, -2, 5, 4]
P = [0] * (len(nums) + 1)
for i, x in enumerate(nums):
  P[i + 1] = P[i] + x

sum_1_to_3 = P[3 + 1] - P[1]  # 7 - 3 = 4

# 2. Prefix Sum + Hash Map (Subarray Sum Equals K)
def subarray_sum(nums: list[int], k: int) -> int:
  counts = {0: 1}  # Base case: empty prefix has sum 0
  curr = ans = 0
  for x in nums:
      curr += x
      ans += counts.get(curr - k, 0)
      counts[curr] = counts.get(curr, 0) + 1
  return ans

# 3. Kadane's Algorithm (Maximum Subarray Sum in O(N) time, O(1) space)
def max_subarray(nums: list[int]) -> int:
  curr = best = nums[0]
  for x in nums[1:]:
      curr = max(x, curr + x)
      best = max(best, curr)
  return best

4. Core Interview Patterns & Common Traps

counts = {0: 1}  # Never forget {0: 1} for subarrays starting at index 0!
curr = ans = 0
for x in nums:
  curr += x
  ans += counts.get(curr - k, 0)
  counts[curr] = counts.get(curr, 0) + 1

5. Practice On Your Own (Curated Submodule Problems)