Understand
30-second explanation
Build the interview-ready mental model before comparing implementations.
Given three arrays a, b, c, count distinct triplets (p, q, r) with p∈a, q∈b, r∈c such that p ≤ q and r ≤ q. The trick: deduplicate and sort each array, then for every distinct q in b multiply (count of distinct a-values ≤ q) by (count of distinct c-values ≤ q) and sum those products. Both counts come from binary search (upper-bound), so the whole thing is O((p+q+r) log). The total can exceed 2³¹ — accumulate in a long.
Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview contextHide interview context
What's being tested
Whether you recognize that the count factorizes — for a fixed q the number of valid p and valid r are independent, so you multiply instead of nesting three loops — and whether you remember to deduplicate and use a long.
Where candidates slip
Forgetting to deduplicate (over-counting triplets), nesting three loops for an O(p·q·r) blowup, or overflowing a 32-bit int when summing products.
How to stand out
State the factorization out loud: 'for each q, the valid p-count and r-count are independent, so the answer is the sum of their products.' Then reach for binary search and call out the overflow risk before being asked.
Choose
Compare the available approaches
Use constraints and trade-offs to select the route you can defend in an interview.
Interactive decision treeInteractiveChoose the right approachExplore the full treeCollapse the tree
How to read it:Pivot on b; the a-side and c-side counts are independent, so multiply then sum.
Learn & trace
Build each solution step by step
Move from the core idea to a visual trace, implementation, proof, and edge cases.
Approach 1 of 2
Brute Force — Triple Nested Loop
1Hint 1Explore hintHide hint
The condition is local to a single triplet: x ≤ y and z ≤ y. What's the most literal way to test every candidate triplet?
2Hint 2Explore hintHide hint
Before counting, collapse duplicates in each array into sets — the problem counts distinct value-triplets.
3Hint 3Explore hintHide hint
Three nested loops over the distinct values: for each y in b, for each x in a, for each z in c, count when x ≤ y and z ≤ y.
A · Core idea
The most direct reading: a triplet (x, y, z) counts when x ≤ y and z ≤ y. So enumerate every combination and tally the ones that satisfy both inequalities.
Deduplicate before you count. The problem asks for distinct triplets of values. If a contains the value 3 twice, picking '3' is still one choice, not two. Convert each array to a set (or sort and unique) first, otherwise duplicates inflate the count.
Why three loops is the natural baseline. Each of the three positions is filled independently from its own array, and the constraint ties x and z to y. The literal translation is a loop per array, checking both inequalities in the innermost body. It's obviously correct, which makes it the right thing to state before optimizing.
Why we don't ship it. With each array up to 10⁵ distinct values, the product is up to 10¹⁵ iterations. Even at a billion ops/second that's days. Mention it, state the cost, then factorize.
B · Visual dry run
Interactive dry run
Select a frame to connect the decision with its visual state.
a = [1, 3, 5], b = [2, 3], c = [1, 2, 3]Array state
y=3 (from b)
a≤3 = {1,3}, c≤3 = {1,2,3} → 2×3 = 6
8C · Code with teaching comments
Reference implementation previewpublic long tripletsBrute(int[] a, int[] b, int[] c) { int[] da = dedupSort(a); int[] db = dedupSort(b); int[] dc = dedupSort(c); long count = 0;Explore the full codeHide the full code
D · Why it works and complexityO(p·q·r) timeO(p+q+r) spaceOpen the invariant and proofExplore the proofHide the proof
The inner two loops do redundant work: for a fixed y, counting valid x doesn't depend on z at all. That observation — the inequalities don't interact — is exactly what lets us replace the inner loops with two independent counts and a multiply.
ComplexityO(p·q·r) time, O(p+q+r) space — After dedup the three loops still run up to |a|·|b|·|c| ≈ 10¹⁵ in the worst case — astronomically too slow.
E · Edge cases and pitfalls3Skipping deduplication — duplicate values inflate the triplet count.Explore edge casesHide edge cases
Pitfalls
- Skipping deduplication — duplicate values inflate the triplet count.
- Using int for the accumulator — overflows past ~2.1×10⁹.
- Accepting the triple loop on full-size inputs — it never finishes.
Approach 2 of 2 · Optimal
Sort + Binary-Search Counting (Optimal)
1Hint 1Explore hintHide hint
For a fixed y, does the number of valid x depend on which z you pick? No — the two conditions are independent. What does that let you replace the inner loops with?
2Hint 2Explore hintHide hint
If a is sorted, 'how many a-values are ≤ y' is just an upper-bound binary search returning the insertion index of y.
3Hint 3Explore hintHide hint
For each distinct y in b, compute x = countLE(a, y) and z = countLE(c, y); add x*z to a long accumulator.
A · Core idea
The brute force re-derives, for every (x, z) pair, the same fact: both must be ≤ y. But the count of valid x and the count of valid z are independent — so for a fixed y the number of triplets is simply (#a ≤ y) × (#c ≤ y). That collapses two inner loops into two counts and a multiply.
Turning a count into binary search. After sorting a ascending, 'how many elements are ≤ y' is the index where y would be inserted to keep the array sorted after all elements equal to y — i.e. an upper bound. In Java, upperBound(a, y) returns exactly that index, which equals the count of elements ≤ y. Same for c. Each query is O(log n) instead of O(n).
Why dedup still matters. We count distinct triplets, so a, b, and c are deduplicated first. Deduping b also means each pivot y is processed once; deduping a and c means the upper-bound counts are counts of distinct values, exactly what the problem wants.
Why long is non-negotiable. Each product x*z can be up to 10⁵ × 10⁵ = 10¹⁰, and we sum up to 10⁵ of them. The running total can reach ~10¹⁵ — far beyond a 32-bit int. Accumulate in long, and in Java make sure the multiplication itself happens in long ((long) x * z) so it doesn't overflow before the cast.
Why it's fast. One sort per array plus a handful of binary searches per pivot makes the whole algorithm O((p+q+r) log), comfortable for 10⁵-sized inputs.
B · Visual dry run
Interactive dry run
Select a frame to connect the decision with its visual state.
a = [1, 3, 5], b = [2, 3], c = [1, 2, 3]Array state
binary search y=3
elements ≤ 3 are {1,3} → upperBound = 2
8C · Code with teaching comments
D · Why it works and complexityO((p + q + r) log(p + q + r)) timeO(p + q + r) spaceOpen the invariant and proofExplore the proofHide the proof
The key realization is independence: for a fixed pivot the two side-counts don't interact, so a nested count becomes a product. Pair that with 'how many ≤ x' = upper-bound binary search, and a would-be O(n³) count drops to O(n log n). This factorize-then-count pattern recurs anywhere a multi-dimensional count separates along a pivot.
ComplexityO((p + q + r) log(p + q + r)) time, O(p + q + r) space — Sorting each array is O(n log n). Then for each of ≤ q distinct pivots we do two O(log) binary searches → O(q log p + q log r). Overall O((p+q+r) log).
E · Edge cases and pitfalls5a = [5, 6], b = [1], c = [1] — y=1: countLE(a,1)=0, so product is 0 → total 0. No a-value is ≤ 1.Explore edge casesHide edge cases
Edge cases handled
a = [5, 6], b = [1], c = [1]y=1: countLE(a,1)=0, so product is 0 → total 0. No a-value is ≤ 1.a = [1,1,1], b = [1,1], c = [1]After dedup all are {1}; y=1 gives 1×1 = 1. Duplicates collapse to a single triplet.
Pitfalls
- Using lower-bound instead of upper-bound — undercounts elements equal to y.
- In Java, writing `total += x * z` with int x,z — the product overflows before the long add; cast or keep x,z as long.
- Forgetting to dedup b — re-processing a repeated pivot doesn't change the total but signals you missed the 'distinct' requirement.
Practice
Try the solution yourself
Edit the optimal implementation, test another input, and observe the result.
Editable code previewpublic long triplets(int[] a, int[] b, int[] c) { int[] da = dedupSort(a); int[] db = dedupSort(b); int[] dc = dedupSort(c); long total = 0;Explore the playgroundClose the playground
Avoid mistakes
Recognize the interview traps
Understand why common attempts fail before reviewing the corrected implementation.
1Skipping deduplication
The problem counts distinct value-triplets. If a value repeats in a, counting it twice multiplies the triplet count incorrectly.
Explore the code comparisonHide the code comparison
Skipping deduplication
The problem counts distinct value-triplets. If a value repeats in a, counting it twice multiplies the triplet count incorrectly.
Don't write this
da, db, dc = sorted(a), sorted(b), sorted(c)Write this instead
da, db, dc = sorted(set(a)), sorted(set(b)), sorted(set(c))2Integer overflow on the product
x and z each reach 10⁵, so x*z reaches 10¹⁰. In Java an int multiply overflows before the cast to long.
Explore the code comparisonHide the code comparison
Integer overflow on the product
x and z each reach 10⁵, so x*z reaches 10¹⁰. In Java an int multiply overflows before the cast to long.
Don't write this
int x = upperBound(da, y);
int z = upperBound(dc, y);
total += x * z; // overflows in 32-bitWrite this instead
long x = upperBound(da, y);
long z = upperBound(dc, y);
total += x * z; // computed in 64-bit3Lower bound instead of upper bound
We need the count of values ≤ y (inclusive). lower_bound stops before equal elements and undercounts ties.
Explore the code comparisonHide the code comparison
Lower bound instead of upper bound
We need the count of values ≤ y (inclusive). lower_bound stops before equal elements and undercounts ties.
Don't write this
x = bisect_left(da, y) # excludes values equal to yWrite this instead
x = bisect_right(da, y) # includes values equal to yRevise
Carry the pattern into the interview
Pattern to remember
Sort + dedup + per-pivot upper-bound counting
Code pattern to memorize
dedup+sort a, b, c
total = 0 (long)
for q in distinct(b):
x = countLE(a, q) # binary search upper bound
z = countLE(c, q)
total += x * zRules to remember
- 1Deduplicate first. The problem counts distinct triplets of values, so duplicate entries inside a, b, or c must collapse to one before counting.
- 2Pivot on b. q is the middle element with p ≤ q and r ≤ q, so b drives the loop and a/c are queried.
- 3Use upper-bound / countLE: the number of values ≤ q is the insertion point of q (plus equal elements). Get this with binary search, not a linear scan.
- 4Accumulate in a long. With p, q, r up to 10⁵ each, products of counts sum well past the 32-bit range.
- 5The two counts are independent — choices of p and r don't interact, so it's a product, not a nested loop.
Use this pattern when
- Counting combinations across multiple sorted sets bounded by a shared pivot value
- 'How many x ≤ value' queries repeated many times over a static array
- A triple/pair count that factorizes into independent per-side counts you can multiply
Choose another pattern when
- You must *enumerate* the actual triplets, not count them → you cannot collapse to a product
- The three constraints are coupled (e.g. p + r ≤ q) → counts no longer multiply independently
- Arrays are tiny and only queried once → a single linear pass beats sorting
Interview takeaway
When a counting problem has a natural pivot and the other dimensions are independent, dedup + sort each side and turn each side into an O(log n) 'how many ≤ pivot' query, then multiply. The product replaces a triple nested loop.
Continue
Transfer the pattern to another problem
Use a direct variation or pattern sibling to prove the idea is reusable.
Transferable patternFactorize-then-count: when a multi-dimensional count separates along a pivot whose other dimensions are independent, replace nested loops with a product of per-side 'how many ≤ pivot' counts, each answered by an upper-bound binary search. Same shape as counting pairs/triplets bounded by a shared value.
Practice queueDirect variations and pattern siblings
Direct follow-ups
- Count triplets with strict inequalitiesComing soonIf the condition becomes x < y and z < y, switch upper-bound to lower-bound counting.
- 3SumComing soonDifferent shape — find triplets summing to zero with sort + two pointers, O(n²).
- Count of Range SumComing soonCounting via sorted structures / BIT — the same 'how many ≤ value' query at scale.