Top 14 Prefix Sum LeetCode Problems to Master for Coding Interviews

One formula. Fourteen disguises.

prefix[r+1] - prefix[l] is the whole thing. The disguises are hashmap keys, modular remainders, 2D rectangles, and monotonic deques. Each one will look like a completely different problem until you've seen the pattern enough times that it stops fooling you. Work through these 14 prefix sum LeetCode problems in order and each one loads the mental model you need for the next.

The Only Formula You Actually Need

# Build (1-indexed, prefix[0] = 0 sentinel)
prefix = [0] * (len(nums) + 1)
for i, n in enumerate(nums):
    prefix[i+1] = prefix[i] + n

# Query: sum of nums[l..r] inclusive
range_sum = prefix[r+1] - prefix[l]

That sentinel zero is not optional. It eliminates every off-by-one check in every problem below. Write this structure until you can produce it asleep.

You. After forgetting the sentinel zero. Again.

Start Here or You'll Regret It

1. Running Sum of 1D Array (LC 1480, Easy)

Build the prefix array in-place and return it. This problem exists so you drill the index convention until it takes zero thought. Do not skip it because it looks too easy. Everything downstream breaks if you're fuzzy on which index maps to which.

def runningSum(nums: list[int]) -> list[int]:
    for i in range(1, len(nums)):
        nums[i] += nums[i-1]
    return nums

2. Range Sum Query - Immutable (LC 303, Easy)

Precompute in __init__, answer in O(1). The prepended zero sentinel means your query is always pre[r+1] - pre[l] with no special cases, ever. This is the pattern you'll paste into every subsequent problem.

class NumArray:
    def __init__(self, nums: list[int]):
        self.pre = [0] * (len(nums) + 1)
        for i, n in enumerate(nums):
            self.pre[i+1] = self.pre[i] + n

    def sumRange(self, l: int, r: int) -> int:
        return self.pre[r+1] - self.pre[l]

Every subsequent problem uses this class structure. Learn it once here so you don't have to think about it again.

3. Find Pivot Index (LC 724, Easy)

The pivot is where left sum equals right sum. You do not need to compute the right sum explicitly: left_sum * 2 + nums[i] == total is a one-pass check that avoids recomputing anything.

def pivotIndex(nums: list[int]) -> int:
    total, left = sum(nums), 0
    for i, n in enumerate(nums):
        if left * 2 + n == total:
            return i
        left += n
    return -1

Balance conditions expressed as prefix constraints appear in at least a dozen medium problems. This is your first taste.

Two More Before Things Get Spicy

4. Find the Highest Altitude (LC 1732, Easy)

The input is a gain array (differences between altitudes). You want the maximum prefix sum of that gain array. Prefix sums work on derived arrays, not just original values. This is the first hint toward the difference array technique.

def largestAltitude(gain: list[int]) -> int:
    altitude = max_alt = 0
    for g in gain:
        altitude += g
        max_alt = max(max_alt, altitude)
    return max_alt

5. Product of Array Except Self (LC 238, Medium)

No division allowed. Build a left-product prefix in the first pass, then multiply by a right-product suffix in the second. Two passes on two prefix arrays is the exact structure of the 1D prefix sum, just with multiplication instead of addition. Same skeleton, different operator.

def productExceptSelf(nums: list[int]) -> list[int]:
    n = len(nums)
    result = [1] * n
    left = 1
    for i in range(n):
        result[i] = left
        left *= nums[i]
    right = 1
    for i in range(n - 1, -1, -1):
        result[i] *= right
        right *= nums[i]
    return result

This two-pass prefix-and-suffix structure also solves LC 42 (Trapping Rain Water) and LC 135 (Candy).

The Problems That Look Different But Aren't

This is where most interview problems live, and where most people hit a wall. The idea: for each current prefix sum s, check in O(1) whether s - k has been seen before. If it has, the subarray between that earlier index and this one sums to exactly k. Everything in this section is a variation on that one lookup.

Always seed the hashmap with {0: 1} for count problems and {0: -1} for length problems. The zero represents the empty prefix before the array starts. If you forget this, your code will silently miss subarrays that start at index 0, pass most test cases, and fail on the one that matters.

6. Subarray Sum Equals K (LC 560, Medium)

This is the canonical problem. Count subarrays with sum exactly k. For each prefix sum s, add however many earlier prefix sums equal s - k. Every other problem in this section is a disguised version of this one.

