Count Pairs Below Threshold

EASY10 pts

You are given an integer array nums containing n elements (0-indexed) and an integer threshold. Your task is to determine how many index pairs (i, j) exist such that:

The first index is strictly smaller than the second index: 0 ≤ i < j < n
The sum of the elements at these indices is strictly less than the threshold: nums[i] + nums[j] < threshold

Return the total count of all such valid pairs that satisfy both conditions.

Key Observations:

Each pair is counted only once; specifically, if (i, j) is valid, we do not also count (j, i) because we require i < j.
The same element can participate in multiple valid pairs with different partners.
Both the array elements and the threshold can be negative, zero, or positive.

Example

Input

nums = [-1,1,2,3,1]
threshold = 2

Output

3

Explanation

There are 3 pairs of indices that satisfy both conditions:

Pair (0, 1): indices 0 < 1, and nums[0] + nums[1] = -1 + 1 = 0 < 2 ✓
Pair (0, 2): indices 0 < 2, and nums[0] + nums[2] = -1 + 2 = 1 < 2 ✓
Pair (0, 4): indices 0 < 4, and nums[0] + nums[4] = -1 + 1 = 0 < 2 ✓ Note that pair (0, 3) is not counted because nums[0] + nums[3] = -1 + 3 = 2, which is not strictly less than the threshold of 2.

Example

Input

nums = [-6,2,5,-2,-7,-1,3]
threshold = -2

Output

10

Explanation

There are 10 pairs whose sum is strictly below -2:

(0,1): -6 + 2 = -4 < -2 ✓
(0,3): -6 + (-2) = -8 < -2 ✓
(0,4): -6 + (-7) = -13 < -2 ✓
(0,5): -6 + (-1) = -7 < -2 ✓
(0,6): -6 + 3 = -3 < -2 ✓
(1,4): 2 + (-7) = -5 < -2 ✓
(3,4): -2 + (-7) = -9 < -2 ✓
(3,5): -2 + (-1) = -3 < -2 ✓
(4,5): -7 + (-1) = -8 < -2 ✓
(4,6): -7 + 3 = -4 < -2 ✓

Example

Input

nums = [1,2,3,4,5]
threshold = 5

Output

2

Explanation

Only 2 pairs have sums strictly below the threshold of 5:

(0,1): 1 + 2 = 3 < 5 ✓
(0,2): 1 + 3 = 4 < 5 ✓ All other pairs produce sums that are greater than or equal to 5.

Accepted0/0·0% Acceptance

Constraints

1 ≤ nums.length ≤ 50
-50 ≤ nums[i] ≤ 50
-50 ≤ threshold ≤ 50

Code

Visualizer

Solutions

14px

Test Cases3

Results

Submissions

nums =

[-1,1,2,3,1]

threshold =

Count Pairs Below Threshold

Hints

Count Pairs Below Threshold

Hints