Algorithms
Easy
2824
2917
Count Pairs Whose Sum is Less than Target
count-pairs-whose-sum-is-less-than-target
"""
Given a 0-indexed integer array nums of length n and an integer target, return the number of pairs (i, j) where 0 <= i < j < n and nums[i] + nums[j] < target.

Example 1:

Input: nums = [-1,1,2,3,1], target = 2
Output: 3
Explanation: There are 3 pairs of indices that satisfy the conditions in the statement:
- (0, 1) since 0 < 1 and nums[0] + nums[1] = 0 < target
- (0, 2) since 0 < 2 and nums[0] + nums[2] = 1 < target
- (0, 4) since 0 < 4 and nums[0] + nums[4] = 0 < target
Note that (0, 3) is not counted since nums[0] + nums[3] is not strictly less than the target.

Example 2:

Input: nums = [-6,2,5,-2,-7,-1,3], target = -2
Output: 10
Explanation: There are 10 pairs of indices that satisfy the conditions in the statement:
- (0, 1) since 0 < 1 and nums[0] + nums[1] = -4 < target
- (0, 3) since 0 < 3 and nums[0] + nums[3] = -8 < target
- (0, 4) since 0 < 4 and nums[0] + nums[4] = -13 < target
- (0, 5) since 0 < 5 and nums[0] + nums[5] = -7 < target
- (0, 6) since 0 < 6 and nums[0] + nums[6] = -3 < target
- (1, 4) since 1 < 4 and nums[1] + nums[4] = -5 < target
- (3, 4) since 3 < 4 and nums[3] + nums[4] = -9 < target
- (3, 5) since 3 < 5 and nums[3] + nums[5] = -3 < target
- (4, 5) since 4 < 5 and nums[4] + nums[5] = -8 < target
- (4, 6) since 4 < 6 and nums[4] + nums[6] = -4 < target


Constraints:

 * 1 <= nums.length == n <= 50
 * -50 <= nums[i], target <= 50
"""
class Solution:
    def countPairs(self, nums: List[int], target: int) -> int:
        
Given a 0-indexed integer array nums of length n and an integer target, return the number of pairs (i, j) where 0 <= i < j < n and nums[i] + nums[j] < target.

Example 1:

Input: nums = [-1,1,2,3,1], target = 2
Output: 3
Explanation: There are 3 pairs of indices that satisfy the conditions in the statement:
- (0, 1) since 0 < 1 and nums[0] + nums[1] = 0 < target
- (0, 2) since 0 < 2 and nums[0] + nums[2] = 1 < target
- (0, 4) since 0 < 4 and nums[0] + nums[4] = 0 < target
Note that (0, 3) is not counted since nums[0] + nums[3] is not strictly less than the target.

Example 2:

Input: nums = [-6,2,5,-2,-7,-1,3], target = -2
Output: 10
Explanation: There are 10 pairs of indices that satisfy the conditions in the statement:
- (0, 1) since 0 < 1 and nums[0] + nums[1] = -4 < target
- (0, 3) since 0 < 3 and nums[0] + nums[3] = -8 < target
- (0, 4) since 0 < 4 and nums[0] + nums[4] = -13 < target
- (0, 5) since 0 < 5 and nums[0] + nums[5] = -7 < target
- (0, 6) since 0 < 6 and nums[0] + nums[6] = -3 < target
- (1, 4) since 1 < 4 and nums[1] + nums[4] = -5 < target
- (3, 4) since 3 < 4 and nums[3] + nums[4] = -9 < target
- (3, 5) since 3 < 5 and nums[3] + nums[5] = -3 < target
- (4, 5) since 4 < 5 and nums[4] + nums[5] = -8 < target
- (4, 6) since 4 < 6 and nums[4] + nums[6] = -4 < target


Constraints:

 * 1 <= nums.length == n <= 50
 * -50 <= nums[i], target <= 50


Please complete the code below to solve above prblem:
```python
class Solution:
    def countPairs(self, nums: List[int], target: int) -> int:
        
```

my_solution = Solution()

test_input = { "nums": [-1,1,2,3,1], "target": 2 }
assert my_solution.countPairs(**test_input) == 3

test_input = { "nums": [-6,2,5,-2,-7,-1,3], "target": -2 }
assert my_solution.countPairs(**test_input) == 10

test_input = { "nums": [9,-5,-5,5,-5,-4,-6,6,-6], "target": 3 }
assert my_solution.countPairs(**test_input) == 27

test_input = { "nums": [-8,-5,5,-4,10], "target": 2 }
assert my_solution.countPairs(**test_input) == 6

