LeetCode 259 - 3Sum Smaller

The problem asks us to count how many distinct index triplets (i, j, k) satisfy two conditions: 1. The indices are ordered such that 0 <= i < j < k < n 2.

leetcodemediumarraytwo-pointersbinary-searchsorting

LeetCode Problem 259

Difficulty: 🟡 Medium
Topics: Array, Two Pointers, Binary Search, Sorting

Solution

Problem Understanding

The problem asks us to count how many distinct index triplets (i, j, k) satisfy two conditions:

  1. The indices are ordered such that 0 <= i < j < k < n
  2. The sum of the corresponding values is strictly smaller than the given target

In other words, we must examine combinations of three different elements in the array and determine how many of those combinations produce a sum less than target.

The input consists of:

  • An integer array nums
  • An integer target

The output is a single integer representing the number of valid triplets.

A key detail is that we are counting triplets by index positions, not by unique values. If the same number appears multiple times in different positions, each valid index combination counts separately.

The constraints are important for deciding which algorithm is practical:

  • n can be as large as 3500
  • A brute-force solution would require checking all possible triplets
  • The number of triplets in the worst case is approximately n^3 / 6

For n = 3500, a cubic algorithm becomes far too slow. We therefore need something more efficient than O(n^3).

The array may also contain:

  • Negative numbers
  • Positive numbers
  • Duplicate values
  • Empty input

The problem guarantees that the final answer fits within a 32-bit integer range, so we do not need special overflow handling.

Several edge cases are important:

  • Arrays with fewer than three elements cannot form any triplets
  • Duplicate numbers should still count as distinct index combinations
  • Negative values can produce many valid triplets
  • Already sorted or reverse-sorted arrays should still work correctly
  • Large numbers of valid combinations must be counted efficiently without explicitly enumerating every triplet

Approaches

Brute Force Approach

The most direct solution is to try every possible triplet.

We can use three nested loops:

  • The first loop chooses index i
  • The second loop chooses index j
  • The third loop chooses index k

For every triplet, we compute:

nums[i] + nums[j] + nums[k]

If the sum is smaller than target, we increment the answer.

This approach is guaranteed to be correct because it explicitly checks every possible valid triplet. Nothing is skipped.

However, the time complexity is O(n^3), which is too slow when n can be 3500.

Optimal Approach, Sorting + Two Pointers

The key observation is that after sorting the array, we can use ordering properties to count many triplets at once.

Suppose we fix the first element nums[i].

We then want to find pairs (j, k) such that:

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

Because the array is sorted:

  • If a particular pair (j, k) works,
  • Then every index between j and k also works with j

For example, if:

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

then:

nums[i] + nums[left] + nums[right - 1] < target
nums[i] + nums[left] + nums[right - 2] < target
...

This means we can count multiple triplets in one step instead of checking them individually.

We use two pointers:

  • left starts just after i
  • right starts at the end of the array

Depending on the current sum:

  • If the sum is smaller than target, all pairs from left through right are valid
  • Otherwise, we decrease the sum by moving right leftward

This reduces the complexity from O(n^3) to O(n^2).

Approach Comparison

Approach Time Complexity Space Complexity Notes
Brute Force O(n³) O(1) Checks every possible triplet explicitly
Optimal O(n²) O(1) or O(log n) depending on sort implementation Uses sorting and two pointers to count multiple triplets efficiently

Algorithm Walkthrough

Optimal Algorithm

  1. Sort the array in non-decreasing order.

Sorting is essential because the two-pointer strategy depends on the array being ordered. Once sorted, increasing or decreasing pointers predictably changes the sum. 2. Initialize a variable count = 0.

This variable stores the total number of valid triplets. 3. Iterate through the array using index i from 0 to n - 3.

We treat nums[i] as the first element of the triplet. 4. For each i, initialize two pointers:

  • left = i + 1
  • right = n - 1

These pointers search for valid second and third elements. 5. While left < right, compute the current sum:

current_sum = nums[i] + nums[left] + nums[right]
  1. If current_sum < target, then every index between left and right forms a valid triplet with i.

Since the array is sorted:

nums[right] >= nums[right - 1] >= ...

Replacing right with any smaller index only decreases the sum.

Therefore, the number of valid triplets is:

right - left

Add this amount to count.

  1. Move left one step to the right.

We have already counted all triplets beginning with the current left, so we continue searching for new combinations. 2. Otherwise, if the sum is too large, move right one step left.

This decreases the sum and may create valid triplets. 3. Continue until all possibilities are processed. 4. Return count.

Why it works

The correctness relies on the sorted order of the array.

When:

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

every index between left and right also works because replacing nums[right] with a smaller element cannot increase the sum.

This allows us to count right - left triplets at once without missing or double-counting any combinations.

Every valid triplet is eventually considered exactly once because:

  • i uniquely fixes the first element
  • The two-pointer scan systematically explores all valid (left, right) pairs

Python Solution

from typing import List

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:
                current_sum = nums[i] + nums[left] + nums[right]

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

        return count

The implementation begins by sorting the array. This enables the two-pointer optimization that follows.

The outer loop selects the first element of each triplet. Since we need three elements total, the loop only runs until n - 3.

For each fixed index i, two pointers search the remaining portion of the array.

The variable current_sum stores the sum of the current triplet candidate.

When the sum is smaller than the target, all positions between left and right are guaranteed to work because the array is sorted. Instead of checking each individually, the code adds right - left directly to the answer.

If the sum is too large, the only way to reduce it is to move right leftward.

The algorithm efficiently counts all valid triplets without enumerating every combination explicitly.

Go Solution

package main

import "sort"

func threeSumSmaller(nums []int, target int) int {
	sort.Ints(nums)

	n := len(nums)
	count := 0

	for i := 0; i < n-2; i++ {
		left := i + 1
		right := n - 1

		for left < right {
			currentSum := nums[i] + nums[left] + nums[right]

			if currentSum < target {
				count += right - left
				left++
			} else {
				right--
			}
		}
	}

	return count
}

The Go implementation closely mirrors the Python solution.

The main difference is that Go uses sort.Ints(nums) from the standard library to sort the slice in place.

Go slices naturally handle empty arrays, so no additional checks are required for edge cases such as arrays with fewer than three elements.

Integer overflow is not a concern because the constraints are small. The largest possible triplet sum is well within Go's int range.

Worked Examples

Example 1

Input:

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

After sorting:

[-2,0,1,3]

Iteration with i = 0

left right Triplet Sum Action Count
1 3 (-2,0,3) 1 Valid, add 2 2
2 3 (-2,1,3) 2 Too large, move right 2

Why add 2?

Because when (-2,0,3) works:

  • (-2,0,1) also works

So both triplets are counted together.

Iteration with i = 1

left right Triplet Sum Action Count
2 3 (0,1,3) 4 Too large 2

Final answer:

2

Example 2

Input:

nums = []
target = 0

The array length is less than 3, so the outer loop never runs.

Result:

0

Example 3

Input:

nums = [0]
target = 0

Again, fewer than three elements exist.

Result:

0

Complexity Analysis

Measure Complexity Explanation
Time O(n²) Sorting takes O(n log n), two-pointer scanning dominates with O(n²)
Space O(1) or O(log n) Only constant extra variables are used, excluding sorting internals

The outer loop runs n times, and for each iteration the two pointers move across the array at most once. Since each pointer only moves inward, the total work per iteration is linear.

This produces an overall time complexity of O(n²).

The algorithm itself uses only a few variables. Depending on the language and sorting implementation, sorting may require logarithmic stack space internally.

Test Cases

from typing import List

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:
                current_sum = nums[i] + nums[left] + nums[right]

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

        return count

solution = Solution()

assert solution.threeSumSmaller([-2, 0, 1, 3], 2) == 2  # provided example
assert solution.threeSumSmaller([], 0) == 0  # empty array
assert solution.threeSumSmaller([0], 0) == 0  # single element
assert solution.threeSumSmaller([1, 1], 3) == 0  # fewer than 3 elements
assert solution.threeSumSmaller([0, 0, 0], 1) == 1  # exactly one valid triplet
assert solution.threeSumSmaller([3, 1, 0, -2], 4) == 3  # unsorted input
assert solution.threeSumSmaller([-1, -1, -1, -1], 0) == 4  # all triplets valid
assert solution.threeSumSmaller([5, 5, 5], 10) == 0  # no valid triplets
assert solution.threeSumSmaller([-2, 0, 1, 3], 5) == 4  # all triplets valid
assert solution.threeSumSmaller([1, 2, 3, 4, 5], 8) == 2  # selective valid triplets
assert solution.threeSumSmaller([-5, -4, -3, -2, -1], -6) == 10  # all negative numbers

Test Summary

Test Why
[-2,0,1,3], target=2 Verifies the main example
[] Ensures empty input returns zero
[0] Ensures insufficient length is handled
[1,1] Confirms arrays with fewer than three elements return zero
[0,0,0], target=1 Tests exactly one valid triplet
[3,1,0,-2], target=4 Verifies sorting is correctly used
[-1,-1,-1,-1], target=0 Tests duplicates and multiple valid combinations
[5,5,5], target=10 Tests case with no valid triplets
[-2,0,1,3], target=5 Tests case where all triplets are valid
[1,2,3,4,5], target=8 Tests mixed valid and invalid triplets
[-5,-4,-3,-2,-1], target=-6 Tests all-negative arrays

Edge Cases

Arrays With Fewer Than Three Elements

If the array contains fewer than three numbers, no triplet can exist. This is a common source of off-by-one bugs in nested loop solutions.

The implementation handles this naturally because the outer loop:

for i in range(n - 2):

does not execute when n < 3.

Duplicate Values

Arrays may contain repeated numbers, and the problem counts triplets by index positions rather than distinct values.

For example:

[-1, -1, -1, -1]

contains multiple valid triplets even though the values repeat.

The implementation correctly counts every distinct index combination because it never skips duplicates.

All Triplets Valid

In some inputs, nearly every possible triplet satisfies the condition.

Example:

nums = [-5,-4,-3,-2,-1]
target = 100

A naive solution still checks every triplet individually.

The optimized solution handles this efficiently by counting multiple triplets at once using:

count += right - left

This prevents unnecessary repeated work and preserves quadratic complexity.

No Valid Triplets

Some arrays produce no valid triplets at all.

Example:

nums = [10,10,10]
target = 5

The implementation correctly returns zero because every computed sum exceeds the target, causing the right pointer to move inward until the search terminates.