# Count Pairs Whose Sum is Less than Target
**Difficulty:** EASY
[External](https://leetcode.com/problems/count-pairs-whose-sum-is-less-than-target)
Canonical: https://scaleengineer.com/dsa/problems/count-pairs-whose-sum-is-less-than-target
**Patterns:** [Two Pointers](https://scaleengineer.com/dsa/patterns/two-pointers)
**Algorithms:** [Binary Search](https://scaleengineer.com/algorithms/binary-search), [Sorting](https://scaleengineer.com/algorithms/sorting)
**Data structures:** Array
**Companies:** [Accenture](https://scaleengineer.com/companies/accenture), [josh technology](https://scaleengineer.com/companies/josh-technology)
---
## Problem
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`

# Approaches
## Brute Force Iteration
The most straightforward approach is to check every possible pair of indices `(i, j)` in the array such that `i < j`. For each pair, we calculate the sum of the corresponding elements and check if it's less than the `target`. If it is, we increment a counter.
**Time:** O(n^2), where `n` is the number of elements in `nums`. We iterate through all possible pairs `(i, j)` with `i < j`, which amounts to n * (n-1) / 2 comparisons. · **Space:** O(1), as we only use a constant amount of extra space for the counter and loop variables.
**Pros:** Simple to understand and implement.; It does not require any modification of the input array.; Works correctly and is acceptable for the given constraints (`n <= 50`).
**Cons:** Inefficient for large input sizes due to its quadratic time complexity.; It performs many redundant calculations.
### Explanation
This method involves using nested loops to generate all unique pairs of elements. The outer loop runs from the first element to the second-to-last element, and the inner loop runs from the element after the current outer loop element to the last element. This ensures that each pair `(i, j)` is considered only once with `i < j`.

Here's the breakdown:
1. Initialize a counter variable `count` to zero.
2. Iterate with an index `i` from `0` to `n-1` (where `n` is the size of `nums`).
3. Inside this loop, iterate with an index `j` from `i+1` to `n-1`.
4. For each pair `(i, j)`, check if `nums.get(i) + nums.get(j) < target`.
5. If the condition is true, increment `count`.
6. After the loops complete, `count` will hold the total number of pairs satisfying the condition.

```java
import java.util.List;

class Solution {
    public int countPairs(List<Integer> nums, int target) {
        int n = nums.size();
        int count = 0;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if (nums.get(i) + nums.get(j) < target) {
                    count++;
                }
            }
        }
        return count;
    }
}
```
### Algorithm
- Initialize a counter `count` to 0.
- Use a nested loop. The outer loop iterates `i` from `0` to `n-2`.
- The inner loop iterates `j` from `i+1` to `n-1`.
- Inside the inner loop, check if `nums[i] + nums[j] < target`.
- If the condition is true, increment `count`.
- After the loops complete, return `count`.

## Two Pointers with Sorting
A more efficient approach involves sorting the array first. After sorting, we can use two pointers, one starting from the beginning (`left`) and one from the end (`right`) of the array. By comparing the sum of the elements at these pointers with the target, we can efficiently count the valid pairs in linear time after the initial sort.
**Time:** O(n log n), where `n` is the number of elements in `nums`. This is dominated by the sorting step. The two-pointer traversal itself takes O(n) time. · **Space:** O(log n) or O(n), depending on the space complexity of the sorting algorithm used. For instance, Timsort used in Java's `Collections.sort` can take up to O(n) space in the worst case. If we ignore the space used by sorting, it's O(1).
**Pros:** Significantly more efficient than the brute-force approach, with a time complexity of O(n log n).; Elegant solution that cleverly uses the sorted property of the array to avoid redundant checks.
**Cons:** Requires modifying the input array by sorting it. If the original order must be preserved, a copy of the array is needed, which adds O(n) space complexity.; The sorting step has a time complexity of O(n log n), which might be slightly slower than brute force for very small arrays, though its overall scalability is far superior.
### Explanation
The key insight is that after sorting the array, if `nums[left] + nums[right] < target`, then `nums[left]` paired with any element between `left+1` and `right` (inclusive) will also form a sum less than the target. This is because all elements `nums[k]` where `left < k <= right` are less than or equal to `nums[right]`. This allows us to count multiple pairs at once.

Algorithm steps:
1. Sort the input array `nums`.
2. Initialize a counter `count` to 0.
3. Initialize two pointers: `left = 0` and `right = n - 1`.
4. Loop while `left < right`:
   a. If `nums.get(left) + nums.get(right) < target`, it means all pairs `(left, left+1), (left, left+2), ..., (left, right)` are valid. There are `right - left` such pairs. Add this number to `count` and move `left` one step to the right (`left++`) to consider the next element.
   b. If `nums.get(left) + nums.get(right) >= target`, the sum is too large. To reduce the sum, we must use a smaller number, so we move the `right` pointer one step to the left (`right--`).
5. Return the final `count`.

```java
import java.util.Collections;
import java.util.List;

class Solution {
    public int countPairs(List<Integer> nums, int target) {
        Collections.sort(nums);
        int n = nums.size();
        int count = 0;
        int left = 0;
        int right = n - 1;
        while (left < right) {
            if (nums.get(left) + nums.get(right) < target) {
                count += (right - left);
                left++;
            } else {
                right--;
            }
        }
        return count;
    }
}
```
### Algorithm
- Sort the input array `nums` in non-decreasing order.
- Initialize a counter `count = 0`.
- Initialize two pointers: `left = 0` and `right = n - 1`.
- Loop while `left < right`:
  - If `nums[left] + nums[right] < target`:
    - This implies that `nums[left]` paired with any element from `nums[left + 1]` to `nums[right]` will also have a sum less than `target`.
    - Add `right - left` to `count`.
    - Increment `left` to consider the next element.
  - Else (`nums[left] + nums[right] >= target`):
    - The sum is too large. To decrease it, move the `right` pointer one step to the left (`right--`).
- Return `count`.

# Solutions
### Java

```java
class Solution {
public
  int countPairs(List<Integer> nums, int target) {
    Collections.sort(nums);
    int ans = 0;
    for (int j = 0; j < nums.size(); ++j) {
      int x = nums.get(j);
      int i = search(nums, target - x, j);
      ans += i;
    }
    return ans;
  }
private
  int search(List<Integer> nums, int x, int r) {
    int l = 0;
    while (l < r) {
      int mid = (l + r) >> 1;
      if (nums.get(mid) >= x) {
        r = mid;
      } else {
        l = mid + 1;
      }
    }
    return l;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int countPairs(vector<int> &nums, int target) {
    sort(nums.begin(), nums.end());
    int ans = 0;
    for (int j = 0; j < nums.size(); ++j) {
      int i = lower_bound(nums.begin(), nums.begin() + j, target - nums[j]) -
              nums.begin();
      ans += i;
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def countPairs(self, nums: List[int], target: int) -> int: nums . sort() ans = 0 for j, x in enumerate(nums): i = bisect_left(nums, target - x, hi=j) ans += i return ans

```