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.

✅ 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.

🤖 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 →