Running Sum of 1d Array

EASY

Description

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

Checkout 3 different approaches to solve Running Sum of 1d Array. Click on different approaches to view the approach and algorithm in detail.

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.

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.

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.

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;
    }
}

Complexity Analysis

Time Complexity: 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 Complexity: 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 and Cons

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.

Code Solutions

Checking out 4 solutions in different languages for Running Sum of 1d Array. Click on different languages to view the code.

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

Video Solution

Watch the video walkthrough for Running Sum of 1d Array

Patterns:

Prefix Sum

Data Structures:

Array

Companies:

EPAM Systems |