test_input = { "nums": [-5,0,-7,-1,9,8,-9,9], "target": -14 }
assert my_solution.countPairs(**test_input) == 1

test_input = { "nums": [6,-1,7,4,2,3], "target": 8 }
assert my_solution.countPairs(**test_input) == 8

test_input = { "nums": [2,8,2,8,7], "target": 10 }
assert my_solution.countPairs(**test_input) == 3

test_input = { "nums": [-6,1,1,-1,-10,-7,1,-5,-4,0], "target": -15 }
assert my_solution.countPairs(**test_input) == 2

test_input = { "nums": [10,-2,-1,7,8,5,3,-4,-9], "target": -10 }
assert my_solution.countPairs(**test_input) == 2

test_input = { "nums": [3,8,-3,4,10,-6], "target": 1 }
assert my_solution.countPairs(**test_input) == 4

test_input = { "nums": [-4,-6,-7,8], "target": -13 }
assert my_solution.countPairs(**test_input) == 0

test_input = { "nums": [-4,0,10,8,-2], "target": 0 }
assert my_solution.countPairs(**test_input) == 3

test_input = { "nums": [-8,-5,-3,1,-7], "target": -6 }
assert my_solution.countPairs(**test_input) == 7

test_input = { "nums": [4,-8,-2,5,2,-9,6,5,-4], "target": -4 }
assert my_solution.countPairs(**test_input) == 9

test_input = { "nums": [-1,-5,4,4,-10], "target": -6 }
assert my_solution.countPairs(**test_input) == 2

test_input = { "nums": [-5,4,-6,-5,-10,-1,10,3], "target": 6 }
assert my_solution.countPairs(**test_input) == 24

test_input = { "nums": [-9,6,-4,10,1,8], "target": 11 }
assert my_solution.countPairs(**test_input) == 11

test_input = { "nums": [-10,-6,-8,-9,6,6,-6,-6,-3], "target": -2 }
assert my_solution.countPairs(**test_input) == 25

test_input = { "nums": [-7,7,6,-9,-4,10,8,-8,2,2], "target": -1 }
assert my_solution.countPairs(**test_input) == 17

test_input = { "nums": [0,-1,0,-6,-9], "target": -9 }
assert my_solution.countPairs(**test_input) == 2

test_input = { "nums": [8,-10,-9,6,-3,5,-2,-2,-7], "target": -4 }
assert my_solution.countPairs(**test_input) == 15

test_input = { "nums": [-1,3,8,3], "target": 2 }
assert my_solution.countPairs(**test_input) == 0

test_input = { "nums": [7,2,9,-10,-4,4,-3,0], "target": -20 }
assert my_solution.countPairs(**test_input) == 0

test_input = { "nums": [6,4,1,-7], "target": 7 }
assert my_solution.countPairs(**test_input) == 4

test_input = { "nums": [3,8,6,-2,6,1,7], "target": 7 }
assert my_solution.countPairs(**test_input) == 7

test_input = { "nums": [1,3,-10,5,-8,0,-5,-9], "target": -7 }
assert my_solution.countPairs(**test_input) == 11

test_input = { "nums": [-6,9,2,4,-9,2,4,-6,6,-9], "target": 11 }
assert my_solution.countPairs(**test_input) == 40

test_input = { "nums": [-10,-7,-5,-1,2,4,-6,6], "target": -3 }
assert my_solution.countPairs(**test_input) == 15

test_input = { "nums": [-1,0,1,9,-2,-8,-8,7], "target": 1 }
assert my_solution.countPairs(**test_input) == 16

test_input = { "nums": [1,9,3,2,9,-5,6,0,-6,6], "target": 9 }
assert my_solution.countPairs(**test_input) == 29

test_input = { "nums": [-3,-3,-4,1,4,9], "target": 6 }
assert my_solution.countPairs(**test_input) == 11

test_input = { "nums": [-10,3,-5,2,-10,7,9], "target": 4 }
assert my_solution.countPairs(**test_input) == 14

test_input = { "nums": [7,10,9,8,-9,1,-7,10,-4,2], "target": 4 }
assert my_solution.countPairs(**test_input) == 21

test_input = { "nums": [9,-9,0,5,4], "target": 14 }
assert my_solution.countPairs(**test_input) == 9

test_input = { "nums": [7,9,7,-10,-6,-8,-5], "target": 2 }
assert my_solution.countPairs(**test_input) == 14

test_input = { "nums": [8,-5,0,4], "target": 0 }
assert my_solution.countPairs(**test_input) == 2

