LeetCode 259: 3Sum Smaller – Count Triplets with Two-Pointer Technique in Python

Programming & Development / April 10, 2025

LeetCode 259: 3Sum Smaller – Count Triplets with Two-Pointer Technique in Python

LeetCode 259 3Sum Smaller Python two pointer technique sorted array triplet count three sum variation array problem binary search coding interview

Copy Link Bookmark Print

Introduction

LeetCode 259: 3Sum Smaller is a variation of the famous 3Sum problem, but instead of finding triplets that sum to zero, we need to count how many triplets have a sum less than a given target.

This is a classic use case for the two-pointer approach on a sorted array and is highly efficient.

Problem Statement

Given an integer array nums and an integer target, return the number of triplets (i, j, k) such that:

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

Example

python

Input: nums = [-2, 0, 1, 3], target = 2
Output: 2
Explanation: The two triplets are:
- (-2, 0, 1)
- (-2, 0, 3)

Step-by-Step Solution in Python

✅ Step 1: Sort the Array

Sorting helps because:

We can use the two-pointer technique
We can efficiently determine how many combinations satisfy the condition

✅ Step 2: Fix One Number and Use Two Pointers

For each index i, we:

Fix nums[i]
Use two pointers (left and right) to find valid j and k such that their sum is less than the target

Step 3: Code It

python

def threeSumSmaller(nums: list[int], target: int) -> int:
    nums.sort()
    count = 0
    n = len(nums)

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

        while left < right:
            total = nums[i] + nums[left] + nums[right]
            if total < target:
                # All elements between left and right will also form valid triplets
                count += right - left
                left += 1
            else:
                right -= 1

    return count

Explanation of the Code

Sort the array: Enables us to reason about increasing values.
Outer loop: Fix the first number of the triplet.
Two-pointer scan:
If total < target: We know all values between left and right will also work (since the array is sorted).
So, we add (right - left) to the count and move left forward.
If total >= target: Move right backward to reduce the sum.

Dry Run Example

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

Sorted: [-2, 0, 1, 3]

i = 0, left = 1, right = 3
total = -2 + 0 + 3 = 1 < 2 → count += 2
i = 1, left = 2, right = 3
total = 0 + 1 + 3 = 4 → too large → move right

Answer: 2

Time and Space Complexity

Time Complexity: O(n²)
Outer loop: O(n), inner loop (two-pointer): O(n)
Space Complexity: O(1)
Just sorting in-place and using pointers.

Conclusion

LeetCode 259 teaches a powerful pattern: fix one element, use two pointers for the rest. This approach is useful in many array-based problems involving combinations or constraints.

NUHMAN.com