Skip to main content
Code ScholarsCodeScholars

Arrays, Strings, and Pattern Techniques · Pattern Techniques

Prefix Sums

Prefix sums precompute running totals so range-sum questions can be answered quickly after one setup pass.

Enroll NowText UsContact Code ScholarsFull DSA Course

Student Focus

This topic is a strong bridge from AP arrays to contest-style efficiency.

Guided Lesson Notes

Understanding Prefix Sums

Prefix Sums focuses on contiguous sequences, index movement, and the state that can be reused while scanning. Prefix sums precompute running totals so range-sum questions can be answered quickly after one setup pass.

Model: picture the input as boxes with numbered positions; every algorithm decision should say which positions are being read, updated, skipped, or remembered.

Invariant: the variables beside the array must summarize exactly the part of the array that has already been processed.

Implementation: careful loops, boundary checks, and small helper variables for sums, counts, positions, or best answers.

Use Prefix Sums when the problem asks about a subarray, substring, range, pair, frequency, or a condition over consecutive values.

Visual Model

A small picture for Prefix Sums

i=0

4

i=1

1

i=2

7

i=3

2

i=4

5

i=5

9

i=6

3

i=7

6

Array and string techniques usually become clear when each index has a job: scan, compare, count, enter a range, leave a range, or store a best answer.

Key Ideas

  • Running totals
  • Range query formulas
  • Preprocessing tradeoffs

Practice Prompts

  • Build a prefix array and answer several range sum queries.
  • Extend prefix sums to count categories or compare intervals.

Vocabulary

Terms students should be able to say clearly

Index

The numeric position used to access an item directly.

Window

A contiguous section of the array or string currently being considered.

Prefix

Information accumulated from the start of the sequence up to a position.

Boundary

The first or last valid position included in the current scan.

State

The running information kept while the loop moves.

Invariant

The rule that makes the running state trustworthy after each iteration.

Worked Example

Worked example: tracing Prefix Sums

Trace a small input, focusing on running totals.

  1. 1Write a small input where Prefix Sums is clearly useful.
  2. 2Label the part of the input related to Running totals.
  3. 3Perform one operation and explain which invariant is still true afterward.
  4. 4Run a second operation that touches an edge case, such as an empty side, duplicate value, boundary index, disconnected vertex, or tie.
  5. 5Finish by saying which operation dominates the runtime and why.

Complexity Check

Costs students should be able to explain

OperationTypical CostReason
Indexed accessO(1)Direct index lookup is fast when the position is known.
Full scanO(n)Most search, count, and validation tasks inspect each item once.
Middle insert/deleteO(n)Items often need to shift to keep order.

Common Mistakes

What to watch while practicing

  • Coding before drawing the structure or state changes.
  • Forgetting the invariant that makes the algorithm correct.
  • Testing only the sample input and skipping boundary cases.
  • Giving Big-O without explaining which operation dominates the work.

Interview-Style Coding Problem

Prefix Sums interview problem: Count Subarrays With Target Sum

Interview medium

Problem

Given an array that may contain negative numbers, count how many contiguous subarrays have sum exactly k.

Input

The first line contains n and k. The second line contains n integers.

Output

Print the number of subarrays whose sum is k.

Sample Input

6 3
1 2 3 -2 2 1

Sample Output

5

Why the sample works

The target sum appears in five different contiguous ranges, including [1, 2], [3], and [2, 1].

Approach

  1. 1Let prefix be the sum of all values seen so far.
  2. 2A previous prefix equal to prefix - k marks a subarray ending here with sum k.
  3. 3Store how many times each prefix sum has appeared.
  4. 4Seed the map with prefix sum 0 so subarrays starting at index 0 are counted.

O(n) time and O(n) extra space.

Java Solution

import java.util.*;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    long k = sc.nextLong();

    Map<Long, Long> seen = new HashMap<>();
    seen.put(0L, 1L);

    long prefix = 0;
    long answer = 0;

    for (int i = 0; i < n; i++) {
      prefix += sc.nextLong();
      answer += seen.getOrDefault(prefix - k, 0L);
      seen.put(prefix, seen.getOrDefault(prefix, 0L) + 1);
    }

    System.out.println(answer);
  }
}

Python Solution

from collections import defaultdict

n, k = map(int, input().split())
a = list(map(int, input().split()))

seen = defaultdict(int)
seen[0] = 1
prefix = 0
answer = 0

for x in a:
    prefix += x
    answer += seen[prefix - k]
    seen[prefix] += 1

print(answer)

Practice Challenge

Make the idea your own

Create a two-minute explanation of Prefix Sums: define it, trace one example, name one edge case, and give the runtime of the main operation.

Tutoring Connection

Need help with this topic?

Bring a question or code attempt to a tutoring session.

Reserve a Free SessionText UsOpen Online Compiler