15% off all plans & roadmaps Use code
See plans3Sum Smaller
- LeetCode 259
- Medium
- Two Pointers
- Converging (Sorted Array Target Sum)
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.
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.
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
- Set
countto 0. - Loop
ifrom 0 ton - 3. - Inside it, loop
jfromi + 1ton - 2. - Inside that, loop
kfromj + 1ton - 1. - If
nums[i] + nums[j] + nums[k] < target, add 1 tocount. - 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
| Time | O(n^3) |
|---|---|
| Space | O(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 countThe 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 infographicSolution 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
- Copy
numsand sort the copy in ascending order. - Set
countto 0 and loopifrom 0 ton - 3. - For each
i, setleft = i + 1andright = n - 1. - While
left < right, compute the sum of the values ati,leftandright. - If the sum is below target, add
right - lefttocountand moveleftup by one. - Otherwise move
rightdown by one. - Return
countafter 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.
| Step | i | left | right | sum | sum < -5? | action | count |
|---|---|---|---|---|---|---|---|
| 1 | 0 | 1 | 4 | -13 | yes | add 3, left becomes 2 | 3 |
| 2 | 0 | 2 | 4 | -8 | yes | add 2, left becomes 3 | 5 |
| 3 | 0 | 3 | 4 | -4 | no | right becomes 3 | 5 |
| 4 | 1 | 2 | 4 | -6 | yes | add 2, left becomes 3 | 7 |
| 5 | 1 | 3 | 4 | -2 | no | right becomes 3 | 7 |
| 6 | 2 | 3 | 4 | 3 | no | right becomes 3 | 7 |
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
| Time | O(n^2) |
|---|---|
| Space | O(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 countCommon mistakes
count += 1inside the valid branch. Adding one counts only (i, left, right) and misses every k between left and right. Addright - leftin 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 = iorleft = 0instead ofleft = i + 1. The pair can then reuse index i or fall before it, which breaks i < j < k and overcounts.elsebranch that movesleftup. When the sum is too large, a largerleftmakes it larger still, so the only useful move isright--.int countin 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-ups3Sum 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
Related problems
- 3Sum · same technique: Converging (Sorted Array Target Sum)
- Container With Most Water · same technique: Converging (Sorted Array Target Sum)
- Two Sum II - Input Array Is Sorted · same technique: Converging (Sorted Array Target Sum)
- 4Sum · same technique: Converging (Sorted Array Target Sum)
- Boats to Save People · same technique: Converging (Sorted Array Target Sum)
- 3Sum Closest · same technique: Converging (Sorted Array Target Sum)
- Trapping Rain Water · next harder, same pattern
- Sort Colors · same pattern: Two Pointers
- Longest Palindromic Substring · same pattern: Two Pointers
- Remove Nth Node From End of List · same pattern: Two Pointers