def subarraySum(nums: list[int], k: int) -> int:
    count, s = 0, 0
    freq = {0: 1}
    for n in nums:
        s += n
        count += freq.get(s - k, 0)
        freq[s] = freq.get(s, 0) + 1
    return count

The hashmap stores prefix sum frequencies. See also /blog/hash-map-time-complexity for why this lookup is O(1).

7. Maximum Size Subarray Sum Equals k (LC 325, Medium)

Same pattern, different question: find the longest subarray with sum k. Store only the first occurrence of each prefix sum. Using first occurrence maximizes subarray length, while LC 560 counts every occurrence. One character difference in the logic, completely different semantics.

def maxSubArrayLen(nums: list[int], k: int) -> int:
    first = {0: -1}
    s = best = 0
    for i, n in enumerate(nums):
        s += n
        if s - k in first:
            best = max(best, i - first[s - k])
        if s not in first:
            first[s] = i
    return best

8. Contiguous Array (LC 525, Medium)

Find the longest subarray with equal 0s and 1s. The trick: replace every 0 with -1. Now you want the longest subarray with prefix sum zero. A prefix sum appearing for the second time marks the end of a zero-sum subarray. The code is LC 325 with k = 0, in a costume.

def findMaxLength(nums: list[int]) -> int:
    first = {0: -1}
    s = best = 0
    for i, n in enumerate(nums):
        s += 1 if n else -1
        if s in first:
            best = max(best, i - first[s])
        else:
            first[s] = i
    return best

9. Continuous Subarray Sum (LC 523, Medium)

Check whether any subarray of length at least 2 has sum divisible by k. Two prefix sums that share the same remainder mod k enclose a subarray whose sum is divisible by k. Store the first index of each remainder.

def checkSubarraySum(nums: list[int], k: int) -> bool:
    seen = {0: -1}
    s = 0
    for i, n in enumerate(nums):
        s = (s + n) % k
        if s in seen:
            if i - seen[s] >= 2:
                return True
        else:
            seen[s] = i
    return False

The >= 2 guard rules out single elements. It trips up almost everyone the first time.

10. Subarray Sums Divisible by K (LC 974, Medium)

Count all subarrays with sum divisible by k. Same modular prefix sum as LC 523, but now you want every pair of equal remainders. Add the frequency of the current remainder before storing it, which counts all valid left endpoints at once.

def subarraysDivByK(nums: list[int], k: int) -> int:
    freq = {0: 1}
    s = count = 0
    for n in nums:
        s = (s + n) % k
        if s < 0:
            s += k
        count += freq.get(s, 0)
        freq[s] = freq.get(s, 0) + 1
    return count

In Python, % always returns non-negative values for positive k. In Java and C++, it can return negative remainders, so s = ((s + n) % k + k) % k is the safe version. This is the kind of thing that will cost you ten minutes in an interview if you write it in Python all week and then code in Java on the day.

Same Trick, More Dimensions

11. Range Sum Query 2D - Immutable (LC 304, Medium)

Extend the 1D formula to a matrix. pre[r+1][c+1] stores the rectangle sum from (0,0) to (r, c). The query uses inclusion-exclusion on four corners: add the doubly-excluded corner back after removing both excluded strips.

sum(r1, c1, r2, c2) = pre[r2+1][c2+1]
                    - pre[r1][c2+1]
                    - pre[r2+1][c1]
                    + pre[r1][c1]

Build in O(mn), query in O(1). You need this structure to solve LC 363 below, and it will show up in any system where you need fast rectangle queries on a fixed grid.

12. Count Number of Nice Subarrays (LC 1248, Medium)

Count subarrays with exactly k odd numbers. Replace odd numbers with 1 and even numbers with 0. The problem becomes LC 560. Recognition is the skill, not the code. Prefix sum problems frequently disguise themselves behind string, counting, or parity language. If the problem asks you to count subarrays satisfying some binary property, you're probably looking at this pattern.

def numberOfSubarrays(nums: list[int], k: int) -> int:
    freq = {0: 1}
    s = count = 0
    for n in nums:
        s += n % 2
        count += freq.get(s - k, 0)
        freq[s] = freq.get(s, 0) + 1
    return count

The Problems That Will Humble You

13. Shortest Subarray with Sum at Least K (LC 862, Hard)

Negative values make the sliding window useless. The classic two-pointer approach breaks the moment a number in the array can be negative, which this problem specifically allows. Build the prefix sum array, then maintain a monotonic deque of increasing prefix sums. For each new prefix[i], pop from the front while the difference exceeds k (recording each valid length), then pop from the back while the current prefix sum is smaller than the back of the deque.

