Skip to main content
Talentd

Running Sum of 1d Array - Solution & Explanation

EasyArrayPrefix Sum12 min readAsked at: Amazon, Microsoft, Meta +3
Practice this problem

Problem Statement

Given an array nums. We define a running sum of an array as runningSum[i] = sum(nums[0]…nums[i]).

Return the running sum of nums.

 

Example 1:

Input: nums = [1,2,3,4]
Output: [1,3,6,10]
Explanation: Running sum is obtained as follows: [1, 1+2, 1+2+3, 1+2+3+4].

Example 2:

Input: nums = [1,1,1,1,1]
Output: [1,2,3,4,5]
Explanation: Running sum is obtained as follows: [1, 1+1, 1+1+1, 1+1+1+1, 1+1+1+1+1].

Example 3:

Input: nums = [3,1,2,10,1]
Output: [3,4,6,16,17]

 

Constraints:

  • 1 <= nums.length <= 1000
  • -10^6 <= nums[i] <= 10^6

Approach Overview

Problem Overview: You receive an integer array nums. For each index i, compute the cumulative sum from index 0 to i. The result array stores these progressive totals, commonly called a running sum or prefix sum. This pattern appears frequently in problems involving cumulative totals, range queries, and sliding windows.

Approach 1: Iterative Accumulation (O(n) time, O(n) space)

Create a new result array and build the running sum while iterating through the input. Start with result[0] = nums[0]. For each next index, compute result[i] = result[i-1] + nums[i]. Each step reuses the previous prefix value instead of recomputing the entire sum. The algorithm performs a single linear pass over the array, making it efficient and straightforward. This version is useful when you must preserve the original input array or when the problem explicitly requires a separate output structure.

Approach 2: In-Place Modification (O(n) time, O(1) space)

The running sum can also be computed directly inside the input array. Iterate from index 1 to the end and update each element as nums[i] += nums[i-1]. Because nums[i-1] already stores the cumulative total up to the previous index, adding it produces the correct running sum. This approach leverages the idea behind prefix sums while minimizing extra memory usage. Only one traversal is required, and the array gradually transforms into the prefix array.

This in-place strategy is common in interview settings when memory optimization matters. It avoids allocating additional arrays and keeps the implementation extremely compact. The only tradeoff is that the original input values are overwritten.

Recommended for interviews: Interviewers expect the prefix-sum insight quickly. Demonstrating the iterative accumulation approach first shows you understand the cumulative relationship between elements. Then optimizing to the in-place version signals awareness of space complexity and memory tradeoffs. Both run in O(n) time, but the in-place method achieves O(1) auxiliary space, which is typically considered the optimal solution.

The running sum technique forms the foundation for more advanced prefix sum problems such as range sum queries, subarray sum detection, and difference arrays. Mastering this pattern makes many seemingly complex array problems easier to reason about.

Approach 1: Iterative Accumulation

This approach involves iterating through the array nums and calculating the running sum iteratively. Use an accumulator variable to keep the sum of elements encountered so far, and place this running sum into the result array.

This C program uses a function runningSum which takes the original array nums, its size, and an array returnArr to store the running sums. An accumulator sum keeps track of the cumulative total as we iterate over the array.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n) where n is the number of elements in the array.
Space Complexity: O(1) since we're modifying the array in place.

Try this approach in the editor →

Approach 2: In-Place Modification

For the in-place approach, iterate through the array nums, and update each position directly to the running sum. This method reduces space usage by avoiding the creation of a separate result array.

In this C solution, the running sum is calculated in place by iterating over the array starting from the second element. Each element is updated as the sum of itself and its predecessor.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n)
Space Complexity: O(1) since only the input array is modified.

Try this approach in the editor →

Approach 3: Prefix Sum

We directly traverse the array. For the current element nums[i], we add it with the prefix sum nums[i-1] to get the prefix sum nums[i] of the current element.

The time complexity is O(n), where n is the length of the array. The space complexity is O(1).

Code

PythonJavaC++GoTypeScriptC#PHP

Python

Java

C++

Go

TypeScript

C#

PHP

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Iterative Accumulation

Time Complexity: O(n) where n is the number of elements in the array.
Space Complexity: O(1) since we're modifying the array in place.

In-Place Modification

Time Complexity: O(n)
Space Complexity: O(1) since only the input array is modified.

Prefix Sum—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Iterative Accumulation (Extra Array)O(n)O(n)When the original array must remain unchanged or when returning a separate result array
In-Place ModificationO(n)O(1)Best for interviews and memory-constrained scenarios where modifying the input array is allowed

Video Solution

Running Sum of 1d Array | LeetCode 1480 | C++, Java, Python • Knowledge Center • 25,740 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Running Sum of 1d Array easy or hard?
Running Sum of 1d Array is classified as an Easy problem on LeetCode with a high acceptance rate. It introduces the prefix sum concept, which becomes essential for solving many medium and hard array problems later.
How to solve Running Sum of 1d Array in O(n)?
Iterate through the array starting from index 1 and add the previous value to the current element. The update rule is nums[i] = nums[i] + nums[i-1]. Since the previous element already stores the cumulative total, this builds the running sum with a single linear traversal.
Running Sum of 1d Array Python or Java solution?
In Python or Java, iterate through the array from index 1 and update each element using the previous prefix value. Python example logic: nums[i] += nums[i-1]. Java uses the same pattern inside a for loop. Both implementations run in O(n) time with O(1) additional space.
What is the best approach for Running Sum of 1d Array?
The best approach uses a prefix sum technique with a single pass through the array. Each element is updated using the previous cumulative value: nums[i] += nums[i-1]. This runs in O(n) time and O(1) extra space when done in place, which is typically the optimal solution expected in interviews.
What data structure is used in Running Sum of 1d Array?
The problem primarily uses an array with a prefix sum technique. No advanced data structures are required. The algorithm relies on sequential traversal and cumulative addition across the array elements.
What is the time complexity of Running Sum of 1d Array?
The optimal solution runs in O(n) time because each element of the array is processed exactly once. Every step performs a constant-time addition using the previous prefix value. Space complexity is O(1) when modifying the array in place, or O(n) if a separate result array is used.
Is Running Sum of 1d Array asked at Google, Amazon, or Meta?
Prefix sum fundamentals appear frequently in interviews at large tech companies including Google, Amazon, and Meta. While this exact easy problem may appear less often, it tests the core concept behind many harder prefix-sum and subarray problems used in real interviews.

Ready to solve this problem?

Practice Running Sum of 1d Array with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays