Introduction

The Running Sum problem involves calculating the cumulative sum of elements in an array.

The running sum at index i is equal to:

  • sum of all elements from index 0 to i.

Given an array arr[] of size n, the task is to return the running sum array.

This is one of the most important beginner-level Prefix Sum problems and helps in understanding cumulative computations, prefix processing, and array traversal.

Example

Input: arr[] = [1, 2, 3, 4]Output: [1, 3, 6, 10]
Explanation:
Running Sum at index 0 = 1
Running Sum at index 1 = 1 + 2 = 3
Running Sum at index 2 = 1 + 2 + 3 = 6
Running Sum at index 3 = 1 + 2 + 3 + 4 = 10

Input: arr[] = [5, 1, 2, 7]
Output: [5, 6, 8, 15]
Explanation:
Each element stores cumulative sum till that index.

Constraints

   1 <= n <= 10^5-10^9 <= arr[i] <= 10^9

Approach 1 : Brute Force

Explanation

The simplest way to solve this problem is:

  1. For every index:
    • calculate sum from index 0 to current index
  2. Store the calculated sum

This approach is easy to understand but repeatedly calculating sums increases time complexity.

Steps

  1. Traverse the array.
  2. For every index:
    • calculate cumulative sum from beginning
  3. Store the sum in result array.
  4. Return result array.

Dry Run

Input Array: [1, 2, 3, 4]Index 0:
Sum = 1
Result:
[1]
Index 1:
Sum = 1 + 2 = 3
Result:
[1, 3]
Index 2:
Sum = 1 + 2 + 3 = 6
Result:
[1, 3, 6]
Index 3:
Sum = 1 + 2 + 3 + 4 = 10
Final Result:
[1, 3, 6, 10]

Brute Force Code

Complexity Analysis

Time Complexity: O(n²)Explanation:
For every index, previous elements are traversed again.

Space Complexity: O(n)
Explanation:
An extra array is used to store running sums.

Approach 2 : Optimized Solution (Prefix Sum)

Explanation

Instead of recalculating sums repeatedly, we can use the Prefix Sum Technique.

The idea is:

  1. Running Sum at current index =
    • previous running sum + current element

This allows cumulative sums to be calculated efficiently in one traversal.

Steps

  1. Initialize:
    • runningSum = 0
  2. Traverse the array.
  3. Add current element to runningSum.
  4. Store runningSum into result array.
  5. Return final result.

Dry Run

Input Array: [1, 2, 3, 4]Initially:
runningSum = 0
Traverse 1:
runningSum = 0 + 1 = 1
Result:
[1]
Traverse 2:
runningSum = 1 + 2 = 3
Result:
[1, 3]
Traverse 3:
runningSum = 3 + 3 = 6
Result:
[1, 3, 6]
Traverse 4:
runningSum = 6 + 4 = 10
Final Result:
[1, 3, 6, 10]

Optimized Code 

Complexity Analysis

Time Complexity: O(n)Explanation:
Each element is processed only once.

Space Complexity: O(n)
Explanation:
Result array stores cumulative sums.

Edge Cases

  1. Array contains negative numbers
  2. Array contains zeros
  3. Array contains one element
  4. Array contains large values

Why This Problem is Important

This problem helps in understanding:

  1. Prefix Sum Technique
  2. Cumulative calculations
  3. Efficient traversal
  4. Range-based computations
  5. Optimization techniques

It is one of the most important beginner-level Prefix Sum problems.

Real-World Applications

Running Sum concepts are used in:

  1. Financial analytics
  2. Data stream processing
  3. Time-series analysis
  4. Sensor monitoring
  5. Performance tracking systems

Common Mistakes

  1. Incorrect cumulative updates
  2. Forgetting previous sum
  3. Incorrect initialization
  4. Overwriting original values unintentionally

Interview Tips

Interviewers often expect:

  1. Prefix Sum optimization
  2. O(n) traversal
  3. Proper cumulative logic

Always explain why storing previous cumulative sums avoids repeated calculations.

Related Questions

  1. Range Sum Query
  2. Subarray Sum Equals K
  3. Prefix Sum Array
  4. Maximum Subarray Sum
  5. Product Except Self

Final Takeaway

The Running Sum problem is a fundamental Prefix Sum problem that teaches cumulative computation and efficient traversal techniques. Understanding this problem builds a strong foundation for advanced prefix sum, range query, and subarray interview problems.