Efficient Two-Pointer Approach to Count Pairs with Sum Less Than Target (O(n log n))
IntuitionThe problem requires us to count the number of pairs (i,j) such that i<j and nums[i]+nums[j]<target.
A brute force approach would check all pairs, but
# Intuition
The problem requires us to count the number of pairs (i,j) such that i<j and nums[i]+nums[j]<target.
A brute force approach would check all pairs, but we can optimize using sorting and the two-pointer approach.
<!-- Describe your first thoughts on how to solve this problem. -->

# Approach
1. Sort the array
    * Sorting helps in efficiently finding pairs using two pointers.
2. Use two pointers (l and r)
    * l starts at 0 (smallest element), r starts at n - 1 (largest element).
    * If nums[l] + nums[r] < target, then all pairs (l, l+1), (l, l+2), ..., (l, r) are valid.
    * Instead of iterating over them, we add (r - l) to the count in one step.
    * Move l right to check the next number.
    * If nums[l] + nums[r] >= target, move r left to decrease the sum.
<!-- Describe your approach to solving the problem. -->

# Complexity
- Time complexity: O(n log n)
    * Sorting takes O(nlogn).
    * The two-pointer traversal takes O(n).
    * Total: O(nlogn)+O(n)=O(nlogn).
<!-- Add your time complexity here, e.g. $$O(n)$$ -->

- Space complexity: O(1)
    * O(1) since we only use two pointers (l, r) and a counter (ans).

<!-- Add your space complexity here, e.g. $$O(n)$$ -->

# Code
```python3 []
class Solution:
    def countPairs(self, nums: List[int], target: int) -> int:
        nums.sort()
        n = len(nums)
        ans = 0
        l, r = 0, n-1
        while l<r:
            if nums[l]+nums[r]<target:
                ans += (r - l)
                l+=1
            else:
                r-=1
        return ans
```


![sad-thumbs-up-cat.3.meme.webp](https://assets.leetcode.com/users/images/31f87dec-80ee-406f-82b5-be7278cc0ec5_1743693507.0317774.webp)



['Two Pointers', 'Python3']