Count valid pairs without listing them
Updated
Counting adds 1 (or a slice of pairs) when a pair is valid and never stores the pair. The answer is an integer.
What to focus on
count starts at 0. After the scan, count is how many pairs passed. On a sorted array, a[L]+a[R] ≤ target lets you add (R-L) at once, then L += 1.
Worked examples
sum ≤ 10
a = [1, 4, 9], target=10- L=0, R=2: 1+9=10, add 2, L=1
- L=1, R=2: 4+9=13 > 10, R=1
- L==R stop
Result: count = 2
none
a = [1, 4, 9], target=4- L=0, R=2: 1+9=10 > 4, R=1
- 1+4=5 > 4, R=0
- L==R
Result: count = 0
empty
a = []- no two indices
- count stays 0
Result: count = 0
Try it
Write countPairs(a, target). a is a sorted array of integers. target is the pair-sum limit. L is the left index. R is the right index. Return an integer, not a list of pairs. count starts at 0. On [1, 4, 9] target 10 returns 2. Target 5 returns 1. On [1, 2, 3] target 10 returns 3.
a is sorted non-decreasing, length ≥ 2.