15% off all plans & roadmaps Use code

See plans

3Sum Smaller

Updated

TL;DR: Count the index triplets whose sum is strictly below target. Sort a copy, fix the first index, then use two converging pointers so that each valid pair counts a whole range of triplets at once.

Problem

You are given an array of n integers nums and an integer target. Count the index triplets (i, j, k) with 0 <= i < j < k < n whose values satisfy nums[i] + nums[j] + nums[k] < target.

Two triplets count as different when their indices differ, even if their values match.

Example 1

Input: nums = [-10, -8, -3, 1, 5], target = -5
Output: 7

Constraints

  • 0 <= n <= 3500
  • -100 <= nums[i], target <= 100

Constraints that matter

  • n up to 3500 rules out the three-loop brute force. It visits about 7.1 * 10^9 triples in the worst case.
  • Sorting costs O(n log n), and one pointer sweep per index costs O(n). The total is about 1.2 * 10^7 steps at n = 3500, which is fast enough.
  • Values from -100 to 100 keep every sum small. The count itself can reach about 7.1 * 10^9, so the counter must hold 64 bits.
  • The answer is a count of positions, not a list of values. Duplicate values must be counted at each distinct index, so you cannot skip equal neighbours.

View on LeetCode

Hints

Hint 1

This problem sums three indices and asks for a count.

Hint 2

The direct reading of the statement is to check every index triple i < j < k.

Solution

Intuition

This problem sums three indices and asks for a count. The condition depends only on the values, not on where they sit, so the count is the same for any ordering of the array. That lets you sort a copy first. The pattern is Two Pointers, converging on a sorted array with a target sum.

Picture a shelf of jars sorted by weight, where the two hands are the left and right pointers. If the two hands' jars fit under the limit, every jar between them fits too, so you count them in one step.

Fix the smallest index i first. Put left at i + 1 and right at the last index. Because the array is sorted, nums[right] is at least as large as every value between left and right. So if nums[i] + nums[left] + nums[right] < target, every index k in (left, right] also works, and you can add right - left in one step.

When the sum is too large, the largest value in the window must shrink, so move right down. When the sum works, the pairs for this left are settled, so move left up. Each move drops candidates that cannot change the answer, which keeps the scan linear for each i.

Watch the pattern animation

Worked example

Input: nums = [-10, -8, -3, 1, 5], target = -5
Output: 7
Explanation: Seven of the ten index triplets have a sum below -5. The three that fail are (0, 3, 4) with sum -4, (1, 3, 4) with sum -2, and (2, 3, 4) with sum 3. Because the sum -4 is not below -5, the triplet (0, 3, 4) does not count.

Approach 1: Brute force

The direct reading of the statement is to check every index triple i < j < k. Each triple gets one sum and one comparison. The data is never used to skip work, so the cost equals the number of triples.

For n values there are n(n-1)(n-2)/6 such triples. That is about n^3 / 6, which is too many once n reaches the thousands.

Steps

  1. Set count to 0.
  2. Loop i from 0 to n - 3.
  3. Inside it, loop j from i + 1 to n - 2.
  4. Inside that, loop k from j + 1 to n - 1.
  5. If nums[i] + nums[j] + nums[k] < target, add 1 to count.
  6. Return count.

Dry run

Use nums = [-10, -8, -3, 1, 5] and target = -5. The array is already sorted, so the loops read it in order.

  • i = 0, j = 1: k = 2 gives -21 (count 1), k = 3 gives -17 (count 2), k = 4 gives -13 (count 3).
  • i = 0, j = 2: k = 3 gives -12 (count 4), k = 4 gives -8 (count 5).
  • i = 0, j = 3: k = 4 gives -4, which is not below -5.
  • i = 1, j = 2: k = 3 gives -10 (count 6), k = 4 gives -6 (count 7).
  • i = 1, j = 3: k = 4 gives -2, which fails.
  • i = 2, j = 3: k = 4 gives 3, which fails.

The final count is 7, which matches the example.

Complexity

TimeO(n^3)
SpaceO(1)

Let n be the length of nums. The three loops nest, and the innermost body runs once for each triple i < j < k, which is n(n-1)(n-2)/6 times. That is about n^3 / 6, so the time is O(n^3). The loop indices and the counter use a fixed amount of memory, so the extra space is O(1).

PythonTested in our runner

class Solution:
    def threeSumSmaller(self, nums: List[int], target: int) -> int:
        n = len(nums)
        count = 0
        for i in range(n - 2):
            for j in range(i + 1, n - 1):
                for k in range(j + 1, n):
                    if nums[i] + nums[j] + nums[k] < target:
                        count += 1
        return count

The Converging (Sorted Array Target Sum) infographic is part of Pro

A one-page visual of the pattern: when it applies, the steps and the invariant to keep.

Unlock the infographic

Solution pattern

Converging (Sorted Array Target Sum)

Part of Two Pointers

Approach 2: Sort, then two pointersOptimalConverging (Sorted Array Target Sum)

What's slow: the brute force decides each triple on its own. At n = 3500 that is about 7.1 * 10^9 separate checks, and most of them repeat the same comparison with a neighbouring index.