test_input = { "nums": [5,2,-1,9,-1,-1], "target": 4 }
assert my_solution.countPairs(**test_input) == 6

test_input = { "nums": [-7,-4,3,9,10,5,-1,1,-7], "target": -4 }
assert my_solution.countPairs(**test_input) == 8

test_input = { "nums": [0,8,9,-9,8,-2,-1,2,5], "target": -1 }
assert my_solution.countPairs(**test_input) == 7

test_input = { "nums": [10,4,-9,8,-10,3], "target": -7 }
assert my_solution.countPairs(**test_input) == 1

test_input = { "nums": [-6,-6,6,-4,-5,-1,10,-8,1], "target": -13 }
assert my_solution.countPairs(**test_input) == 2

test_input = { "nums": [7,3,-4,1,-9,-8,10,4,-1], "target": -2 }
assert my_solution.countPairs(**test_input) == 13

test_input = { "nums": [4,3,-3,1,-3,-1], "target": -2 }
assert my_solution.countPairs(**test_input) == 3

test_input = { "nums": [10,-8,-9,-7,2,-10,4,7,6,6], "target": 14 }
assert my_solution.countPairs(**test_input) == 41

test_input = { "nums": [9,-5,-4,-2,9], "target": 4 }
assert my_solution.countPairs(**test_input) == 3

test_input = { "nums": [-1,2,-3,-4,-10,-8,2], "target": -1 }
assert my_solution.countPairs(**test_input) == 16

test_input = { "nums": [-8,-9,-10,0,-5,-5], "target": -15 }
assert my_solution.countPairs(**test_input) == 3

test_input = { "nums": [-8,9,-10,2,-10,-6,-1,-8], "target": -4 }
assert my_solution.countPairs(**test_input) == 19

test_input = { "nums": [4,-7,8,7,-4,3,7,7,-2,-10], "target": 4 }
assert my_solution.countPairs(**test_input) == 25

test_input = { "nums": [6,3,4,5,-4], "target": 0 }
assert my_solution.countPairs(**test_input) == 1

test_input = { "nums": [2,-4,5,3,7,10,9,-1,9,0], "target": 9 }
assert my_solution.countPairs(**test_input) == 23

test_input = { "nums": [-2,-5,9,-3,-8,5,-1,3,-9], "target": 1 }
assert my_solution.countPairs(**test_input) == 23

test_input = { "nums": [0,-2,-3,-1,-6,-7,3], "target": -10 }
assert my_solution.countPairs(**test_input) == 1

test_input = { "nums": [10,4,-3,9,-8,6], "target": 14 }
assert my_solution.countPairs(**test_input) == 11

test_input = { "nums": [-10,-6,6,-7,1,-7,9,3,1], "target": 15 }
assert my_solution.countPairs(**test_input) == 35

test_input = { "nums": [2,-3,-6,-2,5], "target": -4 }
assert my_solution.countPairs(**test_input) == 3

test_input = { "nums": [-10,-8,8,-2], "target": 0 }
assert my_solution.countPairs(**test_input) == 4

test_input = { "nums": [-2,2,-7,-5,1,6,8], "target": 0 }
assert my_solution.countPairs(**test_input) == 9

test_input = { "nums": [4,-4,-5,-8,9], "target": -10 }
assert my_solution.countPairs(**test_input) == 2

test_input = { "nums": [-5,-4,-6,-7,9,-10,0,4,9,-1], "target": -7 }
assert my_solution.countPairs(**test_input) == 13

test_input = { "nums": [-10,-6,6,-3,10,-6,4,-8], "target": -9 }
assert my_solution.countPairs(**test_input) == 8

test_input = { "nums": [-8,-1,-9,1], "target": -17 }
assert my_solution.countPairs(**test_input) == 0

test_input = { "nums": [6,-4,2,1,10,-1], "target": 1 }
assert my_solution.countPairs(**test_input) == 4

test_input = { "nums": [9,4,-8,8,9,-4], "target": -16 }
assert my_solution.countPairs(**test_input) == 0

test_input = { "nums": [9,-4,8,-9,-2,-2], "target": -11 }
assert my_solution.countPairs(**test_input) == 1

test_input = { "nums": [-7,1,3,7,6,3], "target": 10 }
assert my_solution.countPairs(**test_input) == 12

test_input = { "nums": [10,10,-2,-4], "target": 8 }
assert my_solution.countPairs(**test_input) == 3

test_input = { "nums": [-3,2,6,-6,9], "target": 3 }
assert my_solution.countPairs(**test_input) == 4

test_input = { "nums": [5,0,2,4,2,-7], "target": 2 }
assert my_solution.countPairs(**test_input) == 5

