# Running Sum of 1d Array
**Difficulty:** EASY
[External](https://leetcode.com/problems/running-sum-of-1d-array)
Canonical: https://scaleengineer.com/dsa/problems/running-sum-of-1d-array
**Patterns:** [Prefix Sum](https://scaleengineer.com/dsa/patterns/prefix-sum)
**Data structures:** Array
**Companies:** [EPAM Systems](https://scaleengineer.com/companies/epam-systems)
---
## Problem
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`

# Approaches
## Brute Force with Nested Loops
This approach directly follows the definition of a running sum. For each element at index `i` in the output array, we calculate the sum of all elements from the beginning of the input array up to index `i` by iterating from the start every time.
**Time:** O(n^2), where n is the number of elements in the input array. The nested loops result in a quadratic number of operations. For each element `i`, we perform `i+1` additions. · **Space:** O(n), where n is the number of elements. We create a new array of size `n` to store the results. If the output array is not considered extra space, it would be O(1).
**Pros:** Simple to understand and implement directly from the problem definition.
**Cons:** Highly inefficient due to redundant calculations.; Will be very slow for large input arrays, potentially leading to a 'Time Limit Exceeded' error in competitive programming platforms.
### Explanation
We initialize a new result array, `runningSum`, with the same size as the input `nums`. We then iterate through `nums` from `i = 0` to `n-1`. In each iteration, we use another nested loop that runs from `j = 0` to `i` to sum up the elements `nums[0]` through `nums[i]`. This sum is then stored in `runningSum[i]`. This process is repeated for all indices, resulting in redundant calculations as we re-calculate sums for previous elements in every step.

```java
class Solution {
    public int[] runningSum(int[] nums) {
        int n = nums.length;
        int[] result = new int[n];
        for (int i = 0; i < n; i++) {
            int currentSum = 0;
            for (int j = 0; j <= i; j++) {
                currentSum += nums[j];
            }
            result[i] = currentSum;
        }
        return result;
    }
}
```
### Algorithm
- Create a new integer array `result` of the same size as `nums`.
- Loop through the input array `nums` with index `i` from `0` to `nums.length - 1`.
- Inside the loop, initialize a variable `currentSum` to `0`.
- Start a nested loop with index `j` from `0` to `i`.
- Add `nums[j]` to `currentSum`.
- After the inner loop, assign `currentSum` to `result[i]`.
- After the outer loop finishes, return the `result` array.

## Single Pass with Separate Array
A more efficient approach is to realize that the running sum at index `i` is simply the running sum at index `i-1` plus the current element `nums[i]`. This avoids the need for nested loops and repeated calculations.
**Time:** O(n), where n is the number of elements in the array. We iterate through the array only once. · **Space:** O(n), as we use an additional array of size `n` to store the running sum.
**Pros:** Much more efficient than the brute-force approach with a linear time complexity.; Still conceptually simple and easy to follow.
**Cons:** Uses extra space proportional to the input size, which might be a concern for very large inputs under strict memory constraints.
### Explanation
We can compute the running sum in a single pass. We create a new array, `result`, to store the running sums. The first element of the `result` array is the same as the first element of the input array (`result[0] = nums[0]`). Then, we iterate from the second element (`i = 1`) to the end of the array. For each element, we calculate its running sum using the formula `result[i] = result[i-1] + nums[i]`. This way, each running sum is calculated in constant time using the previously computed value.

```java
class Solution {
    public int[] runningSum(int[] nums) {
        int n = nums.length;
        int[] result = new int[n];
        result[0] = nums[0];
        for (int i = 1; i < n; i++) {
            result[i] = result[i-1] + nums[i];
        }
        return result;
    }
}
```
### Algorithm
- Create a new integer array `result` of the same size as `nums`.
- Set `result[0] = nums[0]`.
- Loop through the input array `nums` with index `i` from `1` to `nums.length - 1`.
- Calculate `result[i] = result[i-1] + nums[i]`.
- After the loop, return the `result` array.

## In-place Modification
This is the most optimal approach in terms of space complexity. Instead of creating a new array for the results, we can modify the input array itself to store the running sum. This is possible because once we calculate the running sum for an index, the original value at that index is no longer needed for subsequent calculations.
**Time:** O(n), where n is the number of elements in the array. We perform a single pass through the array. · **Space:** O(1), as we modify the array in-place and do not use any additional space that scales with the input size. The space for the output is reused from the input.
**Pros:** Most efficient in terms of both time and space.; No extra memory allocation is needed.
**Cons:** Modifies the original input array, which might not be desirable in all situations. If the original array is needed later, a copy must be made first.
### Explanation
We can optimize the previous approach by eliminating the need for a separate result array. We can use the input array `nums` to store the running sum. We start our iteration from the second element (index 1). For each index `i`, we update the element `nums[i]` by adding the value of the previous element `nums[i-1]` to it. Since `nums[i-1]` already holds the running sum up to that point, `nums[i] + nums[i-1]` gives the new running sum at index `i`. After the loop completes, the input array `nums` is transformed into the running sum array.

```java
class Solution {
    public int[] runningSum(int[] nums) {
        for (int i = 1; i < nums.length; i++) {
            // The current element becomes the sum of itself and the previous element
            // which is already the running sum up to that point.
            nums[i] += nums[i - 1];
        }
        return nums;
    }
}
```
### Algorithm
- Loop through the input array `nums` with index `i` from `1` to `nums.length - 1`.
- Update the current element by adding the previous element's value: `nums[i] = nums[i] + nums[i-1]`.
- After the loop, the `nums` array itself contains the running sums. Return `nums`.

# Solutions
### CSharp

```csharp
public class Solution {
    public int[] RunningSum(int[] nums) {
        for (int i = 1; i < nums.Length; ++i) {
            nums[i] += nums[i - 1];
        }
        return nums;
    }
}
```

### Java

```java
class Solution {
public
  int[] runningSum(int[] nums) {
    for (int i = 1; i < nums.length; ++i) {
      nums[i] += nums[i - 1];
    }
    return nums;
  }
}

```

### CPP

```cpp
class Solution {
public:
  vector<int> runningSum(vector<int> &nums) {
    for (int i = 1; i < nums.size(); ++i)
      nums[i] += nums[i - 1];
    return nums;
  }
};

```

### Python

```python
class Solution:
    def runningSum(self, nums: List[int]
                   ) -> List[int]: return list(accumulate(nums))

```