Count Pairs Whose Sum is Less than Target (Brute Force & Optimal Solution)
IntuitionStoring all the pairs in a vector and returning the size of the vectorApproachSorting and Two Pointers ApproachComplexity
Time complexity:
O(n log n)
S
# Intuition
<!-- Describe your first thoughts on how to solve this problem. -->
Storing all the pairs in a vector and returning the size of the vector

# Approach
<!-- Describe your approach to solving the problem. -->
Sorting and Two Pointers Approach

# Complexity
- Time complexity:
<!-- Add your time complexity here, e.g. $$O(n)$$ -->
O(n log n)

- Space complexity:
<!-- Add your space complexity here, e.g. $$O(n)$$ -->
O(1)
# Code
```cpp []
class Solution {
public:
    int countPairs(vector<int>& nums, int target) {
        // Brute Force Approach 
        // Time Complexity O(n2);
        // Space Complexity O(n2);

        // vector<pair<int,int>>ans;
        // sort(nums.begin(),nums.end());
        // for(int i=0;i<nums.size();i++)
        // {
        //     for(int j=i+1;j<nums.size();j++)
        //     {
        //         if((nums[i]+nums[j])<target)
        //         {
        //             ans.push_back(make_pair(nums[i],nums[j]));
        //         }
        //     }
        // }
        // return ans.size();

        //Optimal Approach
        int count=0;
        sort(nums.begin(),nums.end());
        int left=0,right=nums.size()-1;
        while(left<right)
        {
            int sum=nums[left]+nums[right];
            if(sum<target)
            {
                count+=right-left;
                left++;
            }
            else if(sum>=target)
            {
                right--;
            }
        }
        return count;
    }
};
```
['C++']