Brute Force O(n²) and Optimized O(n log n) Solutions
IntuitionThe task is to count all pairs (i, j) in the list nums such that i < j and nums[i] + nums[j] < target.
A brute-force approach (nested loops) would give
# Intuition
The task is to count all pairs (i, j) in the list nums such that i < j and nums[i] + nums[j] < target.
A brute-force approach (nested loops) would give us O(n²) time complexity, which is inefficient for large inputs.
To optimize the solution, we can leverage the sorted array and use a two-pointer technique to efficiently count valid pairs.

# Approach
Sort the list: Sorting helps us manage the two-pointer traversal. If nums[l] + nums[r] < target, then all pairs (l, l+1), (l, l+2), ..., (l, r) will also satisfy the condition, saving us extra iterations.

Two-pointer Technique:

Start with two pointers, l (left) initialized to 0 and r (right) initialized to nums.size() - 1.

If nums[l] + nums[r] < target, it means all pairs from l to r will be valid, so we increment count by (r - l) and move the left pointer to explore more potential pairs.

If the sum is greater than or equal to the target, move the right pointer inward to reduce the sum.

Continue this process until l and r converge.

Return the count after iterating through the list.

# Complexity
- Time complexity:
O(n log n) and O(n2)

- Space complexity:
O(1)

# Code
```java []
class Solution {
    public int countPairs(List<Integer> nums, int target) {
        // int count = 0;
        // O(n2)
        // for(int i = 0; i < nums.size(); i++){
        //     for(int j = i + 1; j < nums.size(); j++){
        //         if(nums.get(i) + nums.get(j) < target){
        //             count++;
        //         }
        //     }
        // }
        nums.sort((a,b) -> a-b); //[-1,1,1,2,3]
        int count = 0;
        int l = 0;
        int r = nums.size() - 1;
        while(l != r){
            if(nums.get(l) + nums.get(r) < target){
                count += r - l;
                l++;
            }else{
                 r--;
            }
        } 
        return count;
    }
}
```
['Java']