Learn
Practice
Interview
Resources
Newsletter
F
Toggle theme
0
F
0
Toggle menu
Animations
← Back to All Animations
Reverse Pairs
Bookmark
Input
Standard
Medium
Small
Large
No Pairs
All Same
Custom
arr
=
[1, 3, 2, 3, 1]
nums[i] > 2·nums[j]
pairs = 0
0
1
2
3
4
1
3
2
3
1
count pairs i < j with nums[i] > 2·nums[j]
nums[i] > 2·nums[j]
pairs = 0
0
1
2
3
4
1
3
2
3
1
count pairs i < j with nums[i] > 2·nums[j]
nums[i] > 2·nums[j]
pairs = 0
0
1
2
3
4
1
3
2
3
1
recurse: sort the
right half
nums[i] > 2·nums[j]
pairs = 0
0
1
2
3
4
1
3
2
3
1
temp
1
3
copy the remaining run across
nums[i] > 2·nums[j]
pairs = 0
arr[i]/2 = 1.5
0
1
2
3
4
1
3
2
3
1
i
j
3
> 2·
2
=
4
?
no
nums[i] > 2·nums[j]
pairs = 0
0
1
2
3
4
1
2
3
3
1
half is now a
sorted run
nums[i] > 2·nums[j]
pairs = 0
0
1
2
3
4
1
2
3
3
1
single element — already a sorted run
nums[i] > 2·nums[j]
pairs = 1
0
1
2
3
4
1
2
3
3
1
temp
1
3
copy the remaining run across
nums[i] > 2·nums[j]
pairs = 1
arr[i]/2 = 1.5
0
1
2
3
4
1
2
3
1
3
+1
i
j
3
> 2·
1
=
2
?
yes
nums[i] > 2·nums[j]
pairs = 2
0
1
2
3
4
1
2
3
1
3
temp
1
1
take smaller from the
right run
nums[i] > 2·nums[j]
pairs = 2
0
1
2
3
4
1
1
2
3
3
reverse pairs = 2
algo
master
.
io
Step:
Start: Count reverse pairs using modified merge sort
0 / 71
Input
Standard
Medium
Small
Large
No Pairs
All Same
Custom
arr
=
[1, 3, 2, 3, 1]
0 / 71
algo
master
.
io
Step:
Start: Count reverse pairs using modified merge sort