The insight that fixes it: sort a copy and fix i. Once the values are sorted, one comparison can decide a whole range. If nums[i] + nums[left] + nums[right] < target, then every k between left and right also gives a sum below target, so add right - left at once.

If the sum is too large, no left value at or above the current one can pair with right, because those values only make the sum larger. So right moves down. The pointers never move backward, so each i costs one sweep.

Steps

  1. Copy nums and sort the copy in ascending order.
  2. Set count to 0 and loop i from 0 to n - 3.
  3. For each i, set left = i + 1 and right = n - 1.
  4. While left < right, compute the sum of the values at i, left and right.
  5. If the sum is below target, add right - left to count and move left up by one.
  6. Otherwise move right down by one.
  7. Return count after all loops finish.

Dry run

The example is already sorted, so the copy matches the input. The table shows each step of the optimal loop with the state that changes.

Stepileftrightsumsum < -5?actioncount
1014-13yesadd 3, left becomes 23
2024-8yesadd 2, left becomes 35
3034-4noright becomes 35
4124-6yesadd 2, left becomes 37
5134-2noright becomes 37
62343noright becomes 37

Each inner loop ends when left meets right. The outer loop stops at i = 3, since it only runs while i < n - 2. The final count is 7, which matches the example.

Complexity

TimeO(n^2)
SpaceO(n)

Let n be the length of nums. Sorting the copy costs O(n log n), and the outer loop runs at most n - 2 times. For each i, every inner step moves left up or right down, so the inner loop takes at most n - i - 1 steps, which is O(n). The total is O(n log n) + O(n^2), which is O(n^2), and the sorted copy takes O(n) space while the pointers and counter take O(1).

PythonTested in our runner

class Solution:
    def threeSumSmaller(self, nums: List[int], target: int) -> int:
        arr = sorted(nums)  # sorted() returns a new list, so the input is unchanged
        n = len(arr)
        count = 0
        for i in range(n - 2):
            left, right = i + 1, n - 1
            while left < right:
                if arr[i] + arr[left] + arr[right] < target:
                    # arr[right] is the largest value in the window,
                    # so every k in (left, right] also gives a sum below target
                    count += right - left
                    left += 1
                else:
                    right -= 1
        return count

Common mistakes

  • count += 1 inside the valid branch. Adding one counts only (i, left, right) and misses every k between left and right. Add right - left in one step.
  • if nums[i] == nums[i - 1]: continue, copied from 3Sum. This problem counts index triplets, so equal values at different indices are separate answers. Remove the skip.
  • left = i or left = 0 instead of left = i + 1. The pair can then reuse index i or fall before it, which breaks i < j < k and overcounts.
  • else branch that moves left up. When the sum is too large, a larger left makes it larger still, so the only useful move is right--.
  • int count in Java or C#. For n = 3500 the count can reach about 7.1 * 10^9, which overflows 32 bits. Keep the counter in a 64-bit type.

Edge cases

  • Empty array or a single element, such as [] with target 0. The loop never runs, so the answer is 0.
  • Two elements, such as [1, 2] with target 10. There is no third index, so the answer is 0.
  • All values equal and below target, such as [1, 1, 1, 1] with target 4. Each sum is 3, so all C(4, 3) = 4 triplets count.
  • Values equal to target, such as [1, 1, 1] with target 3. The sum is 3, which is not strictly below 3, so the answer is 0.
  • All negative values, such as [-100, -100, -100] with target -100. The sum is -300, which is below -100, so the answer is 1.
  • Maximum size, n = 3500, all values -100, target 100. Every triplet counts, giving 7,139,709,500. The counter needs 64 bits, and the starter's int return type caps any answer at 2147483647.

Follow-ups interviewers ask

Follow-ups are part of Pro

The questions interviewers ask after you solve 3Sum Smaller, with how to answer them.

Unlock the follow-ups

3Sum Smaller FAQ

What is the time complexity of 3Sum Smaller?

The time is O(n^2) when you sort a copy first. Sorting costs O(n log n), and the two-pointer sweep for each index costs O(n), so the sweeps dominate. The brute force version takes O(n^3).

Why use two pointers for 3Sum Smaller?

After sorting, moving left up can only raise the sum, and moving right down can only lower it. That lets each step discard candidates that cannot change the answer. The pointers never backtrack, so each index needs one sweep.

Can 3Sum Smaller be solved in O(1) extra space?

Yes, if you sort in place. The pointer loop and the counter use O(1) extra space. Quicksort-style sorts still use O(log n) stack space, so the strict bound holds only when the sort itself is O(1) extra.

How is 3Sum Smaller different from 3Sum?

3Sum asks for unique value triplets that sum to zero, so it skips duplicate values. 3Sum Smaller counts index triplets with a sum below target, so equal values at different indices each count. You do not skip duplicates here.

Does Python's sorted() change the input list?

No. sorted(nums) returns a new list and leaves nums unchanged. nums.sort() sorts the caller's list in place, which can surprise a caller who reuses the array.

Asked at

See which companies ask this — Pro

Practise it