Two-Pointers-Approach || Easy-to-Understand ||  In 9 Languages🔥
Intuition\n Describe your first thoughts on how to solve this problem. \nProblem: You\'re given an array of integers and a target value. The task is to count th
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nProblem: You\'re given an array of integers and a target value. The task is to count the number of pairs of elements in the array such that the sum of the pair is less than the target value.\nThe key insight for solving this problem is recognizing that if you have an array sorted in ascending order, you can efficiently find pairs that meet the given condition using a Two-Pointers Approach.\n# Approach\n<!-- Describe your approach to solving the problem. -->\nThe Two-Pointers Approach is a common technique to solve problems involving arrays or sequences. In this case, you can use two pointers, often referred to as the "left" and "right" pointers, to traverse the array and find pairs that satisfy the given condition.\n\nHere\'s a high-level overview of the approach:\n\n1.) Sort the array in ascending order. Sorting helps in efficiently exploring pairs with sums less than the target value.\n\n2.) Initialize two pointers, left and right, pointing to the first and last elements of the sorted array, respectively.\n\n3.) Initialize a variable count to keep track of the count of valid pairs.\nWhile the left pointer is less than the right pointer:\nIf the sum of the elements at left and right is less than the target value, it means all pairs with the current left element will also satisfy the condition. So, increment the count by right - left and move the left pointer to the right.\nIf the sum is greater than or equal to the target, move the right pointer to the left.\n\n4.) Continue this process until the left pointer crosses the right pointer.\n\n\n\n# Complexity\n- Time complexity: O(nlogn)\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\nSorting the array takes O(n log n) time, where n is the number of elements in the array. The two-pointer traversal takes linear time, O(n), as each element is visited once.\nOverall, the time complexity is dominated by the sorting step, making it O(n log n).\n\n- Space complexity: O(1)\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\nThe space complexity depends on the sorting algorithm used. If you\'re using an in-place sorting algorithm like Quicksort, the space complexity will be O(1) (negligible). If you\'re using an algorithm that requires additional space, the space complexity might be higher.\n\n# ******Upvote******\uD83D\uDE80\n\n# Code\n```C++ []\nclass Solution {\npublic:\n  int countPairs(vector<int>& nums , int target){ // function to count the pairs whose sum is less than target\n      sort(nums.begin() , nums.end()); // sort the vector nums\n      int count = 0; // variable to store the count\n      int left = 0; // variable to store the left\n      int right = nums.size()-1; // variable to store the right\n      while(left < right){ // loop until left is less than right\n          if(nums[left] + nums[right] < target){ // if nums[left] + nums[right] is less than target\n              count += right-left; // update the count\n              left++; // increment the left\n          }\n          else{ // else\n              right--; // decrement the right\n          }\n      }\n      return count; // return the count\n  }\n};\n```\n```java []\nclass Solution {\n    public int countPairs(List<Integer> nums, int target) {\n        Collections.sort(nums); // sort the vector nums\n        int count = 0; // variable to store the count\n        int left = 0; // variable to store the left\n        int right = nums.size()-1; // variable to store the right\n        while(left < right){ // loop until left is less than right\n            if(nums.get(left) + nums.get(right) < target){ // if nums[left] + nums[right] is less than target\n                count += right-left; // update the count\n                left++; // increment the left\n            }\n            else{ // else\n                right--; // decrement the right\n            }\n        }\n        return count; // return the count\n        \n    }\n}\n```\n```python []\nclass Solution(object):\n    def countPairs(self, nums, target):\n        """\n        :type nums: List[int]\n        :type target: int\n        :rtype: int\n        """\n        nums.sort() # sort the vector nums\n        count = 0 # variable to store the count\n        left = 0 # variable to store the left\n        right = len(nums)-1 # variable to store the right\n        while(left < right): # loop until left is less than right\n            if(nums[left] + nums[right] < target): # if nums[left] + nums[right] is less than target\n                count += right-left # update the count\n                left += 1 # increment the left\n            else: # else\n                right -= 1 # decrement the right\n        return count # return the count\n```\n```python3 []\nclass Solution:\n    def countPairs(self, nums: List[int], target: int) -> int:\n        nums.sort() # sort the vector nums\n        count = 0 # variable to store the count\n        left = 0 # variable to store the left\n        right = len(nums)-1 # variable to store the right\n        while(left < right): # loop until left is less than right\n            if(nums[left] + nums[right] < target): # if nums[left] + nums[right] is less than target\n                count += right-left # update the count\n                left += 1 # increment the left\n            else: # else\n                right -= 1 # decrement the right\n        return count # return the count\n```\n```c []\nint countPairs(int* nums, int numsSize, int target){\n    qsort(nums, numsSize, sizeof(int), cmp); // sort the vector nums\n    int count = 0; // variable to store the count\n    int left = 0; // variable to store the left\n    int right = numsSize-1; // variable to store the right\n    while(left < right){ // loop until left is less than right\n        if(nums[left] + nums[right] < target){ // if nums[left] + nums[right] is less than target\n            count += right-left; // update the count\n            left++; // increment the left\n        }\n        else{ // else\n            right--; // decrement the right\n        }\n    }\n    return count; // return the count\n}\nint cmp(const void* a, const void* b){ // function to compare the elements\n    return *(int*)a - *(int*)b; // return the difference\n}\n\n```\n```c# []\npublic class Solution {\n    public int CountPairs(IList<int> nums, int target) {\n        nums = nums.OrderBy(x => x).ToList(); // sort the vector nums\n        int count = 0; // variable to store the count\n        int left = 0; // variable to store the left\n        int right = nums.Count-1; // variable to store the right\n        while(left < right){ // loop until left is less than right\n            if(nums[left] + nums[right] < target){ // if nums[left] + nums[right] is less than target\n                count += right-left; // update the count\n                left++; // increment the left\n            }\n            else{ // else\n                right--; // decrement the right\n            }\n        }\n        return count; // return the count\n    }\n}\n```\n```javascript []\nvar countPairs = function(nums, target) {\n    nums.sort((a, b) => a-b); // sort the vector nums\n    let count = 0; // variable to store the count\n    let left = 0; // variable to store the left\n    let right = nums.length-1; // variable to store the right\n    while(left < right){ // loop until left is less than right\n        if(nums[left] + nums[right] < target){ // if nums[left] + nums[right] is less than target\n            count += right-left; // update the count\n            left++; // increment the left\n        }\n        else{ // else\n            right--; // decrement the right\n        }\n    }\n    return count; // return the count\n};\n```\n```swift []\nclass Solution {\n    func countPairs(_ nums: [Int], _ target: Int) -> Int {\n        var nums = nums.sorted() // sort the vector nums\n        var count = 0 // variable to store the count\n        var left = 0 // variable to store the left\n        var right = nums.count-1 // variable to store the right\n        while(left < right){ // loop until left is less than right\n            if(nums[left] + nums[right] < target){ // if nums[left] + nums[right] is less than target\n                count += right-left // update the count\n                left += 1 // increment the left\n            }\n            else{ // else\n                right -= 1 // decrement the right\n            }\n        }\n        return count // return the count\n    }\n}\n```\n```Dart []\nclass Solution {\n  int countPairs(List<int> nums, int target) {\n    nums.sort(); // sort the vector nums\n    int count = 0; // variable to store the count\n    int left = 0; // variable to store the left\n    int right = nums.length-1; // variable to store the right\n    while(left < right){ // loop until left is less than right\n        if(nums[left] + nums[right] < target){ // if nums[left] + nums[right] is less than target\n            count += right-left; // update the count\n            left++; // increment the left\n        }\n        else{ // else\n            right--; // decrement the right\n        }\n    }\n    return count; // return the count\n  }\n}\n```\n
['Two Pointers', 'Swift', 'C', 'Python', 'C++', 'Java', 'Python3', 'JavaScript', 'C#', 'Dart']