AI InterviewSearch…Search problems, topics, or pages…Ctrl KGet started

Topic

Prefix Sum coding problems

A prefix-sum array stores the running total, so the sum of any range is one subtraction.

New to prefix sum? Read the Prefix Sum tutorial first.

137 problems · 19 easy · 85 medium · 33 hard · judged by hidden tests in 13 languages

137problems

19 easy

85 medium

33 hard

Sign in to tick off what you solve.

Study plan: 14 problems · about 8 h 10 min

Start the study plan

Next up: Running Sum of 1d Array

How it works

Prefix Sum, step by step

Range sums in O(1), with a prefix-sum array

nums = [2, 4, 1, 3, 5, 2]; query: sum of nums[1..4]

nums204112335425prefix00123456prefix[0] = 0

prefix[k] will hold the sum of the first k numbers, so the row is one longer than nums and starts with prefix[0] = 0, the empty sum. Each entry sits under the boundary where its numbers end.

0:01 / 0:27Step 1 of 9
Transcript · 9 steps

Study plan

Learn prefix sum in 8 days

14 of the 137 Prefix Sum problems (4 easy, 7 medium and 3 hard) over 8 days, about 8 h 10 min in all — the pattern first, then easiest to hardest. After that, the other 123 in the full list below are practice at your own pace. Then move on to Sorting.

  1. Day 1

    about 1 h 15 min

    Learn the pattern: read the essentials and step through the walkthrough above, then solve these 3.

  2. Day 2

    about 55 min

    Medium problems: the same pattern with one twist each. Name the twist before you code.

  3. Day 3

    about 1 h 10 min

    More mediums. Before coding each one, write down what state the pattern keeps and when it changes.

  4. Day 4

    about 1 h 10 min

    More mediums. Before coding each one, write down what state the pattern keeps and when it changes.

  5. Day 5

    about 1 h 10 min

    More mediums. Before coding each one, write down what state the pattern keeps and when it changes.

  6. Day 6

    about 50 min

    Hard problems: the pattern combined with a second idea. Give each a full attempt before reading the editorial.

  7. Day 7

    about 50 min

    Another hard one. If it beats you after a real attempt, read the editorial, then solve it again tomorrow from memory.

  8. Day 8

    about 50 min

    Another hard one. If it beats you after a real attempt, read the editorial, then solve it again tomorrow from memory.

    Next topic: Sorting

Prefix Sum Coding Problems: 137 Questions with Solutions

137 prefix sum coding problems — 19 easy · 85 medium · 33 hard — with solutions in 13 languages. Plus a step-by-step walkthrough and a 8-day plan.

  • Problems: 137
  • By difficulty: 19 easy · 85 medium · 33 hard
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
  • Cost: Free on every plan; sign in to run and submit

A prefix-sum array stores the running total, so the sum of any range is one subtraction. Range-sum queries, subarrays with a target sum (with a hash map of prefixes seen), balanced pivots and two-dimensional grid sums all rest on it; the problems here practise building the prefix once and reading it many times.

New to prefix sum? Read the Prefix Sum tutorial first.

How prefix sum works, step by step

nums204112335425prefix[5] = 15prefix[1] = 2prefix00216273104155176sum(1..4) = 15 − 2 = 13
Range sums in O(1), with a prefix-sum array. Example: nums = [2, 4, 1, 3, 5, 2]; query: sum of nums[1..4]
  1. prefix[k] will hold the sum of the first k numbers, so the row is one longer than nums and starts with prefix[0] = 0, the empty sum. Each entry sits under the boundary where its numbers end.
  2. prefix[1] = prefix[0] + nums[0] = 0 + 2 = 2. Each entry is the one before it plus one more number, so no stretch is ever added up twice.
  3. prefix[2] = prefix[1] + nums[1] = 2 + 4 = 6, the same as 2 + 4 without adding those again.
  4. prefix[3] = prefix[2] + nums[2] = 6 + 1 = 7, the same as 2 + 4 + 1 without adding those again.
  5. prefix[4] = prefix[3] + nums[3] = 7 + 3 = 10, the same as 2 + 4 + 1 + 3 without adding those again.
  6. prefix[5] = prefix[4] + nums[4] = 10 + 5 = 15, the same as 2 + 4 + 1 + 3 + 5 without adding those again.
  7. prefix[6] = prefix[5] + nums[5] = 15 + 2 = 17, the total of all 6 numbers. The whole row took 6 additions: O(n), paid once.
  8. Now the sum of nums[1..4]. prefix[5] covers indices 0 to 4 and prefix[1] covers index 0 alone, so taking one from the other leaves exactly indices 1 to 4.
  9. 15 − 2 = 13, the same as 4 + 1 + 3 + 5. Any range now costs one subtraction, O(1), after the O(n) build, instead of up to n additions per query.

Prefix Sum study plan

14 of the 137 Prefix Sum problems (4 easy, 7 medium and 3 hard) over 8 days, about 8 h 10 min in all — the pattern first, then easiest to hardest. After that, the other 123 in the full list below are practice at your own pace. Then move on to Sorting.

Day 1

Learn the pattern: read the essentials and step through the walkthrough above, then solve these 3.

Day 2

Medium problems: the same pattern with one twist each. Name the twist before you code.

Day 3

More mediums. Before coding each one, write down what state the pattern keeps and when it changes.

Day 4

More mediums. Before coding each one, write down what state the pattern keeps and when it changes.

Day 5

More mediums. Before coding each one, write down what state the pattern keeps and when it changes.

Day 6

Hard problems: the pattern combined with a second idea. Give each a full attempt before reading the editorial.

Day 7

Another hard one. If it beats you after a real attempt, read the editorial, then solve it again tomorrow from memory.

Day 8

Another hard one. If it beats you after a real attempt, read the editorial, then solve it again tomorrow from memory.

Next topic: Sorting

Prefix Sum: the essentials

When to reach for it

Many sum queries over ranges of an array that does not change; "subarrays whose sum equals, or is divisible by, k" when values can be negative, which breaks a Sliding Window; "the index where the left and right sums balance"; many range updates applied at once, which is the difference array, the prefix sum run backwards.

The pattern

Define pre[0] = 0 and pre[i + 1] = pre[i] + nums[i]; the sum of nums[l..r] is then pre[r + 1] - pre[l]. To count subarrays that sum to k in one pass, keep a map from each prefix total to how often it has occurred: a subarray ending at the current index sums to k exactly when an earlier prefix equals the current total minus k.

def subarray_sum(nums, k):
    seen = {0: 1}                   # the empty prefix
    total = count = 0
    for x in nums:
        total += x
        count += seen.get(total - k, 0)
        seen[total] = seen.get(total, 0) + 1
    return count

Cost

O(n) to build and O(1) per range query. The two-dimensional table costs O(m × n) to build and answers the sum of any rectangle with four lookups.

Common mistakes

  • Leaving out the empty prefix ({0: 1}), which misses every subarray that starts at index 0.
  • An off-by-one between pre[r] - pre[l] and pre[r + 1] - pre[l]; settle the convention once and keep it.
  • Recording the current total before looking it up, which counts the empty subarray when k is 0.
  • Overflow: 10⁵ values up to 10⁹ sum to 10¹⁴, which needs 64-bit integers.

Start with

All prefix sum problems

Easy (19)

Medium (85)

Hard (33)

Companies that ask prefix sum problems

  • Amazon 129 problems on prefix sum
  • Google 109 problems on prefix sum
  • Meta 17 problems on prefix sum
  • Microsoft 15 problems on prefix sum
  • Uber 10 problems on prefix sum
  • Adobe 8 problems on prefix sum
  • TCS 6 problems on prefix sum
  • Sprinklr 4 problems on prefix sum
  • Zoho 3 problems on prefix sum
  • Arcesium 2 problems on prefix sum
  • Capgemini 2 problems on prefix sum
  • Directi 2 problems on prefix sum

Next topic: Sorting