LeetCode 303: Range Sum Query - Immutable Solution in Python – A Step-by-Step Guide

What Is LeetCode 303: Range Sum Query - Immutable?

In LeetCode 303: Range Sum Query - Immutable, you’re tasked with creating a NumArray class with two methods: __init__(nums) to set up an immutable array, and sumRange(left, right) to return the sum of elements from index left to right (inclusive). The array won’t change, but sumRange will be called many times. For example, with [1, 2, 3, 4], sumRange(1, 3) returns 2 + 3 + 4 = 9. This problem tests your ability to preprocess data for quick queries, sharing a vibe with prefix sum challenges like LeetCode 304: Range Sum Query 2D - Immutable.

Problem Statement

• Input: An integer array nums for __init__; integers left and right for sumRange.
• Output: A class with:
• __init__(nums): Initializes with array (returns nothing).
• sumRange(left, right): Returns sum from left to right.
• Rules: Array is immutable; sumRange called multiple times; indices are valid.

Constraints

• nums length: 1 to 10⁴.
• Values: -10⁵ to 10⁵.
• left and right: 0 ≤ left ≤ right < nums.length.
• Up to 10⁴ sumRange calls.

Examples

• Input: ["NumArray", "sumRange", "sumRange", "sumRange"], [[[-2,0,3,-5,2,-1]], [0,2], [2,5], [0,5]]
• Output: [null, 1, -1, -3] (-2+0+3=1, 3-5+2-1=-1, -2+0+3-5+2-1=-3)
• Input: ["NumArray", "sumRange"], [[[1,2,3]], [0,2]]
• Output: [null, 6] (1+2+3=6)
• Input: ["NumArray", "sumRange"], [[[5]], [0,0]]
• Output: [null, 5]

Understanding the Problem: Summing Ranges Fast

To solve LeetCode 303: Range Sum Query - Immutable in Python, we need a class that takes an array once and then quickly sums any range from left to right. For [1, 2, 3, 4], sumRange(1, 2) is 2 + 3 = 5, and we might get asked this a lot. Adding numbers each time we’re asked would work but be slow with many calls. Instead, we’ll use:

• Best Solution (Prefix Sum Array): O(n) init, O(1) sumRange, O(n) space—fast and efficient.
• Alternative Solution (Brute Force Summation): O(n) init, O(n) sumRange, O(n) space—simple but slow.

Let’s dive into the prefix sum solution with a friendly breakdown that’s easy to follow.

Best Solution: Prefix Sum Array

Why This Is the Best Solution

The prefix sum array is the top choice for LeetCode 303 because it’s super efficient—O(n) time to set up during __init__, O(1) time for each sumRange call, and O(n) space. It precomputes cumulative sums so any range sum is just a quick subtraction. It’s like keeping a running total ready to go—perfect for tons of range queries!

How It Works

Let’s picture this like a running tally:

• Step 1: Build Prefix Sums:
• Create an array prefix where prefix[i] = sum of nums[0] to nums[i-1].
• For [1, 2, 3], prefix = [0, 1, 3, 6] (0, 1, 1+2, 1+2+3).
• Step 2: Compute Range Sum:
• Sum from left to right = prefix[right + 1] - prefix[left].
• For left=1, right=2: prefix[3] - prefix[1] = 6 - 1 = 5 (2 + 3).
• Step 3: Why It Works:
• Prefix sums store all sums up to each point.
• Subtracting prefix[left] from prefix[right + 1] cancels out everything before left, leaving the range sum.
• O(1) lookup beats adding each time.

It’s like a pre-made sum chart—subtract and go!

Step-by-Step Example

Example: nums = [-2, 0, 3, -5, 2, -1]

• Init:
• prefix = [0, -2, -2, 1, -4, -2, -3]:
• 0 (start), -2, -2+0, -2+0+3, -2+0+3-5, -2+0+3-5+2, -2+0+3-5+2-1.
• sumRange(0, 2):
• prefix[3] - prefix[0] = 1 - 0 = 1 (-2 + 0 + 3).
• sumRange(2, 5):
• prefix[6] - prefix[2] = -3 - (-2) = -1 (3 - 5 + 2 - 1).
• sumRange(0, 5):
• prefix[6] - prefix[0] = -3 - 0 = -3 (-2 + 0 + 3 - 5 + 2 - 1).
• Result: Works fast every time!

