Linear Solution (and other 3 Approaches) with Explanations! 👥 🎯 🔥
Intuition\n Describe your first thoughts on how to solve this problem. \nThe problem requires finding pairs in a list whose sum is less than a given target. Ini
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nThe problem requires finding pairs in a list whose sum is less than a given target. Initially, a brute-force approach comes to mind, but it\'s inefficient for larger lists. More efficient methods include sorting with two pointers, counting sort with two pointers, or binary search, each reducing the number of comparisons.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n\n### Counting Sort and Two Pointers\n1. **Counting Sort**: Use counting sort since the range of numbers is small (-50 to 50). This helps in sorting the list efficiently.\n2. **Two Pointers**: With the sorted list, use two pointers to find pairs whose sum is less than the target. If the sum is less than the target, count all pairs between the current pointers and move the left pointer to the right. Otherwise, move the right pointer to the left.\n\n### Tim Sort and Two Pointers\n1. **Tim Sort**: Sort the list using Python\'s built-in sort, which is Tim Sort.\n2. **Two Pointers**: Apply the two-pointers technique to count valid pairs.\n\n### Binary Search\n1. **Sort the List**: Sort the list using Tim Sort.\n2. **Iterate and Search**: For each element, use binary search to find the rightmost position where the sum of the current element and another element is less than the target.\n\n### Naive Approach\n1. **Nested Loops**: Use two nested loops to check every possible pair of elements to see if their sum is less than the target. This method is straightforward but inefficient.\n\n# Complexity\n- Time complexity:\n  - **Counting Sort and Two Pointers**: $$O(n + k)$$, where $$n$$ is the number of elements and $$k$$ is the range of numbers (constant, 100 in this case).\n  - **Tim Sort and Two Pointers**: $$O(n \\log n)$$ for sorting and $$O(n)$$ for the two-pointer traversal.\n  - **Binary Search**: $$O(n \\log n)$$ for sorting and $$O(n \\log n)$$ for binary search in the worst case, resulting in a total of $$O(n \\log n)$$.\n  - **Naive Approach**: $$O(n^2)$$ due to the nested loops.\n  \n- Space complexity:\n  - **Counting Sort and Two Pointers**: $$O(n + k)$$ total space due to the count array and sorted array.\n  - **Tim Sort and Two Pointers**: $$O(n)$$ total space.\n  - **Binary Search**: $$O(n)$$ total space.\n  - **Naive Approach**: $$O(1)$$ auxiliary space.\n\n# Clarifications\n\n##### Understanding Why Sorting Works Even When 0 <= i < j < n is Violated\n\nWhen we sort the array and use the two-pointer technique to count pairs, we\u2019re leveraging the property that the sum of elements determines the validity of the pairs. The key insight here is to understand the distinction between permutations and combinations of array elements. For an array of size n, there are n!/(n-2)! permutations of pairs of indices (i, j). This set includes pairs where the indices do not satisfy 0 <= i < j < n. However, for the purpose of counting valid pairs, we are interested in combinations where the sum of the elements is less than the target and the indices satisfy 0 <= i < j < n.\n\nWhen the sorted array helps us identify a valid pair (a, b) such that a + b < target, there might be cases where the original indices of a and b do not satisfy i < j. For instance, consider an array nums = [5, 3, 2] with target = 7. Originally, a valid pair is (5, 2) with indices (0, 2), which satisfies 0 < 2. After sorting, the array becomes nums = [2, 3, 5], and one valid pair is (2, 5) with indices (0, 2) in the sorted array. In the original array, the number 2 was at index 2 and 5 was at index 0, resulting in a permutation where i = 2 and j = 0, which violates i < j.\n\nHowever, since we are only counting the pairs and not returning them, we can conceptualize swapping these indices back to their original positions, ensuring the valid pairs are counted correctly. Thus, the pair (5, 2) in the original array corresponds to (2, 5) in the sorted array, preserving the sum condition. This ensures that our counting algorithm is correct even without explicitly tracking the original indices because finding a valid pair in the sorted array implies that there exists a corresponding valid pair in the original array where the sum condition is met, and the indices can be conceptualized to respect i < j.\n\nI would just think of 0 <= i < j < n as saying to choose different pairs of indices, not to make things overcomplicated. But the real reason why this solution works is because of what I said previously.\n\n# Code\n```python\nclass Solution:\n    def countPairs(self, nums: List[int], target: int) -> int:\n        # Counting Sort and Two Pointers\n        min_val, max_val = -50, 50\n        count = [0] * (max_val - min_val + 1)\n        \n        for num in nums:\n            count[num - min_val] += 1\n        \n        nums = []\n        for value in range(min_val, max_val + 1):\n            index = value - min_val # index from 0 to 100.\n            nums.extend([value] * count[index])\n\n        # Two pointers to count pairs.\n        left, right = 0, len(nums) - 1\n        count = 0\n        \n        while left < right:\n            if nums[left] + nums[right] < target:\n                count += (right - left)\n                left += 1\n            else:\n                right -= 1\n        \n        return count\n\n        # O((n + k) + n) -> O(n + k) time. We know k = 100. \n        # O(n + k) auxiliary space.\n        # O(n + k) total space.\n\n\n    def countPairs2(self, nums: List[int], target: int) -> int:\n        # Tim Sort and Two Pointers\n        nums.sort()\n        left, right = 0, len(nums) - 1\n        count = 0\n\n        while left < right:\n            if nums[left] + nums[right] < target:\n                count += (right - left)\n                left += 1\n            else:\n                right -= 1\n\n        return count\n\n        # O(n * log(n)) time.\n        # O(n) auxiliary space.\n        # O(n) total space. \n\n\n    def countPairs3(self, nums: List[int], target: int) -> int:\n        # Binary Search\n        nums.sort()  \n        count = 0\n    \n        for i in range(len(nums) - 1):\n            left, right = i + 1, len(nums) - 1\n            \n            # Binary search element that added to nums[i] is not less than target.\n            while left <= right:\n                mid = left + (right - left) // 2\n                if nums[i] + nums[mid] < target:\n                    left = mid + 1\n                else:\n                    right = mid - 1\n            # All elements between i+1 and right are valid pairs\n            count += right - i\n        \n        return count\n\n        # O(n * log(n)) time.\n        # O(n) auxiliary space.\n        # O(n) total space.\n\n\n    def countPairs4(self, nums: List[int], target: int) -> int:\n        # Naive Approach\n        count = 0\n\n        for i in range(len(nums)):\n            for j in range(i + 1, len(nums)):\n                if nums[i] + nums[j] < target:\n                    count += 1\n\n        return count \n\n        # O(n^2) time.\n        # O(1) auxiliary space.\n        # O(1) total space.\n```\n\nUPVOTE IF HELPFUL \uD83E\uDD19\nTHANKS
['Python3']