Learn
Practice
Interview
Resources
Newsletter
F
Toggle theme
0
F
0
Toggle menu
Animations
← Back to All Animations
Count of Range Sum
Bookmark
Input
Standard
Medium
Small
All Positive
All Negative
Custom
nums
=
[-2, 5, -1]
,
lower
=
-2
,
upper
=
2
sum ∈ [-2, 2]
count = 0
0
1
2
3
0
-2
3
2
count subarray sums that fall in the target range
sum ∈ [-2, 2]
count = 0
0
1
2
3
0
-2
3
2
count subarray sums that fall in the target range
sum ∈ [-2, 2]
count = 0
0
1
2
3
0
-2
3
2
single element — already a sorted run
sum ∈ [-2, 2]
count = 0
[-4, 0]
0
1
2
3
0
-2
3
2
+1
j
lo
hi
prefix[hi] ≤ 0 →
hi++
sum ∈ [-2, 2]
count = 1
0
1
2
3
-2
0
3
2
half is now a
sorted run
sum ∈ [-2, 2]
count = 1
0
1
2
3
-2
0
3
2
recurse: sort the
right half
sum ∈ [-2, 2]
count = 1
0
1
2
3
-2
0
3
2
merge the two sorted halves back together
sum ∈ [-2, 2]
count = 1
0
1
2
3
-2
0
2
3
for each j on the right, count valid prefix[i] on the left
sum ∈ [-2, 2]
count = 3
[1, 5]
0
1
2
3
-2
0
2
3
j
lo
hi
prefix[3] = 3
→ need prefix[i] ∈
[1, 5]
sum ∈ [-2, 2]
count = 3
0
1
2
3
-2
0
2
3
temp
-2
take smaller from the
left run
sum ∈ [-2, 2]
count = 3
0
1
2
3
-2
0
2
3
count = 3
algo
master
.
io
Step:
Start: Count range sums using modified merge sort on prefix sums
0 / 50
Input
Standard
Medium
Small
All Positive
All Negative
Custom
nums
=
[-2, 5, -1]
,
lower
=
-2
,
upper
=
2
0 / 50
algo
master
.
io
Step:
Start: Count range sums using modified merge sort on prefix sums
