Understanding Prefix Sum for LeetCode Problems

Image for post
Image for post

The background

There are number of prefix sum problems on LeetCode, and they tend to either be Medium or Hard problems. Is there a way this can be reasonably explained and coded?

Let us have a go!

The problem

Given aan array of Int nums, and an integer k calculate the number of continuous subarrays whose sum equals the integer k.

Continuous means that there cannot be a gap in the subarray.

The explanation

It is possible to create a memo using a dictionary to make our answer as efficient as possible (since a dictionary can be accessed in O(n)).

Image for post
Image for post

So the count is incremented if we have visited the prefixSum — 3 (and natually this must have came before the current num we are visiting, in continuous order).

So here is an example where k = 3 and nums is [1,2,3,4,2,1] which gives the result as 3, represented as three blue arrows here:

Image for post
Image for post

The solution

Here the dictionary is used to store the memo, as lookup can happen (on average) O(n).

You can download the repo from here!

Conclusion

This is a really important theoretical tool for your programming toolbox, and is one that is often used for those people who have LeetCode problems to solve.

If you’ve any questions, comments or suggestions please hit me up on Twitter

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store