Three Sum Smaller

Implementation

• Brute Force approach:
  • Time complexity - O(n${}^3$)
  • Space complexity - O(1)

class Solution:

    def threeSumSmaller(self, nums: List[int], target: int) -> int:

        res = 0

        for i in range(len(nums)):

            if i >= 0:

                for j in range(len(nums)):

                    if j > i:

                        for k in range(len(nums)):

                            if k>j and k<len(nums):

                                if nums[i] + nums[j] + nums[k] < target:

                                    res+=1

        return res

• Optimal-ish approach:
  • Time complexity - O(n${}^2$)
  • Space complexity - O(1)

class Solution:

    def threeSumSmaller(self, nums: List[int], target: int) -> int:

        res = 0

        nums.sort()

        for i, a in enumerate(nums):            

            j, k = i + 1, len(nums) - 1

            while j < k:

                threesum = a + nums[j] + nums[k]

                if threesum < target:

                    res += k - j

                    j += 1

                else:

                    k -= 1

        return res