Count the triplets with a sum below a target
Medium · Target 15 minutes · Two pointers· Type asked at
Uber
J.P. Morgan
Two Sigma
You're given an integer array nums and an integer target, and you have to count
the triples of indices i < j < k with nums[i] + nums[j] + nums[k] < target. Equal
values at different positions count as different triplets.
Examples
| Input | Output | Why |
|---|---|---|
nums = [-2, 0, 1, 3], target = 2 | 2 | −2 + 0 + 1 = −1 and −2 + 0 + 3 = 1 are both under 2, and anything else comes to 2 or more. |
nums = [], target = 0 | 0 | There's nothing to pick from, so the count's zero. |
nums = [1, 1, 1], target = 4 | 1 | There's only one way to pick three positions out of three. |
Constraints
- 0 ≤ n ≤ 3500
- −100 ≤ nums[i], target ≤ 100
Hints
Hint 1
You're counting positions, not values, so the order of the array doesn't matter. What does sorting buy you once you've fixed the first value?
Hint 2
With nums[i] fixed it's the count-pairs-below-a-target question on everything to the right of i, with the target lowered by nums[i].
Hint 3
If nums[i] + nums[lo] + nums[hi] < target, every k from lo + 1 up to hi works with lo too, so you'd add hi − lo in one go and move lo up.
Where people lose marks
- Skipping repeated values the way you do in 3-sum. Here every set of positions counts, so you'd be throwing away triplets you're meant to keep.
- Adding 1 on a hit when you've really found hi − lo triplets with this i and lo, which gets the small examples right and the bigger ones wrong.
- Using ≤ when the problem says <, so that a triplet that adds up to the target exactly gets counted when it shouldn't.
Dry run on [3,1,0,-2],4
Read it one frame at a time, the way you would trace the code on paper in an interview. Each frame shows the state after the step it describes.
-
Step 1 / 5nums-20011233count0
I'd sort it first, which gives -2, 0, 1, 3, and then fix the smallest value at i and scan for pairs to its right.
-
Step 2 / 5nums-20i01lo1233hicount2
With -2 fixed, -2 + 0 + 3 = 1 is under 4, so 0 goes with all 2 values up to hi. That's 2 more and lo moves up.
-
Step 3 / 5nums-20i0112lo33hicount3
With -2 fixed, -2 + 1 + 3 = 2 is under 4, so 1 goes with that one value. That's 1 more and lo moves up.
-
Step 4 / 5nums-2001i12lo33hicount3
0 + 1 + 3 = 4, which isn't under 4, so 3 is too big here and hi comes down.
-
Step 5 / 5nums-20011233count3
Every i has had its scan, and there are 3 triplets in all.
How to think about it
Every triple is O(n³), and at 3,500 that's about seven billion triples, which is far too slow. Since you're
counting positions the order doesn't matter, so I'd sort, fix the smallest value at i, and count pairs
to the right of it whose sum is below target − nums[i].
That pair count is the same scan as counting the pairs below a target. With lo just after
i and hi at the end, if the three values add up to less than the target then
nums[lo] works with everything from lo + 1 to hi, because none of those are
bigger than nums[hi]. You add hi − lo and move lo up. If the sum's too big it's
nums[hi] that can't be part of anything with the smallest values left, and hi comes down.
It's n scans of O(n) each, so O(n²). Unlike 3-sum there's nothing to skip, because two triplets with the same values at different positions are both meant to be counted.
Complexity. Time O(n²) · Space O(1) extra (after an in-place sort)
The solution, in six languages
Each one is compiled and run against the test table before it is published. Java is reviewed by hand.
def three_sum_smaller(nums, target):
a = sorted(nums)
count = 0
for i in range(len(a) - 2):
lo, hi = i + 1, len(a) - 1
while lo < hi:
if a[i] + a[lo] + a[hi] < target:
count += hi - lo # a[lo] works with everything up to hi
lo += 1
else:
hi -= 1
return count#include <vector>
#include <algorithm>
long long solve(std::vector<int> a, int target) {
std::sort(a.begin(), a.end());
long long count = 0;
for (int i = 0; i + 2 < (int)a.size(); ++i) {
int lo = i + 1, hi = (int)a.size() - 1;
while (lo < hi) {
if (a[i] + a[lo] + a[hi] < target) { count += hi - lo; ++lo; } // a[lo] works with everything up to hi
else --hi;
}
}
return count;
}import java.util.Arrays;
class Solution {
public long threeSumSmaller(int[] nums, int target) {
int[] a = nums.clone();
Arrays.sort(a);
long count = 0;
for (int i = 0; i + 2 < a.length; i++) {
int lo = i + 1, hi = a.length - 1;
while (lo < hi) {
if (a[i] + a[lo] + a[hi] < target) { count += hi - lo; lo++; } // a[lo] works with everything up to hi
else hi--;
}
}
return count;
}
}function threeSumSmaller(nums, target) {
const a = nums.slice().sort((x, y) => x - y);
let count = 0;
for (let i = 0; i + 2 < a.length; i++) {
let lo = i + 1, hi = a.length - 1;
while (lo < hi) {
if (a[i] + a[lo] + a[hi] < target) { count += hi - lo; lo++; } // a[lo] works with everything up to hi
else hi--;
}
}
return count;
}fn solve(nums: &[i64], target: i64) -> i64 {
let mut a = nums.to_vec();
a.sort();
let mut count = 0i64;
for i in 0..a.len().saturating_sub(2) {
let (mut lo, mut hi) = (i + 1, a.len() - 1);
while lo < hi {
if a[i] + a[lo] + a[hi] < target { count += (hi - lo) as i64; lo += 1; } // a[lo] works with everything up to hi
else { hi -= 1; }
}
}
count
}import Data.Array
import Data.List (sort)
solve :: [Int] -> Int -> Int
solve nums target = sum [scan i (i + 1) (n - 1) 0 | i <- [0 .. n - 3]]
where
n = length nums
a = listArray (0, max 0 (n - 1)) (sort nums)
scan i lo hi acc
| lo >= hi = acc
| a ! i + a ! lo + a ! hi < target = scan i (lo + 1) hi (acc + hi - lo) -- a ! lo works with everything up to hi
| otherwise = scan i lo (hi - 1) accVariants to try
- If you're asked for the triplets with a sum in a range [a, b], you'd count those below b + 1 and take away those below a.
- If you're asked to count the triplets with a sum equal to the target, that's 3-sum counting positions, and on a hit you'd multiply the counts of the two values when they're different.
Next problems
All distinct triplets summing to zero
Sort, then fix one value and run the two-pointer scan on the rest. The whole difficulty is in the duplicates.
Open the problem → Medium20 minThe triple sum closest to a target
Fix the smallest of the three, then walk two pointers over the rest, moving whichever brings the sum towards the target.
Open the problem → Medium15 minCount the triangles you can make
Sort, fix the longest side, and one scan counts every pair that works with it, several at a time.
Open the problem →Write a solution and run it against the real test table.
Keep going
All distinct triplets summing to zero
Sort, then fix one value and run the two-pointer scan on the rest. The whole difficulty is in the duplicates.
Open the problem → Medium20 minThe triple sum closest to a target
Fix the smallest of the three, then walk two pointers over the rest, moving whichever brings the sum towards the target.
Open the problem → Medium15 minCount the triangles you can make
Sort, fix the longest side, and one scan counts every pair that works with it, several at a time.
Open the problem → Two pointersThe pattern behind it
Two indices walking a sorted or paired structure, each step ruling out one candidate for good.
Read the pattern →Preparing for a real process? Quant interview preparation, or book a free 20-minute call.