LeetCode 327: Count of Range Sum Solution in Python – A Step-by-Step Guide

What Is LeetCode 327: Count of Range Sum?

In LeetCode 327: Count of Range Sum, you’re given an integer array nums and two integers lower and upper. Your task is to count the number of contiguous subarrays whose sum falls within the inclusive range [lower, upper]. For example, with nums = [-2,5,-1], lower = -2, upper = 2, there are 3 subarrays: [-2], [-2,5,-1], and [5,-1]. This problem tests your ability to handle subarray sums efficiently, connecting to concepts in LeetCode 560: Subarray Sum Equals K.

Problem Statement

• Input: An integer array nums and integers lower and upper.
• Output: An integer—the number of subarrays with sum in [lower, upper].
• Rules:
• Subarrays must be contiguous.
• Sum must satisfy lower <= sum <= upper.
• Count all valid subarrays.

Constraints

• 1 <= nums.length <= 10⁵
• -2³¹ <= nums[i] <= 2³¹ - 1
• -10⁵ <= lower <= upper <= 10⁵

Examples

• Input: nums = [-2,5,-1], lower = -2, upper = 2
• Output: 3 (Subarrays: [-2], [-2,5,-1], [5,-1])
• Input: nums = [0], lower = 0, upper = 0
• Output: 1 (Subarray: [0])
• Input: nums = [1,2,3], lower = 5, upper = 6
• Output: 1 (Subarray: [2,3])

Understanding the Problem: Counting Range Sums

To solve LeetCode 327: Count of Range Sum in Python, we need to count all contiguous subarrays in nums with sums between lower and upper. A naive approach—computing every subarray sum—is O(n²), too slow for 10⁵ elements. Instead, we’ll use:

• Best Solution (Merge Sort): O(n log n) time, O(n) space—fast and scalable.
• Alternative Solution (Brute Force): O(n²) time, O(1) space—simple but inefficient.

Let’s start with the merge sort solution, explained in a beginner-friendly way.

Best Solution: Merge Sort with Prefix Sums

Why This Is the Best Solution

The merge sort approach is the top choice for LeetCode 327 because it’s efficient—O(n log n) time, O(n) space—and cleverly uses prefix sums with a divide-and-conquer strategy. It counts valid subarray sums during the merge step, avoiding redundant calculations. It’s like sorting and tallying treasures in one go—smart and swift!

How It Works

Think of this as a sorted sum counter:

• Step 1: Compute Prefix Sums:
• prefix[i] = sum of elements from 0 to i-1.
• Subarray sum from i to j = prefix[j+1] - prefix[i].
• Step 2: Merge Sort:
• Split array, sort recursively.
• During merge, count pairs where lower <= prefix[j] - prefix[i] <= upper.
• Step 3: Accumulate Count:
• Sum counts across merges.
• Step 4: Why It Works:
• Sorted prefixes allow range counting in O(n) per merge.
• O(log n) merge steps total O(n log n).

It’s like organizing and counting in a single sweep!

Step-by-Step Example

Example: nums = [-2,5,-1], lower = -2, upper = 2

• Prefix Sums: [0, -2, 3, 2] (0 is sum before first element)
• Merge Sort:
• Split: [0, -2] and [3, 2]
• Left: [0, -2] → Sorted: [-2, 0], Count: 0
• Right: [3, 2] → Sorted: [2, 3], Count: 0
• Merge: [-2, 0, 2, 3]
• For i=-2: j=0 (0-(-2)=2), j=2 (2-(-2)=4), Count=1
• For i=0: j=2 (2-0=2), j=3 (3-0=3), Count=2
• For i=2: j=3 (3-2=1), Count=1
• Total = 3
• Result: 3

Code with Detailed Line-by-Line Explanation

