Prefix Sum Pattern

I want to share an insight I have into the 'prefix sum' pattern. It's one of 15 patterns recommended on this site, for candidates who want to prepare for coding rounds. Link to site:

LeetCode was HARD until I Learned these 15 Patterns

#21 - Patterns to master LeetCode

AlgoMaster NewsletterAshish Pratap Singh

This is the algorithm mentioned:

For experienced readers, the insight I have is that of continuity, and how it's so relevant to arrays, from storing numbers to retrieving them, and even thinking about how to use an array.

For new programmers, new grads, and curious people, the above will be more clear at the end.

In computer science, an array is a continuous sequence, in memory.

No need to overthink it.

As in, all this:

1. There is an abstract, conceptual thing, like a row of boxes
2. That's not in reality
3. ...but represents something in reality, and probably not the matrix's Ones and Zeroes
4. And a programmer doesn't need to know all this to make one.

Is not needed.

For a coder, this is enough:

var array = new int[10]; // int is for integer.

But I am glad I took that philosophy course.

I found it interesting that this problem applies closely to arrays, as a concept.

That is, there is a direct relationship to why an array is used, and why this problem is this way.

It's like having an array of 10 buckets of water, each having 1 liter of water.

loop over the array Walk next to the bucket, take half of the water from the first bucket, and pour it into the next index bucket.

Which bucket will overflow?

Assuming a bucket can handle only 2 liters, second bucket will now have 1.5 liters.

Half of that, 0.75, into the next bucket, is 1.75 liters.

Next bucket will have 2.875 liters.....Oops.

The answer is the 4th bucket.

Remember when I said an array is 10 buckets of water levels close to each other a contiguous set of memory locations?

But wait, there's more!

The 2 sum problem asks for the location of 2 numbers that add to another number. The latter number is not known beforehand.

How would you find 2 buckets that add up to X amount of water?

In the previous problem, we are told each bucket has 1 liter. Here we don't know that. Additionally, we aren't even told what X is.

But the interviewer slipped up - probably intentionally.

Zoom, enhance, and find the spy (kid)

2 numbers that add to another number.

Ok, so

a + b = X.

Out of the 10 buckets, two of them - say, 4th or 7th one - or maybe 1st and 9th, have water, that together are X.

The best way to find which buckets have water equal to X, will have the same solution as the best way to find the indexes of 2 numbers in an array, which add up to X.

2 problems - one that is a basic pattern of 'prefix sum' and another utilizing commutative property of math - rely on continuity of integers water levels for an efficient solution.

I am excited I was able to figure out the 'purpose' of prefix pattern, and wanted to share my thoughts.

I am beginning to understand the purpose of leetcode, and what some advice I have read, and been told, means.

Lot of advice I see for computer science online, or my mother's tutoring, feel like this:

I mean if you work hard everyday, you will succeed in life, and if you run everyday, you will break the world record at some point.

If I remember correctly, an elderly friend of my father asked me how I write. I think I said, 'If you can read, you can write'.

I would later read about Hemingway's shit-detector, but I think it's the reverse that's true. Interest affects talent, as much as the other way around.

Once you know what is bad, then comes the why it's bad, then the hardwork to improve...starts.

Until I started reading the Art of Programming, I didn't know the 5 qualities of a good algorithm.

Those 5 qualities framed the way I spent time on my algorithms, planning my studies, from knowing when to see the answer, and when to push myself more.

And its not like I am a genius - I recognized the beauty in The Art of War as a poet:

Sounds like Muhammad Ali's

"Float like a butterfly. Sting like a bee. You can't hit what your eyes don't see."

But I understood it last year.

Philosophers, am I right?

They don't make sense, and when they do, you think they're great - because their words perfectly encapsulate a decade of struggle.

Now, reading The Art of War in college, instead of getting a ph.D. in computer science, and starting the Art of Programming this year, after layoffs - it takes bravery, not genius 😄

Let's get back to water arrays.

I don't need to know how to solve the problem, though I am pretty sure solving it quickly will help my scores, in interviews.

I need to use this pattern, to understand what properties of the solution, transfer to something efficient, smart, and creative, which I can use later in real life.

In prefix sum, it's the idea of cumulation - if everything is stored continuously, I can do math that involves continuity without taxing the computer.

I am pretty sure there are more concepts like this in this problem, but for now - sounds like arrays are a way to think in terms of continuity.

Not just in memory - continuous ease of access - like interview guides say.

But also continuous math - say, sequences of fibonacci.

Or, the prices of the stock market over time - this problem gives you an array, but the solution uses another pattern, 2 pointers.

If I have a customer that wants to know how many servers buckets can be filled with `log.txt`, and I need to ask Microsoft for money to buy more servers buckets, while I can't use this algorithm, Microsoft will be very happy if my algorithm used less electricity, less servers, and less time for the same result.