Count the triangles you can make
Medium · Target 15 minutes · Two pointers· Type asked at
Hudson River Trading
Palantir
Bank of America
You're given an array nums of non-negative integers and you have to return how many
triples of indices i < j < k give you side lengths nums[i], nums[j] and
nums[k] that can make a triangle. Three lengths make a triangle when each one's less than the other two
added together.
Examples
| Input | Output | Why |
|---|---|---|
nums = [2, 2, 3, 4] | 3 | (2, 3, 4) twice, once for each 2, and (2, 2, 3). (2, 2, 4) fails because 2 + 2 is not more than 4. |
nums = [4, 2, 3, 4] | 4 | |
nums = [1, 2, 3] | 0 | 1 + 2 = 3, a flat triangle, which does not count. |
Constraints
- 0 ≤ n ≤ 1000
- 0 ≤ nums[i] ≤ 1000
Hints
Hint 1
If you sort the three lengths so that a ≤ b ≤ c you'll only need to check one of the three inequalities. Which one is it?
Hint 2
It's a + b > c, because the other two hold already when c's the biggest. So you'd sort the whole array and fix c as the longest side.
Hint 3
With c fixed at index k you put lo = 0 and hi = k − 1. If nums[lo] + nums[hi] > c then every index from lo up to hi − 1 works with hi as well, so you can add hi − lo and move hi down. If it doesn't you move lo up.
Where people lose marks
- Adding 1 on a hit and moving lo. You'll miss every other lo that works with the same hi and you're no longer counting pairs a range at a time.
- Fixing the shortest side and scanning above it. Then a hit doesn't rule anything out in one direction and you can't count by ranges any more.
- Counting a + b = c. That's a flat triangle with no area and the problem asks for a strict inequality.
- Zeros. You'd think they need a special case but 0 + b > c can't hold when b ≤ c, so they drop out by themselves.
Dry run on [4,2,3,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 / 5nums20314243count0
Sorted: 2, 3, 4, 4. Fix the largest side at k and scan below it.
-
Step 2 / 5nums20lo3142hi43kcount2
2 + 4 > 4: every index from 0 to 1 works with 4, since each is at least 2. Add 2, move hi left.
-
Step 3 / 5nums20lo31hi4243kcount3
2 + 3 > 4: only index 0 sits below hi, and it works. Add 1, move hi left.
-
Step 4 / 5nums20lo31hi42k43count4
2 + 3 > 4: only index 0 sits below hi, and it works. Add 1, move hi left.
-
Step 5 / 5nums20314243count4
Every k has been tried: 4 triangles.
How to think about it
If you check every triple it's O(n³). Sorting helps because once you've got a ≤ b ≤ c
the only inequality you need to check is a + b > c, since c can't ever be bigger than c plus
something that's at least zero.
So after the sort I fix the longest side at index k, going down from the end, and run two pointers
over nums[0..k−1]. When nums[lo] + nums[hi] > nums[k] you'd still have a triangle if you
swapped nums[lo] for anything bigger, and everything at lo, lo + 1, …, hi − 1 is at least as
big. That's hi − lo triangles you can count in one go, and since hi has now been paired with
everything it can be you move it down. When the sum's too small it's nums[lo] that's too short to go
with anything that's left, so you move lo up instead.
Each of those scans is O(k) and you run n of them, so you end up at O(n²).
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 triangle_number(nums):
a = sorted(nums)
count = 0
for k in range(len(a) - 1, 1, -1): # a[k] is the longest side
lo, hi = 0, k - 1
while lo < hi:
if a[lo] + a[hi] > a[k]:
count += hi - lo # every lo' in [lo, hi) works with hi
hi -= 1
else:
lo += 1
return count#include <vector>
#include <algorithm>
long long solve(std::vector<int> a) {
std::sort(a.begin(), a.end());
long long count = 0;
for (int k = (int)a.size() - 1; k >= 2; --k) { // a[k] is the longest side
int lo = 0, hi = k - 1;
while (lo < hi) {
if (a[lo] + a[hi] > a[k]) { count += hi - lo; --hi; } // every lo' in [lo, hi) works with hi
else ++lo;
}
}
return count;
}import java.util.Arrays;
class Solution {
public int triangleNumber(int[] nums) {
int[] a = nums.clone();
Arrays.sort(a);
int count = 0;
for (int k = a.length - 1; k >= 2; k--) { // a[k] is the longest side
int lo = 0, hi = k - 1;
while (lo < hi) {
if (a[lo] + a[hi] > a[k]) { count += hi - lo; hi--; } // every lo' in [lo, hi) works with hi
else lo++;
}
}
return count;
}
}function triangleNumber(nums) {
const a = nums.slice().sort((x, y) => x - y);
let count = 0;
for (let k = a.length - 1; k >= 2; k--) { // a[k] is the longest side
let lo = 0, hi = k - 1;
while (lo < hi) {
if (a[lo] + a[hi] > a[k]) { count += hi - lo; hi--; } // every lo' in [lo, hi) works with hi
else lo++;
}
}
return count;
}fn solve(nums: &[i64]) -> i64 {
let mut a = nums.to_vec();
a.sort();
let mut count = 0i64;
for k in (2..a.len()).rev() { // a[k] is the longest side
let (mut lo, mut hi) = (0usize, k - 1);
while lo < hi {
if a[lo] + a[hi] > a[k] { count += (hi - lo) as i64; hi -= 1; } // every lo' in [lo, hi) works with hi
else { lo += 1; }
}
}
count
}import Data.Array
import Data.List (sort)
solve :: [Int] -> Int
solve nums = sum [scan k 0 (k - 1) 0 | k <- [2 .. n - 1]]
where
n = length nums
a = listArray (0, n - 1) (sort nums)
-- a ! k is the longest side; count the pairs below it
scan k lo hi acc
| lo >= hi = acc
| a ! lo + a ! hi > a ! k = scan k lo (hi - 1) (acc + hi - lo)
| otherwise = scan k (lo + 1) hi accVariants to try
- If you're asked for the largest perimeter of any triangle you sort and walk down from the top, and the first three values in a row that work give you the answer in O(n log n).
- If you're asked to count triples with a + b + c ≤ target it's the same shape where you fix one value and count a range at a time.
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 triplets with a sum below a target
Sort, fix the smallest value, and when the pair sum fits you've found a whole run of triplets in one step. There are no duplicates to worry about this 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 triplets with a sum below a target
Sort, fix the smallest value, and when the pair sum fits you've found a whole run of triplets in one step. There are no duplicates to worry about this 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.