Running State Pattern — LeetCode #1480: Running Sum of 1D Array

Prerequisite: Loop Invariants — the first post in this series covers what an invariant is and how to state one. If the word "invariant" is new to you, start there. The Problem (15 seconds) Given an array nums , return an array where each element is the running sum up to that index. Input: [1, 2, 3, 4] Output: [1, 3, 6, 10] // result[0] = 1 // result[1] = 1 + 2 = 3 // result[2] = 1 + 2 + 3 = 6 // result[3] = 1 + 2 + 3 + 4 = 10 LeetCode #1480 — Running Sum of 1D Array The Obvious Mistake Most engineers look at this problem and see a loop inside a loop. "For each index, add up everything before it." That's the instinct. It's technically correct. It's also exactly the kind of thinking that produces O(n²) code when O(n) was sitting right there. // Brute force — recompute the sum from scratch for each index function runningSum ( nums : number []): number [] { const result : number [] = []; for ( let i = 0 ; i < nums . length ; i ++ ) { let sum = 0 ; for ( let j = 0 ; j <= i ; j ++ ) { sum +=