Today we will be going over Leetcode 1480 Running Sum of 1d Array. Our problem is a bit unique in that it really is just an introduction to the concept of using prefix sums. As such, this will be a relatively short post. But it will serve as the basis for a lot of problems we will see in the future. Prefix sums are a very common concept in competitive programming and algorithms in general. The prefix sum technique is the idea to take a list of numbers, and transform it such that each number in the list it the cumulate sum of itself and all the previous numbers in the list. This is a unique property that can help us make certain problems that would normally take O(n^2) time take O(n) time. Thats a big difference!
- leetcode
- algorithms
- typescript
- prefix sum
Read more
→