Medium

3Sum Smaller

LAB

Return the number of index triplets whose values sum to less than target.

EXAMPLES

Example 1

Input
{
  "nums": [
    -2,
    0,
    1,
    3
  ],
  "target": 2
}

Output
2

FUNCTION SHAPE

nums: intArraytarget: int→int

SOLUTION NOTE

Rearrange the equation: nums[j] + nums[k] < target - nums[i]. Let c = target - nums[i]. Now for a fixed i, use two pointers to count all (j,k) for i < j < k where nums[j] + nums[k] < c.

Similar to Valid Triangle Number but we're fixing i and finding all (j,k), and counting nums[j] + nums[k] < c rather than > c.

Reveal reference solution +

pythonREFERENCE

def threeSumSmaller(self, nums: List[int], target: int) -> int:
    n = len(nums)
    nums.sort()
    res = 0

    for i in range(n):
        j = i + 1
        k = n - 1

        while j < k:
            if nums[j] + nums[k] < target - nums[i]:
                res += (k - j)
                j += 1
            else:
                k -= 1

    return res

TimeO(n²)

SpaceO(1)

Open on LeetCode ↗