Copy codeclass Solution:
    def countRangeSum(self, nums: List[int], lower: int, upper: int) -> int:
        # Compute prefix sums
        prefix = [0] * (len(nums) + 1)
        for i in range(len(nums)):
            prefix[i + 1] = prefix[i] + nums[i]

        # Merge sort with counting
        def merge_sort(left, right):
            if left >= right:
                return 0
            mid = (left + right) // 2
            count = merge_sort(left, mid) + merge_sort(mid + 1, right)

            # Count valid ranges during merge
            i = j = mid + 1
            for l in range(left, mid + 1):
                while i <= right and prefix[i] - prefix[l] < lower:
                    i += 1
                while j <= right and prefix[j] - prefix[l] <= upper:
                    j += 1
                count += j - i

            # Merge sorted halves
            temp = []
            p1, p2 = left, mid + 1
            while p1 <= mid or p2 <= right:
                if p1 > mid:
                    temp.append(prefix[p2])
                    p2 += 1
                elif p2 > right:
                    temp.append(prefix[p1])
                    p1 += 1
                elif prefix[p1] <= prefix[p2]:
                    temp.append(prefix[p1])
                    p1 += 1
                else:
                    temp.append(prefix[p2])
                    p2 += 1
            prefix[left:right + 1] = temp
            return count

        return merge_sort(0, len(nums))

• Lines 3-6: Build prefix sum array.
• Lines 9-37: Merge sort:
• Recursively split and count.
• During merge, count ranges where lower <= diff <= upper.
• Merge sorted halves in-place.
• Time Complexity: O(n log n)—merge sort with O(n) counting per merge.
• Space Complexity: O(n)—prefix array and temp storage.

This is like a sum-counting maestro—fast and precise!

Alternative Solution: Brute Force

Why an Alternative Approach?

The brute-force approach—O(n²) time, O(1) space—computes the sum of every subarray explicitly and checks if it falls within [lower, upper]. It’s simple to understand but too slow for large inputs, making it a baseline for learning. It’s like checking every treasure chest—thorough but tedious!

How It Works

Check all subarrays:

• Step 1: For each start index:
• Compute running sum to each end index.
• Step 2: Count if sum is in range.

Step-by-Step Example

Example: nums = [1,2], lower = 2, upper = 3

• Subarrays:
• [1]: 1
• [1,2]: 3 (Count 1)
• [2]: 2 (Count 1)
• Result: 2

Code for Brute Force Approach

Copy codeclass Solution:
    def countRangeSum(self, nums: List[int], lower: int, upper: int) -> int:
        count = 0
        for i in range(len(nums)):
            curr_sum = 0
            for j in range(i, len(nums)):
                curr_sum += nums[j]
                if lower <= curr_sum <= upper:
                    count += 1
        return count

• Time Complexity: O(n²)—nested loops.
• Space Complexity: O(1)—just variables.

It’s a sum-checking slogger—basic but slow!

Comparing the Two Solutions

• Merge Sort (Best):
• Pros: O(n log n) time, O(n) space, scalable.
• Cons: Complex logic.
• Brute Force (Alternative):
• Pros: O(n²) time, O(1) space, easy to follow.
• Cons: Too slow for large n.

Merge sort wins for performance.

Additional Examples and Edge Cases

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

Both handle these, but merge sort is faster.

Complexity Breakdown

• Merge Sort: Time O(n log n), Space O(n).
• Brute Force: Time O(n²), Space O(1).

Merge sort is the clear choice.

Key Takeaways

• Merge Sort: Sort and count—efficient!
• Brute Force: Check all—simple!
• Python: Arrays and logic shine—see [Python Basics](/python/basics).
• Sums: Ranges add challenge.

Final Thoughts: Tally the Ranges

LeetCode 327: Count of Range Sum in Python is a subarray-sum masterpiece. The merge sort solution offers speed and elegance, while brute force provides a baseline. Want more sum challenges? Try LeetCode 560: Subarray Sum Equals K or LeetCode 325: Maximum Size Subarray Sum Equals k. Ready to count? Head to Solve LeetCode 327 on LeetCode (premium) and sum up those ranges today!