from collections import deque

def shortestSubarray(nums: list[int], k: int) -> int:
    n = len(nums)
    pre = [0] * (n + 1)
    for i, x in enumerate(nums):
        pre[i+1] = pre[i] + x
    dq: deque[int] = deque()
    ans = n + 1
    for i in range(n + 1):
        while dq and pre[i] - pre[dq[0]] >= k:
            ans = min(ans, i - dq.popleft())
        while dq and pre[i] <= pre[dq[-1]]:
            dq.pop()
        dq.append(i)
    return ans if ans <= n else -1

The two while loops have distinct jobs. Front pops record answers. Back pops maintain the invariant. These are not interchangeable. See /blog/monotonic-stack for the broader pattern this comes from.

14. Max Sum of Rectangle No Larger Than K (LC 363, Hard)

Fix two row indices, compute column sums between them, then reduce to "max 1D subarray sum no larger than k." For each prefix sum s, you want the smallest stored prefix that is at least s - k. A sorted container gives you that lower-bound query in O(log n), making the total complexity O(m² n log n).

from sortedcontainers import SortedList

def maxSumSubmatrix(matrix: list[list[int]], k: int) -> int:
    m, n = len(matrix), len(matrix[0])
    ans = float('-inf')
    for r1 in range(m):
        col_sum = [0] * n
        for r2 in range(r1, m):
            for c in range(n):
                col_sum[c] += matrix[r2][c]
            sl = SortedList([0])
            s = 0
            for x in col_sum:
                s += x
                idx = sl.bisect_left(s - k)
                if idx < len(sl):
                    ans = max(ans, s - sl[idx])
                sl.add(s)
    return ans

This problem stacks three techniques: 2D-to-1D reduction via column sums, 1D prefix sums, and binary search on a sorted set. If any one of the three layers is unfamiliar, the problem is unsolvable in 45 minutes. Know each layer cold before you try this one.

The Cheat Sheet You'll Screenshot

#	Problem	Difficulty	Core Technique	Key Insight
1	LC 1480 Running Sum	Easy	Basic prefix	Define the building block
2	LC 303 Range Sum Query	Easy	Class + sentinel	O(1) query, no edge cases
3	LC 724 Pivot Index	Easy	Balance formula	left*2 + nums[i] == total
4	LC 1732 Highest Altitude	Easy	Prefix on diffs	Works on derived arrays
5	LC 238 Product Except Self	Medium	Prefix + suffix	Two passes, no division
6	LC 560 Subarray Sum = K	Medium	Prefix + hashmap	Count(pre[i] - k) seen before
7	LC 325 Max Size Subarray	Medium	First occurrence	First seen = maximum length
8	LC 525 Contiguous Array	Medium	Transform 0 to -1	Balanced = prefix sum 0
9	LC 523 Continuous Sum	Medium	Mod k remainder	Equal remainders = valid
10	LC 974 Divisible by K	Medium	Mod frequency	Count every pair
11	LC 304 Range Sum 2D	Medium	2D inclusion-exclusion	Four-corner formula
12	LC 1248 Nice Subarrays	Medium	Abstract transform	Odd parity = 1, then LC 560
13	LC 862 Shortest Subarray	Hard	Prefix + deque	Monotone increasing queue
14	LC 363 Max Sum Rectangle	Hard	2D prefix + sorted set	Fix rows, binary search 1D

How to Actually Drill This List

Do 1 through 5 in a single sitting. They build the convention. Problems 6 through 12 form a block where each adds one idea to the previous, so work through them without large gaps between sessions. Only attempt 13 and 14 after you can solve any of 6 through 12 cold, including explaining why the hashmap is seeded with {0: 1}.

The real interview risk is not getting the code wrong. It is knowing the pattern but being unable to explain why it works while someone watches you. Why does the hashmap seed with {0: 1}? Why does the deque pop from both ends? If you cannot answer those questions out loud under mild pressure, a real interview will expose the gap. SpaceComplexity runs voice-based mock interviews specifically for this kind of reasoning practice, with rubric-based feedback on whether your explanation would actually land with an interviewer.

For the broader technique this pattern fits into, see /blog/prefix-sum-problems for signal recognition and /blog/sliding-window-algorithm for when to choose a window over a prefix approach instead.

Further Reading

• GeeksforGeeks: Top Problems on Prefix Sum Technique
• USACO Guide: Introduction to Prefix Sums
• LeetCode: Prefix Sum Problem List
• Codeforces: Prefix Sum Complete Guide
• Wikipedia: Prefix Sum