Find the running sum of an array of integers

Given an array of integers, return a new array containing the running sum of integers of first array.

Assumptions

- array.length >= 1

- Array is unsorted

- Array can contain duplicate numbers

Example

Input: [2,1,9,4,10,3,7,5,6]

Output: [2,3,12,16,26,29,36,41,47]

Explanation: Running sum is calcullates as [2, 2+1, 2+1+9, 2+1+9+4, 2+1+9+4+10, ...]

Solution

1. Maintain a new array - running sum array - to store the values of running sums. Initialize the array to the same length as the original array.

2. Maintain an int variable to store the running sum.

3. Traverse Array.
- Update running sum by adding element to the running sum.
- Add running sum to the running sum array.

4. Return running sum array.

Code

Complexity

Time Complexity O(N) -

Space Complexity O(N)