Prefix Sum Array

Problem

Build the prefix sum array of arr, returning a list of length n + 1 where out[i] is the sum of the first i elements, so out[0] = 0.

This structure lets any contiguous range sum be computed in O(1) as out[right] - out[left]. The input may contain negative numbers or be empty.

Hint

Carry a running total and append it after each element, starting with 0.

case 1

in: [[1,2,3,4]]

expected: [0,1,3,6,10]

case 2

in: [[]]

expected: [0]

case 3

in: [[-1,1,-1]]

expected: [0,-1,0,-1]

case 4

in: [[5]]

expected: [0,5]

Starter codePython

def prefix_sums(arr):
    # Your code here
    pass

4 test cases · run your code against them in the editor