Topic: Learning notes

LeetCode 1480: Running Sum in TypeScript

Use each completed array position as state for one linear scan, with an honest discussion of in-place mutation, the loop invariant, and O(n) time.

This small problem is useful because one array position becomes state for the next. Start at the second position. The previous one already holds the total so far, so adding it to the current value produces the next running sum.

Problem

Original problem: LeetCode 1480: Running Sum of 1d Array

Given an integer array nums, return an array where the value at index i is the sum of nums[0] through nums[i].

For example, [1, 2, 3, 4] becomes [1, 3, 6, 10].

The repeated-work approach

The most direct approach recalculates the entire prefix for every index.

function runningSumNaive(nums: number[]): number[] {
  return nums.map((_, end) => {
    let sum = 0;

    for (let start = 0; start <= end; start += 1) {
      sum += nums[start];
    }

    return sum;
  });
}

It repeats work. The first result adds one value, the second adds two values, and so on, for O(n²) total time.

Reuse the previous position

The preceding position already stores the prefix sum. Update the current position instead of starting over.

function runningSum(nums: number[]): number[] {
  for (let index = 1; index < nums.length; index += 1) {
    nums[index] += nums[index - 1];
  }

  return nums;
}

This version mutates nums and returns that same array. The original problem only asks for the running sum. If the caller still needs the source values, copy the array before calling the function.

Why the loop is correct

At the start of each iteration, every position before index already contains its running sum.

The base case is index = 1. nums[0] is unchanged, so it is the running sum of its one-element prefix. After nums[index] += nums[index - 1], the current value is its original value plus the prior running sum. That is the sum from index 0 through index. When the loop ends, every position satisfies the problem definition.

Minimal verification

console.log() only leaves a result for someone to inspect. An assertion fails when the result differs from the expected value.

import assert from "node:assert/strict";

assert.deepStrictEqual(runningSum([1, 2, 3, 4]), [1, 3, 6, 10]);
assert.deepStrictEqual(runningSum([3, 1, 2, 10, 1]), [3, 4, 6, 16, 17]);
assert.deepStrictEqual(runningSum([-2, 5, -1]), [-2, 3, 2]);

Complexity and trade-off

The loop visits the array once, so time is O(n). This version allocates no separate working array, so auxiliary space is O(1), but it mutates the input.

To keep the input unchanged, write const result = [...nums] and run the same loop on result. Time remains O(n), while auxiliary space becomes O(n).

Common mistakes

• Starting at index 0 and reading a nonexistent previous position.
• Recalculating every prefix and falling back to O(n²) time.
• Failing to document that the function mutates its input.
• Treating returned storage and auxiliary working space as the same thing.

Transferable idea

The state in this problem is the preceding running sum. A scalar is enough when only the final total is needed. Store every prefix in an array when later work needs each intermediate result. The same distinction appears in prefix sums, range queries, and dynamic programming.

External references

• LeetCode 1480: Running Sum of 1d Array: original problem statement, examples, and constraints.
• TypeScript Handbook: More on Functions: function parameter and return-type syntax.
• Node.js: assert.deepStrictEqual(): strict deep equality checks for array results.