Problem statement

https://leetcode.com/problems/3sum-smaller/

Solution

The idea is to use 2sum problem: for each i solve 2sum smaller problem, which can be done using 2 pointers approach. If we have sum greater or equal than goal, move end pointer, that is decrease this sum, if we have smaller, add end - beg to final answer: this number of pairs satisfies the condition.

Complexity

Time complexity is $O(n^2)$, because we solve $n$ subproblems. Space complexity is $O(n)$ to keep sorted data.

Code

class Solution:
    def threeSumSmaller(self, nums, target):
        nums.sort()
        n, ans = len(nums), 0
        
        for i in range(n-2):
            goal = target - nums[i]
            beg, end = i + 1, n - 1

            while beg < end:
                if nums[beg] + nums[end] >= goal:
                    end -= 1
                else: 
                    ans += (end - beg)
                    beg += 1
                
        return ans