O(n^2) and O(nlogn) python solutions with step by step explanation
IntuitionWe will be solving this problem using nested loops as the problem states that we have to find the count of pairs whose sum is less than the given targe
# Intuition
We will be solving this problem using nested loops as the problem states that we have to find the count of pairs whose sum is less than the given target but solving with nested loops gives time complexity of O(n^2). But we want the most optimal approach which would be sorting and two ptrs which will give a time complexity of O(nlogn).

# Approach 1
We will create a variable named count which will store the number of count we encounter and also be our output. Then, we will assign 'n' to be the len of nums array. 

Then, we will write a for loop which will run from 0th index to n and inside that loop, we have a inner for loop which will run from 1st index to n. Inside it, we will see if the addition of nums[i] and nums [j] are less than target or not. If yes, we increment count. And at the end, we return count as output.

# Example of the operation:
-> nums = [1,2,3,4,5]
-> target = 6

This is the input array and target we're provided with.

We create count variable and assign it to be 0:
-> count = 0

We'll have two ptrs i and j. i for outer for loop and j for inner loop. And j will be incremented on each iteration and i will be incremented only after we're out of j's.

On 1:
-> i = 0 ie 1 (index and value)
-> j = 1 ie 2
We will enter the for loops and see if nums[i] + nums[j] are less than target or not:
-> target = 6
-> nums[i] + nums[j] = 1 + 2 = 3

Yes, 1 is less than target which is 6. So, we execute the if statement and increment count:
-> count = 0 + 1 = 1

Incremented j:
-> i = 0 ie 1
-> j = 2 ie 3
We will enter the for loops and see if nums[i] + nums[j] are less than target or not:
-> target = 6
-> nums[i] + nums[j] = 1 + 3 = 4

Yes, 4 is less than target which is 6. So, we execute the if statement and increment count:
-> count = 1 + 1 = 2

Incremented j:
-> i = 0 ie 1
-> j = 3 ie 4
We will enter the for loops and see if nums[i] + nums[j] are less than target or not:
-> target = 6
-> nums[i] + nums[j] = 1 + 4 = 5

Yes, 5 is less than target which is 6. So, we execute the if statement and increment count:
-> count = 2 + 1 = 3

Incremented j:
-> i = 0 ie 1
-> j = 4 ie 5
We will enter the for loops and see if nums[i] + nums[j] are less than target or not:
-> target = 6
-> nums[i] + nums[j] = 1 + 5 = 6

We don't execute the if statement as the 6 is equal too target and we exit the for loop and increment i.

On 2:
-> i = 1 ie 2
-> j = 2 ie 3 (index and value)
We will enter the for loops and see if nums[i] + nums[j] are less than target or not:
-> target = 6
-> nums[i] + nums[j] = 2 + 3 = 5

Yes, 5 is less than target which is 6. So, we execute the if statement and increment count:
-> count = 3 + 1 = 4

Incremented j:
-> i = 1 ie 2
-> j = 3 ie 4
We will enter the for loops and see if nums[i] + nums[j] are less than target or not:
-> target = 6
-> nums[i] + nums[j] = 2 + 4 = 6

We don't execute the if statement as 6 is equal to target and we don't increment count.

Incremented j:
-> i = 1 ie 2
-> j = 4 ie 5
We will enter the for loops and see if nums[i] + nums[j] are less than target or not:
-> target = 6
-> nums[i] + nums[j] = 2 + 5 = 7

We don't execute the if statement as 7 is greater than target and we don't increment count and exit the inner for loop.

On 3:
-> i = 2 ie 3
-> j = 3 ie 4
We will enter the for loops and see if nums[i] + nums[j] are less than target or not:
-> target = 6
-> nums[i] + nums[j] = 3 + 4 = 7

We don't execute the if statement as 7 is greater than target and we don't increment count.

Incremented j:
-> j = 4 ie 5
We will enter the for loops and see if nums[i] + nums[j] are less than target or not:
-> target = 6
-> nums[i] + nums[j] = 3 + 5 = 8

We don't execute the if statement as 8 is greater than target and we don't increment count and exit the inner for loop.

On 4:
-> i = 3 ie 4
-> j = 4 ie 5
We will enter the for loops and see if nums[i] + nums[j] are less than target or not:
-> target = 6
-> nums[i] + nums[j] = 4 + 5 = 9

We don't execute the if statement as 9 is greater than target and we don't increment count and exit the inner for loop.

On 5:
-> i = 4 ie 5
We can't run the loop as j is out of bounds. So, we exit the for loop and return count as output.
-> count = 4

