Python 3 - Step By Step - Beats 90.20%
Intuition\n Describe your first thoughts on how to solve this problem. \nWe want to find all the pairs that are less than target.\nNote: We only choose two numb
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nWe want to find all the pairs that are less than target.\nNote: We only choose two numbers from different indices and they can have the same value. [1, 1] -> i = 0, j = 1 \n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n* First we sort the array.\n* We iterate over the array, so we have the first number (call its index i), we need to check how many numbers in the list that can be used as pairs and be < target.\n* To find the second number, think of finding the last index that can satisfy the conditin and all the previous ones will also match (since we sorted the array). We use **Binary Search**.\n* After finding the last index (call it sec), we count all the numbers between i and sec "including sec" and add to result.\n* **To make the iteration faster:** we check if number at index i is >= target and is a positive number, if it matches this case then we can\'t find anymore pairs.\n    * Ex: [2,4,5] , target = 2 -> no pairs can be used.\n    * Ex: [-2, -1, 2, 6] , target: -2 -> Note here first number = -2 but is a negative number. If we used 6 -> sum = -4 < target, a pair is possible. \n# Complexity\n- Time complexity: $$O(nlogn)$$\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\nCalling the sort method takes O(nlogn) time complexity and since we have binary search "O(logn)" inside the iteration, the nested loop also takes O(nlogn).\n- Space complexity: $$O(1)$$\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\nWe store int variables; res, start, end, mid.\n# Code\n```\nclass Solution:\n    def countPairs(self, nums: List[int], target: int) -> int:\n        nums.sort()\n        res = 0\n        for i in range(len(nums)):\n            # There is no pairs left that matches the condition\n            if nums[i] >= target and nums[i] > 0:\n                break\n            else:\n                # find the last index of the second number that matches the condition\n                start = i + 1\n                end = len(nums) - 1\n                mid = 0\n                while start <= end:\n                    mid = (start + end) // 2\n                    # print(nums[start], nums[mid], nums[end])\n                    if nums[mid] >= target - nums[i]:\n                        end = mid - 1\n                    else: # nums[mid] < target - nums[i]\n                        start = mid + 1\n                \n                res += end - i\n                # print(res)\n\n        return res\n        \n```
['Binary Search', 'Python3']