Running Total (Accumulator)
The running total pattern keeps one variable, called the accumulator, and updates it as you walk through the data once. After each step the accumulator holds the answer for everything seen so far, so you never need to go back and recompute. Interviewers like it because it tests whether you can turn a "look at the whole array" question into a single clean pass, and it is the base for prefix sums, Kadane's algorithm and many counting tricks.
When to use it
- The question asks for a total, product, count, or average over an array or stream.
- You need the answer for every prefix (the first 1 item, the first 2 items, and so on).
- A brute force solution re-adds the same numbers again and again for different ranges.
- You must process data in one pass without storing all of it, such as a stream of numbers.
- The question asks for the number of subarrays or items that satisfy a sum or count condition.
See it work
- Problem: given nums = [3, 1, 4, 2, 5], build the running sum array, where each position holds the sum of everything up to and including it. Start with total = 0 and an empty result.
[3, 1, 4, 2, 5] - Index 0: add 3 to the total. total = 0 + 3 = 3. Save 3 as the first result.
[3, 1, 4, 2, 5] - Index 1: add 1. total = 3 + 1 = 4. The accumulator already remembers the 3, so we do not re-add it.
[3, 1, 4, 2, 5] - Index 2: add 4. total = 4 + 4 = 8. Index 3: add 2. total = 8 + 2 = 10.
[3, 1, 4, 2, 5] - Index 4: add 5. total = 10 + 5 = 15. The loop ends, and result = [3, 4, 8, 10, 15]. One pass, each number touched once.
[3, 1, 4, 2, 5]
Code template
Python
def running_total(nums):
total = 0 # the accumulator (use 1 for products)
result = []
for x in nums:
total += x # fold the current item into the total
result.append(total) # total now covers nums[0..i]
return result
# Variant: count subarrays whose sum is k
def count_subarrays(nums, k):
total, count = 0, 0
seen = {0: 1} # prefix sum -> how many times seen
for x in nums:
total += x
count += seen.get(total - k, 0) # earlier prefix that leaves sum k
seen[total] = seen.get(total, 0) + 1
return countC
// Fills result[] with running sums of nums[0..n-1]
void running_total(const int *nums, int n, int *result) {
int total = 0; // the accumulator (use 1 for products)
for (int i = 0; i < n; i++) {
total += nums[i]; // fold the current item into the total
result[i] = total; // total now covers nums[0..i]
}
}
// Range sum after one pass: sum of nums[l..r] = result[r] - (l ? result[l-1] : 0)
int range_sum(const int *result, int l, int r) {
return result[r] - (l > 0 ? result[l - 1] : 0);
}Java
int[] runningTotal(int[] nums) {
int total = 0; // the accumulator (use 1 for products)
int[] result = new int[nums.length];
for (int i = 0; i < nums.length; i++) {
total += nums[i]; // fold the current item into the total
result[i] = total; // total now covers nums[0..i]
}
return result;
}
// Variant: count subarrays whose sum is k
int countSubarrays(int[] nums, int k) {
int total = 0, count = 0;
Map<Integer, Integer> seen = new HashMap<>();
seen.put(0, 1); // empty prefix
for (int x : nums) {
total += x;
count += seen.getOrDefault(total - k, 0);
seen.merge(total, 1, Integer::sum);
}
return count;
}
Complexity: Time is O(n) because each item is visited once; space is O(1) for a single accumulator, or O(n) if you store every prefix value or use a hash map of prefix sums.
Programs that use it
- Sum of Two Numbers
- Area of a Circle
- Compound Interest
- Celsius to Fahrenheit
- Sum of First n Natural Numbers
- Factorial of a Number
- Fibonacci Series
- Perfect Number
- Power of a Number
- Sum of the Series 1 + 1/2 + … + 1/n
- Count Down with a While Loop
- Pascal’s Triangle
- Sum and Average of an Array
- Count Even and Odd Numbers in an Array
- Count Vowels in a String
Interview problems that use it
- Running Sum of an Array: Keep a total, add each number, and write the total into the output at that position.
- Subarray Sum Equals K: Track the running sum and a map of earlier prefix sums; if total - k was seen before, a subarray ending here sums to k.
- Maximum Subarray (Kadane's Algorithm): Carry the best sum ending at the current item, and reset it to the item itself whenever the carried sum goes negative.
- Product of Array Except Self: Do one pass carrying a product from the left and another from the right, then multiply the two for each position.
- Find Pivot Index: Compute the total once, then carry a left sum; the pivot is where left sum equals total minus left sum minus the current item.
- Range Sum Query (Immutable): Build a prefix sum array once so any range sum is one subtraction of two stored totals.
Common mistakes
- Starting the accumulator with the wrong value: use 0 for sums and counts but 1 for products, otherwise every result is off or zero.
- Updating the accumulator in the wrong order, such as saving the result before adding the current item, which shifts every answer by one position.
- Forgetting the empty prefix (sum 0 seen once) in subarray-sum counting, so subarrays that start at index 0 are missed; also watch for integer overflow on large sums.
Frequently asked questions
What is the difference between a running total and a prefix sum?
They are the same idea. A running total is the value you carry while looping, and a prefix sum is that value stored in an array so you can look it up later. Storing prefix sums lets you answer any range sum with one subtraction.
When should I use a running total instead of a sliding window?
Use a running total when you need totals over prefixes or want to count ranges using earlier totals, especially when numbers can be negative. A sliding window fits better when you want the best window of a fixed or flexible size and all values are non-negative, since you also remove items from the total as the window moves.
Can the accumulator be something other than a sum?
Yes. It can be a product, a count, a maximum so far, a minimum so far, a running XOR, or a balance such as open parentheses. The pattern is the same: one variable updated each step, so the loop never has to look back.