test_input = { "nums": [4,-5,-4,-2,-9,-6,-10,-10,2,-8], "target": -19 }
assert my_solution.countPairs(**test_input) == 1

test_input = { "nums": [-10,10,-9,-2,3,-2,-7,-1,-6,7], "target": -17 }
assert my_solution.countPairs(**test_input) == 1

test_input = { "nums": [-9,-9,3,7,-9,-10,2,3,-4], "target": -13 }
assert my_solution.countPairs(**test_input) == 7

test_input = { "nums": [-5,-4,-10,7], "target": 14 }
assert my_solution.countPairs(**test_input) == 6

test_input = { "nums": [-3,4,-6,-6,1,-10,-1,-8], "target": -11 }
assert my_solution.countPairs(**test_input) == 7

test_input = { "nums": [-7,1,-5,8,-7,-3,2,-2,-2,7], "target": -5 }
assert my_solution.countPairs(**test_input) == 14

test_input = { "nums": [8,0,-8,-8,-1,5], "target": 0 }
assert my_solution.countPairs(**test_input) == 8

test_input = { "nums": [9,7,2,4,3], "target": 7 }
assert my_solution.countPairs(**test_input) == 2

test_input = { "nums": [8,-1,-5,7,7,5,-6,2], "target": -2 }
assert my_solution.countPairs(**test_input) == 5

test_input = { "nums": [-1,3,3,3,9], "target": 8 }
assert my_solution.countPairs(**test_input) == 6

test_input = { "nums": [-8,0,-1,-6,-9,2,3,1], "target": -9 }
assert my_solution.countPairs(**test_input) == 4

test_input = { "nums": [3,-3,-7,-6,-5,-2], "target": -2 }
assert my_solution.countPairs(**test_input) == 12

test_input = { "nums": [3,6,0,-4,-2,5], "target": -6 }
assert my_solution.countPairs(**test_input) == 0

test_input = { "nums": [-8,9,2,5,9,-4,3], "target": 6 }
assert my_solution.countPairs(**test_input) == 12

test_input = { "nums": [0,-6,-5,-8,-4,0,7], "target": 7 }
assert my_solution.countPairs(**test_input) == 19

test_input = { "nums": [0,9,2,-4], "target": -8 }
assert my_solution.countPairs(**test_input) == 0

test_input = { "nums": [-7,9,-3,-5,-9,-3,-8,-2,1,2], "target": -8 }
assert my_solution.countPairs(**test_input) == 15

test_input = { "nums": [4,10,-7,0,-3,5,9,6,8,-4], "target": 13 }
assert my_solution.countPairs(**test_input) == 34

test_input = { "nums": [2,-6,0,5,-9,-8,6,5], "target": -3 }
assert my_solution.countPairs(**test_input) == 11

test_input = { "nums": [-4,6,-2,10,-5,-7,-8,-1], "target": -5 }
assert my_solution.countPairs(**test_input) == 13

test_input = { "nums": [10,4,8,-1,9,-5,-1,-7,-9], "target": 19 }
assert my_solution.countPairs(**test_input) == 35

test_input = { "nums": [-6,5,3,-2,0,3,-7,-7], "target": -8 }
assert my_solution.countPairs(**test_input) == 5

test_input = { "nums": [-3,-1,7,4,-10,-6,2], "target": -4 }
assert my_solution.countPairs(**test_input) == 7

test_input = { "nums": [-7,8,3,-1,2,1,-10], "target": -7 }
assert my_solution.countPairs(**test_input) == 5

test_input = { "nums": [7,-3,-5,9,-10,-1,-3,-3,-3,1], "target": 6 }
assert my_solution.countPairs(**test_input) == 36

test_input = { "nums": [-5,-10,-7,-3,-2,-2], "target": -15 }
assert my_solution.countPairs(**test_input) == 1

test_input = { "nums": [-4,6,-9,-8,-9,-9], "target": -17 }
assert my_solution.countPairs(**test_input) == 3

test_input = { "nums": [-3,-8,-6,-4,-8,-10,-2,5,-2], "target": 1 }
assert my_solution.countPairs(**test_input) == 32

test_input = { "nums": [1,1,-6,8,2,10,-7,-9,-9], "target": -7 }
assert my_solution.countPairs(**test_input) == 10

test_input = { "nums": [-9,-6,-3,5,-4], "target": 2 }
assert my_solution.countPairs(**test_input) == 9

test_input = { "nums": [-5,10,-5,1,7,-8,8,-6,-6], "target": 2 }
assert my_solution.countPairs(**test_input) == 19