Running Sum of 1d Array - Practice Coding Problems

Running Sum of 1d Array - 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.

Input & Output

Example 1 — Basic Case

$ Input: nums = [1,2,3,4]

› Output: [1,3,6,10]

💡 Note: Running sums: [1, 1+2, 1+2+3, 1+2+3+4] = [1,3,6,10]

Example 2 — Single Element

$ Input: nums = [1]

› Output: [1]

💡 Note: Only one element, so running sum is just [1]

Example 3 — With Negative Numbers

$ Input: nums = [1,1,1,1,1]

› Output: [1,2,3,4,5]

💡 Note: Running sums of identical elements: [1, 1+1, 1+1+1, 1+1+1+1, 1+1+1+1+1]

Constraints

1 ≤ nums.length ≤ 1000
-10⁶ ≤ nums[i] ≤ 10⁶

Visualization

Tap to expand

Understanding the Visualization

Input Array

Original numbers: [1,2,3,4]

Calculate Running Sums

Each position accumulates sum up to that point

Output Array

Running sums: [1,3,6,10]

Key Takeaway

🎯 Key Insight: Each running sum builds upon the previous one, allowing O(n) solution

Asked in

a Amazon 15 M Microsoft 8 G Google 6

The key insight is that each running sum can be calculated from the previous running sum: runningSum[i] = runningSum[i-1] + nums[i]. Best approach is prefix sum in single pass with Time: O(n), Space: O(1) if modifying in-place.

Common Approaches

Approach	Time	Space	Notes
✓ Prefix Sum - Single Pass	O(n)	O(n)	Build running sum in one pass by adding each element to the previous sum
Brute Force - Recalculate Each Sum	O(n²)	O(n)	For each position, sum all elements from start to that position
In-Place Modification	O(n)	O(1)	Modify the input array directly to save space

Prefix Sum - Single Pass — Algorithm Steps

Initialize first element as nums[0]
For each subsequent position, add current element to previous running sum
Return the transformed array

Visualization

Tap to expand

Step-by-Step Walkthrough

Initialize

result[0] = nums[0] = 1

Build Running Sum

Each position = previous sum + current element

Result

Running sums calculated in O(n) time

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int* solution(int* nums, int numsSize, int* returnSize) {
    *returnSize = numsSize;
    int* result = (int*)malloc(numsSize * sizeof(int));
    result[0] = nums[0];
    
    for (int i = 1; i < numsSize; i++) {
        result[i] = result[i - 1] + nums[i];
    }
    
    return result;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    line[strcspn(line, "\n")] = 0;
    
    // Parse array [1,2,3] format
    int nums[1000];
    int size = 0;
    char* token = strtok(line + 1, ",]"); // Skip opening bracket
    
    while (token != NULL) {
        nums[size++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    int returnSize;
    int* result = solution(nums, size, &returnSize);
    
    // Print result in [1,2,3] format
    printf("[");
    for (int i = 0; i < returnSize; i++) {
        printf("%d", result[i]);
        if (i < returnSize - 1) printf(",");
    }
    printf("]\n");
    
    free(result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Single pass through array, each element processed once

✓ Linear Growth

Space Complexity

O(n)

Extra array to store n running sum values (O(1) if modifying in-place)

⚡ Linearithmic Space

85.0K Views

High Frequency

~10 min Avg. Time

4.2K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Prefix Sum - Single Pass — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler