easy Problem 1 Running Sum of 1d Array

Problem Statement

Given a one-dimensional array of integers, create a new array that represents the running sum of the original array.

The running sum at position i in the new array is calculated as the sum of all the numbers in the original array from the 0th index up to the i-th index (inclusive). Formally, the resulting array should be computed as follows: result[i] = sum(nums[0] + nums[1] + ... + nums[i]) for each i from 0 to the length of the array minus one.

Examples

Example 1

Input: [2, 3, 5, 1, 6]
Expected Output: [2, 5, 10, 11, 17]
Justification:
- For i=0: 2
- For i=1: 2 + 3 = 5
- For i=2: 2 + 3 + 5 = 10
- For i=3: 2 + 3 + 5 + 1 = 11
- For i=4: 2 + 3 + 5 + 1 + 6 = 17

Example 2

Input: [1, 1, 1, 1, 1]
Expected Output: [1, 2, 3, 4, 5]
Justification: Each element is simply the sum of all preceding elements plus the current element.

Example 3

Input: [-1, 2, -3, 4, -5]
Expected Output: [-1, 1, -2, 2, -3]
Justification: Negative numbers are also summed up in the same manner as positive ones.

Constraints:

1 <= nums.length <= 1000
<= nums[i] <=

Try it yourself

Try solving this question here:

Please check the next lesson for a complete solution.

🎯 STRICT STANDOUT: Why / worked+complexity / pattern+when-not / edge / drills — Problem 1 Running Sum of 1d Array (easy)

Why this concept exists (judgment layer)

Running sum installs the PREFIX SUM family: every result[i] is an aggregate of nums[0..i]. The transferable win is replacing Θ(n²) re-summing with one O(n) accumulator — foundation for range queries, altitude, and difference arrays.

Recognition signals:

result[i] depends on the sum of nums[0..i] (or any range aggregate built from prefixes).
Brute re-summing 0..i for every i is Θ(n²).
Siblings: range-sum queries, left/right sum diffs, altitude after gains, difference arrays.

Worked example with complexity derivation

nums=[2,3,5,1,6]:
acc: 2 → 2+3=5 → 5+5=10 → 10+1=11 → 11+6=17 → [2,5,10,11,17].
Naive: for each i sum 0..i → 1+2+…+n = n(n+1)/2 → Θ(n²).
Template: acc=0; for x: acc+=x; emit acc → n adds → Θ(n) time, Θ(n) output space
(Θ(1) extra if overwrite allowed in-place).
Negatives [−1,2,−3,4,−5] → [−1,1,−2,2,−3] — prefix can decrease; still one pass.

Pattern + when-NOT / named alternative

PATTERN: PREFIX / RUNNING ACCUMULATOR — result[i]=f(prefix i). WHEN NOT: variable subarray under constraint (sum≤k, unique chars) → sliding window. Sorted pair sum → two pointers. Max contiguous sum → Kadane (not store all prefixes). Range sum many queries after static array → build prefix once O(n), query O(1).

Dual pattern: difference array (range-update)

Prefix sum answers range queries; its dual, the difference array, answers range updates cheaply. To add a constant over a range, mark only the two boundaries, then a single prefix-sum pass materialises the array.

array size 5, apply +3 on range [1,3]:
d = [0,0,0,0,0]           // difference array
d[1] += 3                 // start of range
d[4] -= 3                 // one past end of range (r+1 = 4)
d      = [0, 3, 0, 0, -3]
prefix-sum d → [0, 3, 3, 3, 0]   // indices 1..3 got +3

Each update is O(1) (two writes); one final O(n) prefix pass reconstructs the result. So k range-updates + 1 read of the whole array is O(n + k) with a difference array, versus O(nk) if you loop over each range applying the increment element by element.

Edge case / failure mode

Edges: single [5]→[5]; n≥1 so empty out of constraints; overflow if language int fixed (constraints here ±1e6 * n≤1e3 still fine). Failure: re-summing each i under n=1e5.

Hostile-panel drills (defend the decision)

Q1. Derive time of re-summing every prefix.
Model answer: Σ_{i=1..n} i grows quadratically (the closed form shown in the worked-example derivation above), hence Θ(n²).

Q2. When is sliding window the right sibling instead?
Model answer: When you need a contiguous segment meeting a live constraint, not all prefixes stored.

Q3. In-place running sum: space?
Model answer: Θ(1) extra: nums[i]+=nums[i-1] for i=1..n-1; output overwrites input.

✅ Solution Running Sum of 1d Array

Problem Statement

Given a one-dimensional array of integers, create a new array that represents the running sum of the original array.

Examples

Example 1

Input: [2, 3, 5, 1, 6]
Expected Output: [2, 5, 10, 11, 17]
Justification:
- For i=0: 2
- For i=1: 2 + 3 = 5
- For i=2: 2 + 3 + 5 = 10
- For i=3: 2 + 3 + 5 + 1 = 11
- For i=4: 2 + 3 + 5 + 1 + 6 = 17

Example 2

Input: [1, 1, 1, 1, 1]
Expected Output: [1, 2, 3, 4, 5]
Justification: Each element is simply the sum of all preceding elements plus the current element.

Example 3

Input: [-1, 2, -3, 4, -5]
Expected Output: [-1, 1, -2, 2, -3]
Justification: Negative numbers are also summed up in the same manner as positive ones.

Constraints:

1 <= nums.length <= 1000
<= nums[i] <=

Solution

To find a solution of this problem, we can employ a straightforward approach. Starting from the first element of the input array, we can traverse through each element, cumulatively summing up the values as we proceed and placing the running total at the corresponding index in the resulting array.

Initially, the first element of the output array is the same as the input array since there are no preceding elements to add. From the second element onwards, every element in the output array is the sum of the current element in the input array and the previous element in the output array. This is because the previous element in the output array already contains the cumulative sum of all the previous elements in the input array.

Step-by-step Algorithm

Check for Edge Cases:
- If the input array is null or has no elements, return an empty array since there's nothing to process.
Initialize the Result Array:
- Create an array of the same length as nums to store the running sum.
- Set the first element of result equal to the first element of nums since the first element remains unchanged.
Compute the Running Sum:
- Iterate through the array starting from index 1.
- For each index, update the value in the result array by adding the previous sum to the current element.
Return the Running Sum Array:
- After processing all elements, return the result array, which now contains the cumulative sum at each index.

Algorithm Walkthrough

Initialization

Input: [2, 3, 5, 1, 6]
Create a result array with five elements.
Set the first element of result to 2.
Result after initialization: [2, _, _, _, _]

Step-by-Step Computation

Iteration 1 (i = 1)
- Add the previous sum (2) to the current element (3).
- Update result[1] to 5.
- Result: [2, 5, _, _, _]
Iteration 2 (i = 2)
- Add the previous sum (5) to the current element (5).
- Update result[2] to 10.
- Result: [2, 5, 10, _, _]
Iteration 3 (i = 3)
- Add the previous sum (10) to the current element (1).
- Update result[3] to 11.
- Result: [2, 5, 10, 11, _]
Iteration 4 (i = 4)
- Add the previous sum (11) to the current element (6).
- Update result[4] to 17.
- Result: [2, 5, 10, 11, 17]

Final Output

Running Sum Array: [2, 5, 10, 11, 17]
This array represents the cumulative sum at each step.

Code

Here is the code for this algorithm:

java

class Solution {

  public int[] runningSum(int[] nums) {
    // Check if the array is null or has no elements and return an empty array if true
    if (nums == null || nums.length == 0) {
      return new int[0];
    }

    // Initialize an array to store the running sum
    int[] result = new int[nums.length];
    result[0] = nums[0];

    // Loop through the array starting from index 1, adding the previous sum to the current element
    for (int i = 1; i < nums.length; i++) {
      result[i] = result[i - 1] + nums[i];
    }

    // Return the array containing the running sum
    return result;
  }

  public static void main(String[] args) {
    Solution solution = new Solution();

    // Test cases
    int[][] testInputs = {
      { 2, 3, 5, 1, 6 },
      { 1, 1, 1, 1, 1 },
      { -1, 2, -3, 4, -5 },
    };

    for (int[] input : testInputs) {
      int[] output = solution.runningSum(input);

      // Print the output array
      for (int val : output) {
        System.out.print(val + " ");
      }
      System.out.println();
    }
  }
}

Complexity Analysis

Time Complexity

Single pass through the array: The algorithm uses a single loop to traverse the input array nums. For each element, it calculates the running sum by adding the current element to the sum of the previous elements. This loop runs for each element in the array, so it takes time, where N is the length of the input array.

Overall time complexity: , where N is the number of elements in the input array.

Space Complexity

Output array: The algorithm creates a new array result to store the running sum. This array has the same length as the input array, so the space complexity for the result array is , where N is the number of elements in the input array.
Additional variables: The algorithm uses a few extra variables (i), which take constant space, .

Overall space complexity: , where N is the number of elements in the input array.

Pattern Transfer — PREFIX SUM / RUNNING ACCUMULATOR

Pattern family: PREFIX SUM. This page is the gateway to range queries, left/right differences, and altitude-from-gains.

Recognition signals: need every prefix; need range sum as pref[r]−pref[l−1]; “running total” language.

Template:

acc = 0
for x in a:
  acc += x
  store/use acc

In-place variant (mutation OK, O(1) extra): for i = 1 .. n-1: a[i] += a[i-1]. Example: [1,2,3] → [1,3,6].

When NOT:

Variable window constraint → sliding window.
Pair sum on sorted array → two pointers.
Frequencies / membership → hash set/map.

Brute contrast: for each i sum 0..i costs 1+2+…+n = n(n+1)/2 = Θ(n²).

Complexity derivation (K11)

Loop over indices 1..n−1 inclusive → exactly n−1 constant-time updates → Θ(n) time. New array length n → Θ(n) space (or O(1) extra if in-place). For n=5 → 4 updates.

Transfer siblings: Left and Right Sum Differences; Find the Highest Altitude; range-sum queries via prefix.

Drill: Given prefix array P, express sum of subarray [L..R] in O(1).

🧩 Pattern · Arrays

Recognize it: Scan once tracking what you need (running max/sum), or precompute a prefix-sum / hash → turn O(n²) into O(n).

▶ Visualize this problem (step it, predict each fork)

⛶ Open this problem debugger in explore mode

🤖 Don't fully get this? Learn it with Claude

Stuck on Problem 1 Running Sum of 1d Array? Open Claude, copy a block below, and it'll teach you this exact concept — visually and interactively.

🪜 Hint ladder (no spoilers)

Progressively stronger hints — you still solve it.

I'm working on the problem **Problem 1 Running Sum of 1d Array** (DSA). Give me a HINT LADDER: start with the tiniest nudge, then wait. Only reveal the next, stronger hint when I ask. Do NOT show the full solution unless I type 'show solution'. Keep me doing the thinking. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

🎨 Explain the approach visually

See the technique, not just code.

Explain the optimal approach to **Problem 1 Running Sum of 1d Array** with a VISUAL walkthrough: trace it on a small concrete example using ASCII art / a step-by-step diagram, narrate what changes each step, then give time & space complexity with a one-line derivation. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

🔍 Review my solution

Catch bugs, edge cases, sub-optimality.

I'll paste my solution to **Problem 1 Running Sum of 1d Array**. Review it for correctness, missed edge cases, and time/space complexity, then coach me toward the optimal — don't just rewrite it. Ask me to paste my code now. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

🔁 Drill the pattern

Lock in recognition with look-alikes.

Give me 2 problems that use the SAME underlying pattern as **Problem 1 Running Sum of 1d Array**. For each, let me attempt first, then review my answer and name the trigger signal that reveals the pattern. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

📝 My notes

← Roman to Integer Best Time to Buy and Sell →