Java Two Pointer Approach with Explanation
Intuition\n Describe your first thoughts on how to solve this problem. \nWe need to  count the number of pairs of numbers such that their sum is less than a giv
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nWe need to  count the number of pairs of numbers such that their sum is less than a given target. We can sort the given list in ascending order and then count the pairs using a two pointer approach.\n# Approach\n<!-- Describe your approach to solving the problem. -->\n1. First we sort the list in ascending order using the sort method. This way, we can identify potential pairs without having to compare every element with each other.\n\n2. Next, we initialize two pointers, left and right at the start and end respectively. We then calculate the sum of numbers at this pointers.\n\n    - If sum is less than the target then increment count variable by the number of pairs between left and right pointer as the array is already sorted and all pairs will satisfy the condition. Increment the left pointer to check for more pairs.\n\n    - If sum is greater than the target value or equal to the target value, decrement the right pointer to reduce the sum. This works since the list is sorted and all values to the left of the right pointer is less than the value at right pointer.\n\n3. Finally return the count variable.\n# Complexity\n- Time complexity:\n$$O(nlogn)$$\n    Since we sort the list once and the pointer move at max n steps in total.\n\n- Space complexity:\n$$O(1)$$\n    Since we did not make use of any new data containers and Java\'s collection.sort() uses inplace sorting.\n\n# Code\n```java []\nclass Solution {\n    public int countPairs(List<Integer> nums, int target) {\n        Collections.sort(nums);\n        int count = 0;\n        int left = 0;\n        int right = nums.size() - 1;\n\n        while (left < right) {\n            int sum = nums.get(left) + nums.get(right);\n            if (sum < target) {\n                count += (right - left);\n                left++;\n            } else {\n                right--;\n            }\n        }\n\n        return count;\n    }\n}\n```\n**PLEASE UPVOTE IF YOU FOUND THIS HELPFUL!**
['Two Pointers', 'Sorting', 'Java']