Code with Detailed Line-by-Line Explanation

Here’s the Python code, broken down so it’s easy to follow:

Copy codeclass NumArray:
    def __init__(self, nums: List[int]):
        # Step 1: Build prefix sum array
        self.prefix = [0] * (len(nums) + 1)  # Extra 0 at start
        for i in range(len(nums)):
            self.prefix[i + 1] = self.prefix[i] + nums[i]  # Cumulative sum

    def sumRange(self, left: int, right: int) -> int:
        # Step 2: Return range sum with subtraction
        return self.prefix[right + 1] - self.prefix[left]

• Line 4-6: In __init__:
• Create prefix with size n+1, starting with 0.
• Fill it: prefix[i+1] = prefix[i] + nums[i], e.g., [0, 1, 3, 6] for [1, 2, 3].
• Line 9-10: In sumRange:
• Return prefix[right + 1] - prefix[left], e.g., right=2, left=1 → 6 - 1 = 5.
• Time Complexity: O(n) init, O(1) sumRange.
• Space Complexity: O(n)—prefix array.

This is like a sum shortcut—precompute and subtract!

Alternative Solution: Brute Force Summation

Why an Alternative Approach?

Brute force summation stores the array as-is—O(1) init, O(n) sumRange, O(n) space. It’s simpler but slower, adding numbers each time sumRange is called, like doing the math on the fly—great for understanding but not for speed with many queries.

How It Works

Let’s think of this as a manual tally:

• Step 1: Store the array in __init__.
• Step 2: For sumRange, loop from left to right, adding each number.
• Step 3: Return the sum.

It’s like counting coins one-by-one each time!

Step-by-Step Example

Example: nums = [1, 2, 3, 4]

• Init: nums = [1, 2, 3, 4].
• sumRange(1, 2):
• 2 + 3 = 5.
• sumRange(0, 3):
• 1 + 2 + 3 + 4 = 10.
• Result: Works, but slow with many calls.

Code for Brute Force Approach

Copy codeclass NumArray:
    def __init__(self, nums: List[int]):
        self.nums = nums  # Just store the array

    def sumRange(self, left: int, right: int) -> int:
        total = 0
        for i in range(left, right + 1):  # Add from left to right
            total += self.nums[i]
        return total

• Time Complexity: O(1) init, O(n) sumRange.
• Space Complexity: O(n)—stores nums.

It’s a slow count each time!

Comparing the Two Solutions

• Prefix Sum (Best):
• Pros: O(n) init, O(1) sumRange, O(n) space, fast queries.
• Cons: Precomputation effort.
• Brute Force (Alternative):
• Pros: O(1) init, O(n) sumRange, O(n) space, simple setup.
• Cons: Slow queries.

Prefix sum wins for many calls.

Additional Examples and Edge Cases

• [1], (0,0): 1.
• [-1, 1], (0,1): 0.
• [2, -2, 2], (1,2): 0.

Prefix sum is faster.

Complexity Breakdown

• Prefix Sum: Init O(n), SumRange O(1), Space O(n).
• Brute Force: Init O(1), SumRange O(n), Space O(n).

Prefix sum rules.

Key Takeaways

• Prefix Sum: Precompute for speed—smart!
• Brute Force: Add on demand—clear!
• Ranges: Prep beats repeat.
• Python Tip: Arrays rock—see [Python Basics](/python/basics).

Final Thoughts: Sum It Up

LeetCode 303: Range Sum Query - Immutable in Python is a handy array challenge. Prefix sums zip through queries, while brute force shows the basics. Want more? Try LeetCode 304: Range Sum Query 2D - Immutable or LeetCode 560: Subarray Sum Equals K. Ready to tally? Head to Solve LeetCode 303 on LeetCode and sum those ranges today!