![Screenshot 2025-03-25 at 4.37.22 PM.png](https://assets.leetcode.com/users/images/648e343f-c2c2-4f34-a98a-5d455003d1e6_1742900874.9667392.png)

![Screenshot 2025-03-25 at 5.15.31 PM.png](https://assets.leetcode.com/users/images/4f404975-ab12-4d7c-963f-51310475be34_1742903157.03952.png)


# Approach 2
We will sort the input array first and assign count variable to 0. Then, we will assign left and right ptr to 0 and len(nums) -1 respectively. -1 so that it will point to the last elemt.

Then, we will write a while loop which will run until left and right becomes equal. If the addition of left and right is less than target. If yes, we append count with r - l and increment left and if not ie addition is greater than target and decrement right by 1. At the end, we return count as output.

# Example of the operation:
-> nums = [5,8,6,9,7]
-> target = 14
This is the input array and target we're provided with.

To begin solving, we will first sort the array:
-> nums = [5,8,6,9,7]
After sorting:
-> nums.sort()
-> nums = [5,6,7,8,9]

Assign count variable to 0 and assign left and right pointers:
-> count = 0
-> left = 0 ie 5
which is the starting point of the nums array
-> right = 4 ie 9
which is the last index of the nums array

We will enter the while loop as left is less than right and will repeat the process until they become equal.

On 5:
-> left = 0 ie 5
-> right = 4 ie 9
We enter the loop and see if addition of nums[left] and nums[right] is less than target or not:
-> nums[left] + nums[right] < target
-> target = 14
-> 5 + 9 = 14

We don't execute the if statement as 14 is equal to target and instead, we execute the else condition:
-> right -= 1
-> right = 4
-> right = 4 - 1 = 3
-> right = 3 ie 8

On 5:
-> left = 0 ie 5
-> right = 3 ie 8
We enter the loop and see if addition of nums[left] and nums[right] is less than target or not:
-> nums[left] + nums[right] < target
-> target = 14
-> 5 + 8 = 13

We execute the if statement as 13 is less than 14:
-> count += right - left
-> count = 0
-> right - left = 8 - 5 = 3
-> count = 0 + 3
-> count = 3

Incrementing left:
-> left = 0 + 1 = 1
-> left = 1 ie 6

On 6:
-> left = 1 ie 6
-> right = 3 ie 8
We enter the loop and see if addition of nums[left] and nums[right] is less than target or not:
-> nums[left] + nums[right] < target
-> target = 14
-> 6 + 8 = 14

We don't execute the if condition as 14 is equal to target and instead, we execute the else condition:
-> right -= 1
-> right = 3
-> right = 3 - 1 = 2

On 6:
-> left = 1 ie 6
-> right = 2 ie 7
We enter the loop and see if addition of nums[left] and nums[right] is less than target or not:
-> nums[left] + nums[right] < target
-> target = 14
-> 6 + 7 = 13

We enter the if condition as 13 is less than target:
-> count += right - left
-> count = 3
-> right - left = 7 - 6 = 1
-> count = 3 + 1 = 4
-> count = 4

Incrementing left:
-> left = 1
-> left = 1 + 1 = 2
-> left = 2 ie 7

On 7:
We dont enter the while loop as both pointers became equal so we skip the loop and return count as output.

-> count = 4

![Screenshot 2025-03-25 at 5.14.06 PM.png](https://assets.leetcode.com/users/images/d9ca9d39-e2b1-4584-8b98-814592763c32_1742903074.7536514.png)

![Screenshot 2025-03-25 at 5.14.58 PM.png](https://assets.leetcode.com/users/images/53f0aa4c-1358-492b-afac-7b70a8b98429_1742903122.2462687.png)


# Complexity
- Time complexity:
O(n^2) where n denotes the number of elemts in the input array as we're looping through it and second n denotes the inner for loop as we're looping through them again.
For approach 2: O(nlogn) where nlogn denotes the usage of sorting

- Space complexity:
Space would be constant O(1) because we're not storing anything.
Space would be constant O(1) too for second approach.

# Code
```python3 []
class Solution:
    def countPairs(self, nums: List[int], target: int) -> int:
        count = 0 # variable count assign to zero
        n = len(nums) # length of nums array

        for i in range(n): # for every number in nums starting from 0th index
            for j in range(i + 1, n): # for every number in nums starting from 1st index
                if nums[i] + nums[j] < target: # if the addition of nums[i] and nums[j] is less than target
                    count += 1 # we increment count
        
        return count # return count as output

        
```
```python3 []
class Solution: # sorting and two ptrs
    def countPairs(self, nums: List[int], target: int) -> int:
        nums.sort() # sorting the nums array
        count = 0 # assigning count to be zero
        left, right = 0, len(nums) - 1 # starting point of left and right

        while left < right: # while left is less than right that is until they become equal
            if nums[left] + nums[right] < target: #if the addition is less than target
                count += right - left # we append r - l to count
                left += 1 # and increment left
            else: # if the addition is greater than target
                right -= 1 # decrmenet right
        
        return count # returning count as output
        # time complexity: O(nlogn)
        # space: O(1)
        
```
['Python3']