LeetCode 259: 3Sum Smaller

Problem Restatement

We are given:

• An integer array nums
• An integer target

We need to count how many index triplets satisfy:

i < j < k

and:

Return the number of such triplets.

The constraints are 0 <= nums.length <= 350, -100 <= nums[i] <= 100, and -100 <= target <= 100. (github.com)

Input and Output

Example function shape:

def threeSumSmaller(nums: list[int], target: int) -> int:
    ...

Examples

Example 1:

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

Valid triplets:

Triplet:

(-2, 1, 3)

has sum:

2

which is not strictly smaller than 2.

Answer:

2

Example 2:

nums = []
target = 0

No triplets exist.

Answer:

0

Example 3:

nums = [0, 0, 0]
target = 1

The only triplet has sum:

0

which is smaller than 1.

Answer:

1

First Thought: Try Every Triplet

The direct approach is to check every possible triplet.

class Solution:
    def threeSumSmaller(self, nums: list[int], target: int) -> int:
        n = len(nums)
        count = 0

        for i in range(n):
            for j in range(i + 1, n):
                for k in range(j + 1, n):
                    if nums[i] + nums[j] + nums[k] < target:
                        count += 1

        return count

This works, but it checks too many combinations.

Problem With Brute Force

Three nested loops give:

With n = 350, this becomes unnecessarily expensive.

We need a faster way to count many triplets at once.

Key Insight

Sorting allows us to use the two-pointer technique.

Suppose the array is sorted:

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

Fix the first number:

nums[i] = -2

Now we need pairs:

Use two pointers:

The important observation is this:

If:

then every index between left and right also works with left.

Why?

Because the array is sorted.

So:

nums[left + 1] <= nums[right]

Replacing nums[right] with a smaller value keeps the sum smaller than target.

Therefore we can count all these triplets at once:

right - left

This is the core optimization.

Algorithm

1. Sort the array.
2. Fix the first index i.
3. Use two pointers:
   • left = i + 1
   • right = n - 1
4. While left < right:
   • Compute the triplet sum.
   • If the sum is smaller than target:
     • Add:

       right - left
       to the answer.
     • Move left rightward.
   • Otherwise:
     • Move right leftward.

Walkthrough

Use:

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

The array is already sorted.

Start:

i = 0
nums[i] = -2
left = 1
right = 3

Current sum:

-2 + 0 + 3 = 1

Since:

the triplet works.

Because the array is sorted, every index between left and right also works with left.

That gives:

right - left = 2

valid triplets:

(-2, 0, 1)
(-2, 0, 3)

Add 2 to the answer.

Move left:

left = 2

Now:

-2 + 1 + 3 = 2

This is not strictly smaller than 2.

Move right leftward.

Now left == right, so stop.

Continue with:

i = 1

No more valid triplets exist.

Final answer:

2

Correctness

The array is sorted before processing.

Fix some index i.

The algorithm searches for pairs (left, right) such that:

If this condition is true, then every index k satisfying:

left < k <= right

also forms a valid triplet with i and left.

This follows from sorting:

nums[k] <= nums[right]

Therefore replacing nums[right] with any smaller value keeps the total sum below target.

So exactly:

right - left

new triplets are counted correctly.

If instead the sum is too large, then using the same right with any larger left index would only increase the sum further. Therefore decreasing right is the only way to possibly reach a valid sum.

The algorithm examines all valid pointer states without missing or double-counting any triplet.

Therefore the final count is correct.

Complexity

The outer loop runs n times.

The inner two-pointer scan moves each pointer at most n steps total.

Implementation

class Solution:
    def threeSumSmaller(self, nums: list[int], target: int) -> int:
        nums.sort()

        n = len(nums)
        count = 0

        for i in range(n - 2):
            left = i + 1
            right = n - 1

            while left < right:
                total = nums[i] + nums[left] + nums[right]

                if total < target:
                    count += right - left
                    left += 1
                else:
                    right -= 1

        return count

Code Explanation

We first sort the array:

nums.sort()

Sorting enables the two-pointer logic.

For each first index:

for i in range(n - 2):

we search for valid pairs to the right.

The pointers start here:

left = i + 1
right = n - 1

Compute the current triplet sum:

total = nums[i] + nums[left] + nums[right]

If the sum is valid:

if total < target:

then every index between left and right also works.

So we count them all at once:

count += right - left

Then move left to search for more triplets.

If the sum is too large:

else:
    right -= 1

we decrease right to reduce the sum.

Finally return the total count.

Testing

def run_tests():
    s = Solution()

    assert s.threeSumSmaller([-2, 0, 1, 3], 2) == 2
    assert s.threeSumSmaller([], 0) == 0
    assert s.threeSumSmaller([0, 0, 0], 1) == 1
    assert s.threeSumSmaller([1, 1, -2], 1) == 1
    assert s.threeSumSmaller([3, 1, 0, -2], 4) == 3
    assert s.threeSumSmaller([1, 2, 3, 4], 100) == 4
    assert s.threeSumSmaller([5, 5, 5], 10) == 0

    print("all tests passed")

run_tests()

Test meaning: