HardNo. 0327
Count of Range Sum — LeetCode 327 Python Solution
- Pattern
- Monotonic Stack
- Topics
- Binary Indexed Tree, Segment Tree, Array, Binary Search, Divide and Conquer, Ordered Set, Merge Sort
- Reading time
- 5 min
- Source
- leetcode.com
The problem
Given an integer array nums and two integers lower and upper, return the number of range sums that lie in [lower, upper] inclusive. Range sum S(i, j) is defined as the sum of the elements in nums between indices i and j inclusive, where i <= j.
Example
- Input
- nums = [-2,5,-1], lower = -2, upper = 2
- Output
- 3
- Explanation
- The three ranges are: [0,0], [2,2], and [0,2] and their respective sums are: -2, -1, 2.
Python solution
class BinaryIndexedTree:
def __init__(self, n):
self.n = n
self.c = [0] * (n + 1)
def update(self, x, v):
while x <= self.n:
self.c[x] += v
x += x & -x
def query(self, x):
s = 0
while x > 0:
s += self.c[x]
x -= x & -x
return s
class Solution:
def countRangeSum(self, nums: List[int], lower: int, upper: int) -> int:
s = list(accumulate(nums, initial=0))
arr = sorted(set(v for x in s for v in (x, x - lower, x - upper)))
tree = BinaryIndexedTree(len(arr))
ans = 0
for x in s:
l = bisect_left(arr, x - upper) + 1
r = bisect_left(arr, x - lower) + 1
ans += tree.query(r) - tree.query(l - 1)
tree.update(bisect_left(arr, x) + 1, 1)
return ansComplexity
- Time
- O(log n) or O(n log n)
- Space · auxiliary
- O(1)
Pattern: Monotonic Stack
Answer "what is the next greater element" for every position in one pass. LeetCode 327. Count of Range Sum is filed here because the reference solution below belongs to the algorithm family this hub collects, even though its LeetCode tags point elsewhere.
The monotonic stack guide has the Python template for the pattern and the 225 LeetCode problems that use it.
Related problems
| No. | Problem | Difficulty |
|---|---|---|
| 0315 | Count of Smaller Numbers After Self | Hard |
| 0493 | Reverse Pairs | Hard |
| 1649 | Create Sorted Array through Instructions | Hard |
| 2179 | Count Good Triplets in an Array | Hard |
| 2426 | Number of Pairs Satisfying Inequality | Hard |
| 2659 | Make Array Empty | Hard |
Frequently asked questions
- How hard is LeetCode 327. Count of Range Sum?
LeetCode 327. Count of Range Sum is rated Hard on LeetCode.
- What topics does LeetCode 327. Count of Range Sum cover?
LeetCode 327. Count of Range Sum is tagged Binary Indexed Tree, Segment Tree, Array, Binary Search, Divide and Conquer, Ordered Set and Merge Sort on LeetCode.