# 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:

```python
i < j < k
```

and:

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

Return the number of such triplets.

The constraints are `0 <= nums.length <= 350`, `-100 <= nums[i] <= 100`, and `-100 <= target <= 100`. ([github.com](https://github.com/doocs/leetcode/blob/main/solution/0200-0299/0259.3Sum%20Smaller/README_EN.md?utm_source=chatgpt.com))

## Input and Output

| Item | Meaning |
|---|---|
| Input | Integer array `nums` and integer `target` |
| Output | Number of valid triplets |
| Valid triplet | `i < j < k` |
| Condition | Sum of the three numbers is smaller than `target` |

Example function shape:

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

## Examples

Example 1:

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

Valid triplets:

| Triplet | Sum |
|---|---|
| `(-2, 0, 1)` | `-1` |
| `(-2, 0, 3)` | `1` |

Triplet:

```python
(-2, 1, 3)
```

has sum:

```python
2
```

which is not strictly smaller than `2`.

Answer:

```python
2
```

Example 2:

```python
nums = []
target = 0
```

No triplets exist.

Answer:

```python
0
```

Example 3:

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

The only triplet has sum:

```python
0
```

which is smaller than `1`.

Answer:

```python
1
```

## First Thought: Try Every Triplet

The direct approach is to check every possible triplet.

```python
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:

$$
O(n^3)
$$

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:

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

Fix the first number:

```python
nums[i] = -2
```

Now we need pairs:

$$
nums[left] + nums[right] < target - nums[i]
$$

Use two pointers:

| Pointer | Meaning |
|---|---|
| `left` | Starts after `i` |
| `right` | Starts at the end |

The important observation is this:

If:

$$
nums[i] + nums[left] + nums[right] < target
$$

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

Why?

Because the array is sorted.

So:

```python
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:

```python
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:
       ```python id="7zc3ca"
       right - left
       ```
       to the answer.
     - Move `left` rightward.
   - Otherwise:
     - Move `right` leftward.

## Walkthrough

Use:

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

The array is already sorted.

Start:

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

Current sum:

```python
-2 + 0 + 3 = 1
```

Since:

$$
1 < 2
$$

the triplet works.

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

That gives:

```python
right - left = 2
```

valid triplets:

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

Add `2` to the answer.

Move `left`:

```python
left = 2
```

Now:

```python
-2 + 1 + 3 = 2
```

This is not strictly smaller than `2`.

Move `right` leftward.

Now `left == right`, so stop.

Continue with:

```python
i = 1
```

No more valid triplets exist.

Final answer:

```python
2
```

## Correctness

The array is sorted before processing.

Fix some index `i`.

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

$$
nums[i] + nums[left] + nums[right] < target
$$

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

```python
left < k <= right
```

also forms a valid triplet with `i` and `left`.

This follows from sorting:

```python
nums[k] <= nums[right]
```

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

So exactly:

```python
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

| Metric | Value | Why |
|---|---|---|
| Time | `O(n^2)` | Sorting plus two-pointer scans |
| Space | `O(1)` or `O(log n)` | Depends on sorting implementation |

The outer loop runs `n` times.

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

## Implementation

```python
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:

```python
nums.sort()
```

Sorting enables the two-pointer logic.

For each first index:

```python
for i in range(n - 2):
```

we search for valid pairs to the right.

The pointers start here:

```python
left = i + 1
right = n - 1
```

Compute the current triplet sum:

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

If the sum is valid:

```python
if total < target:
```

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

So we count them all at once:

```python
count += right - left
```

Then move `left` to search for more triplets.

If the sum is too large:

```python
else:
    right -= 1
```

we decrease `right` to reduce the sum.

Finally return the total count.

## Testing

```python
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:

| Test | Why |
|---|---|
| Standard example | Basic two-pointer behavior |
| Empty array | No triplets |
| All zeros | Single valid triplet |
| Negative values | Mixed-sign handling |
| Unsorted input | Confirms sorting works |
| Very large target | All triplets valid |
| Impossible target | No valid triplets |