3Sum Smaller — LeetCode 259 Python Solution

The problem

Given an array of n integers nums and an integer target, find the number of index triplets i, j, k with 0 <= i < j < k < n that satisfy the condition nums[i] + nums[j] + nums[k] < target.

Example

Input

nums = [-2,0,1,3], target = 2

Output

2

Explanation

Because there are two triplets which sums are less than 2:

Python solution

class Solution:
    def threeSumSmaller(self, nums: List[int], target: int) -> int:
        nums.sort()
        ans, n = 0, len(nums)
        for i in range(n - 2):
            j, k = i + 1, n - 1
            while j < k:
                x = nums[i] + nums[j] + nums[k]
                if x < target:
                    ans += k - j
                    j += 1
                else:
                    k -= 1
        return ans

Complexity

Pattern: Two Pointers

Use the order already in the input to discard half the search space at every step. LeetCode 259. 3Sum Smaller is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Two Pointers.

The two pointers guide has the Python template for the pattern and the 201 LeetCode problems that use it.

Related problems