100% Beats Solution || Two Approch Discuss || Step By Step Explain || Easy to Understand ||
Abhiraj Pratap Singh\n---\n\n# UPVOTE IT.....\n\n---\n\n### Two Approach .\n- Brute Force \n- Optimal ( Binary Search )\n---\n\n# Approach 1 ( Brute Force Appro
# Abhiraj Pratap Singh\n---\n\n# UPVOTE IT.....\n\n---\n\n### Two Approach .\n- Brute Force \n- Optimal ( Binary Search )\n---\n\n# Approach 1 ( Brute Force Approach )\n<!-- Describe your approach to solving the problem. -->\n1. Initialize Variables:\n    - Initialize variables i, j, and count to keep track of indices and count of pairs.\n2. Outer Loop:\n    - Use a while loop with i to iterate through each element in the vector (nums).\n3. Inner Loop:\n\n    - Use a nested while loop with j to iterate through the elements after the current i in the vector (nums).\n4. Check Sum:\n\n    - Inside the inner loop, check if the sum of elements at indices i and j is less than the target.\n5. Increment Count:\n\n    - If the sum is less than the target, increment the count variable.\n6. Increment Inner Loop:\n\n    - Increment j to consider the next element in the inner loop.\n7. Increment Outer Loop:\n\n    - Increment i to consider the next element in the outer loop.\n8. Return Count:\n\n    - Return the final count of pairs whose sum is less than the target.\n\n---\n\n# Code 1 ( Brute Force Approach )\n```\nclass Solution {\npublic:\n    int countPairs(vector<int>& nums, int target) \n    {\n        int i=0;\n        int j;\n        int count=0;\n        while(i<nums.size())\n        {\n            j=i+1;\n            while(j<nums.size())\n            {\n                if(nums[i]+nums[j]<target)\n                    count++;\n                j++;\n            }\n            i++;\n        }    \n        return count;\n    }\n};\n```\n# Complexity\n\n- **Time complexity: O(n*n) ,** The nested loops result in quadratic time complexity.\n\n---\n\n- **The space complexity O(1),** is constant as it uses a fixed number of variables regardless of the input size.\n\n---\n---\n\n![Screenshot (47).png](https://assets.leetcode.com/users/images/cd54b3b5-edb9-4f09-96ed-b98856d03876_1705333508.1644714.png)\n\n---\n---\n\n# Approach 2 ( Optimal Approach )\n\n1. Sort the Array:\n    - Sort the input vector nums in non-decreasing order.\n2. Initialize Pointers:\n    - Initialize two pointers, start at the beginning of the array and end at the end of the array.\n3. Initialize Count:\n    - Initialize a variable count to keep track of pairs.\n4. Iterate using Two Pointers:\n    - Use a while loop to iterate while start is less than end.\n    - Check if the sum of elements at start and end is less than the target.\n5. Increment Count and Move Pointer:\n    - If the sum is less than the target, increment the count by the difference between end and start (indicating all pairs between start and end satisfy the condition).\n    - Move start pointer to the next element.\n6. Decrement End Pointer:\n    - If the sum is greater than or equal to the target, decrement the end pointer.\n7. Repeat:\n    - Repeat steps 4-6 until start is less than end.\n8. Return Count:\n    - Return the final count of pairs whose sum is less than the target.\n\n---\n\n\n# Complexity:\n\n\n- **Time complexity: O(nlogn)** , Sorting the array takes O(nlogn) time, and the subsequent two-pointer traversal takes O(n) time.\n\n---\n\n\n- **Space complexity: O(1)** , The space complexity is constant as it uses a fixed number of variables regardless of the input size.\n\n\n\n\n\n\n\n\n\n\n\n\n# Code 2 ( Optimal Approach )\n```\npublic:\n    int countPairs(vector<int>& nums, int target) \n    {\n        sort(nums.begin(),nums.end());\n        int start=0;\n        int end=nums.size()-1;\n        int count=0;\n        while(start<end)\n        {\n            if( nums[start]+nums[end]<target )\n            {\n                count=count+end-start;\n                start++;\n            }\n            else\n                end--;\n        }   \n        return count;\n    }\n};\n```\n\n\n---\n\n# if you like the solution please UPVOTE IT.....\n\n---\n\n![discord-discordgifemoji.gif](https://assets.leetcode.com/users/images/67570655-2232-42aa-883c-8d0a07f7dd26_1705333588.3291564.gif)\n\n---\n\n![fucking-die-redditor-stupid-cuck-funny-cat.gif](https://assets.leetcode.com/users/images/a662db30-60cb-4cbe-b983-e09a2ef4011d_1705333610.324654.gif)\n\n
['Array', 'Two Pointers', 'Binary Search', 'Sorting', 'C++']