Is there a way to print the cumulative sum of a given list of non-negative integers of length n in O(n)?

For instance, given a list {3,2,3,12,2}

the output would be: 3 5 5 17 17

I would have to implement this in a unbounded ram, so complicated structures may be hard to do.

CodePudding user response：

If you use a HashSet for the lookup of already seen elements then you just need a single pass and can solve this in O(n).

def cumulative_sum(l):
    seen = set()
    result = []
    for e in l:
        last = result[-1] if result else 0
        if e in seen:
            result.append(last)
        else:
            seen.add(e)
            result.append(last   e)
    return result

l = [3, 2, 3, 12, 2]
print(cumulative_sum(l))