Thinking on Scale: The Range Sum Query Lesson

Hello guys! Today I want to talk about a LeetCode problem that looks deceptively simple but, in my opinion, carries a really interesting lesson for any software engineer: Range Sum Query — Immutable.

I believe this is a great initial question to give engineers a taste of what it really means to think on scale. Let’s take a look.

The Problem

The statement is pretty straightforward: you get an array of integers and you need to implement a sumRange(left, right) method that returns the sum of the elements between indexes left and right (inclusive).

Any software engineer can solve this. Store the numbers, and at every query just run through them left to right adding things up, right?

class NumArray:
    def __init__(self, nums: List[int]):
        self.nums = nums

    def sumRange(self, left: int, right: int) -> int:
        return sum(self.nums[left:right+1])

Easy. Problem solved. Move on.

…or is it?

The catch

Here is where I think most people stop and miss the real beauty of engineering. If we truly want to engineer something great, we can’t stop at our first draft. What if sumRange gets called a billion times?

Currently, we’re paying O(N) on every single sumRange call. If that is all that we got, we’ll be swallowed by the volume of requests. Scale is unforgiving. Can we do better than this? The answer is yes.

A faster sumRange with prefix sums

It turns out we can answer sumRange in O(1) if we’re willing to do a bit of extra work upfront. The trick is to compute a prefix sum array during initialization, where each position i holds the sum of all numbers from 0 to i-1.

class NumArray:
    def __init__(self, nums: List[int]):
        n = len(nums)
        self.prefix = [0] * (n+1)
        self.nums = nums
        for i in range(1, n+1):
            self.prefix[i] = self.prefix[i-1] + self.nums[i-1]

With that in place, answering any query becomes a single subtraction:

def sumRange(self, left: int, right: int) -> int:
    return self.prefix[right+1] - self.prefix[left]

We pay O(N) once on construction, and every sumRange call after that is constant time. A billion calls? No problem.

But wait… there is always a tradeoff

Did you notice what just happened? We traded memory for time. We allocated an extra array of size N+1 to make our sumRange queries instant.

And that is the whole point of this post: it is not about solving the problem, it is about how to think about solving the problem.

What if memory is the real constraint in our application? What if we’re running on an embedded device with tight memory limits, or our array is gigantic and we simply can’t afford to double its footprint? Suddenly, the naive O(N) solution might actually be reasonable.

That kind of thinking must be on the back of your head every single time you solve an engineering problem: How does the system scale? What are the constraints?

Know your units

If we think of construction engineers, they may have their abstractions, but ultimately there are bricks, cement and beams supporting their buildings. I’ve observed that in software, it is very common practice, especially for early engineers, to abstract things out and take certain behaviors for granted. We often forget that we’re also managing something tangible: the bit.

Our unit, as software engineers, is the bit. The bit is the thing that we’re creating and moving around, that ultimately resides in the computer’s primary and secondary memory, in processors’ registers, and we often don’t have an infinite amount of compute. There are limitations to what we can achieve in terms of performance, scale and complexity, exactly like the bricks for a building.

It is important that we don’t lose sight of these requirements, especially when assembling a solution for large scale. Every data structure and algorithm is a tradeoff. Every line of code is a small bet between time, memory, complexity, and readability. Knowing your units and how your system should behave is a must.

The End

These are the things that make engineering really interesting to me, and I hope to you too. Next time you tackle a problem, don’t just look right away for an answer. Ask what happens at scale. Look for the tradeoffs. I think that kind of judgment is what differentiates the good from the great in software engineering.

I hope you liked this post and may the code be with you!