Loading…

mediumArraysFrequently asked

Count Triplets

Q: How do you solve Count Triplets using the Brute Force — Triple Nested Scan approach?

When to use it: Say it first to nail down the definition of a valid triplet, then explain why it's too slow for n = 10⁵. The most literal reading: enumerate every ordered triple of indices `i i and k > j.** The triplet is ordered by position, so the inner loops must start past the outer index to avoid reusing a position and to avoid counting the same index set in a different order. That guarantees each index triple is examined exactly once. **Why multiplication, not addition, in the test.** We compare `arr[j] == arr[i]·r`. Working with the product (rather than dividing) sidesteps integer-division pitfalls when a value isn't divisible by `r`. **Why we don't ship it.** C(n,3) for n = 10⁵ is ~1.6×10¹⁴ iterations — utterly infeasible. It only demonstrates the definition; the frequency-map version is the real answer. Time complexity: O(n³). Space complexity: O(1).

Q: How do you solve Count Triplets using the Two Frequency Maps — Fix the Middle (Optimal) approach?

When to use it: The answer they want: linear time by treating each element as the middle term. The key reframe: stop enumerating triples and instead fix the **middle** element. If the middle value is `a`, the geometric progression forces the first value to be `a/r` and the third to be `a·r`. Those are uniquely determined, so the only question is *how many* of each exist on the correct side. **Two maps, left and right.** `right` starts as the frequency of the whole array; `left` starts empty. As we walk left-to-right and reach element `a`, we first **decrement `right[a]`** — `a` is the middle now, no longer an available right-partner. Then everything still in `right` is strictly to the right of the current index, and everything in `left` is strictly to the left. That positional invariant is what enforces `i < j < k`. **Why we multiply.** For middle `a`, there are `c1 = left[a/r]` valid first elements and `c2 = right[a·r]` valid third elements, each completely independent. Combining them is a Cartesian product, so the contribution is `c1 · c2`, summed over all middles. **The divisibility guard.** `a/r` must be an integer to be a real array value. We only read `left[a/r]` when `a % r == 0`; otherwise `c1 = 0`. Skipping this guard would look up a fractional or truncated key and overcount. **Overflow.** The grand total is a sum of products that can reach ~n³/6 (all equal, `r = 1`). That overflows 32-bit ints, so the accumulator must be `long` in Java (Python ints are unbounded, but the same care matters when porting). Time complexity: O(n). Space complexity: O(n).

Arrays & Hashing · 71 of 83 · 9 min

You are given an array arr of n integers and a positive integer r. A triplet (arr[i], arr[j], arr[k]) is a geometric progression with ratio r if i < j < k and arr[j] = arr[i]·r and arr[k] = arr[j]·r.

Return the number of such index triplets. Because values can repeat, two triplets are different if any of their indices differ.

In plain English

Count ordered position triplets whose values are `x, x·r, x·r²`. Duplicates matter: if value `x·r` appears at three middle positions, each can anchor several triplets. The clean decomposition is to treat every element as the middle term and multiply the count of valid predecessors on its left by the count of valid successors on its right.

Examples

Example 1

Input: arr = [1, 2, 2, 4], r = 2
Output: 2
Note: GP 1·2·4. The middle value 2 sits at indices 1 and 2; each pairs the 1 at index 0 with the 4 at index 3 → 2 triplets.

Example 2

Input: arr = [1, 3, 9, 9, 27, 81], r = 3
Output: 6
Note: Three GP shapes (1,3,9), (3,9,27), (9,27,81). The doubled 9 doubles each adjacent shape → 2 + 2 + 2 = 6.

Example 3

Input: arr = [1, 5, 5, 25, 125], r = 5
Output: 4
Note: (1,5,25) with two choices of middle 5 → 2, plus (5,25,125) with two choices of first 5 → 2. Total 4.

Constraints

1 ≤ n ≤ 10⁵
1 ≤ r ≤ 10⁹
1 ≤ arr[i] ≤ 10⁹
The answer can exceed 32-bit range — use 64-bit (long)

Clarifying questions4First question: Do we count index triplets or distinct value triplets?Explore questions

Q1.Do we count index triplets or distinct value triplets?
Index triplets. With arr = [1, 2, 2, 4], r = 2 the answer is 2 because the middle value 2 occurs at two indices, each pairing the same 1 and 4.
Q2.Can the ratio be 1?
Yes. Then every triplet of equal values counts — arr = [1, 1, 1, 1], r = 1 gives C(4,3) = 4. This is exactly the case that overflows int for large n.
Q3.Are values guaranteed positive integers?
Yes, so divisibility (`a % r == 0`) is a valid way to test whether the predecessor `a/r` is an integer.
Q4.Do i < j < k strictly hold?
Yes — strictly increasing indices, which is why we decrement the right map for the current element before looking up partners.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Count index triplets (i < j < k) whose values form a geometric progression with common ratio `r`: `arr[j] = arr[i]·r` and `arr[k] = arr[j]·r`. Treat each element as the **middle** of a triplet and keep two frequency maps — `left` (counts of elements already passed) and `right` (counts of elements still ahead). For middle value `a`, the answer contribution is `left[a/r] · right[a·r]`. Accumulate into a **long** — the count can exceed `int` range (e.g. all-equal arrays with `r = 1`).

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you reframe a triple-nested search as 'fix the middle, count partners on each side', and whether you anticipate integer overflow on the count.

Where candidates slip

Forgetting `a % r == 0` (counting bogus predecessors), counting the current element on both sides because you didn't decrement `right` first, or using `int` and overflowing on all-equal inputs.

How to stand out

Explain why the middle element is the right pivot (it uniquely determines both partners as `a/r` and `a·r`), and call out the overflow before the interviewer does — switch the accumulator to `long`.

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Brute Force — Triple Nested Scan	`O(n³)`	`O(1)`	Say it first to nail down the definition of a valid triplet, then explain why it's too slow for n = 10⁵.	Read
2	Two Frequency Maps — Fix the Middle (Optimal)Optimal	`O(n)`	`O(n)`	The answer they want: linear time by treating each element as the middle term.	Read

Interactive decision treeInteractiveChoose the right approachFollow the branches and learn why each constraint changes the solution.First decision previewElement a as MIDDLE terma % r == 0 ?NoYesExplore the full tree

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 2

Brute Force — Triple Nested Scan

TimeO(n³)SpaceO(1)

Say it first to nail down the definition of a valid triplet, then explain why it's too slow for n = 10⁵.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

A triplet needs three increasing indices i < j < k. What's the most direct way to examine every such triple?

2Hint 2Explore hint

For each (i, j, k) check the two ratio conditions: arr[j] == arr[i]·r and arr[k] == arr[j]·r.

3Hint 3Explore hint

Three nested loops, increment a counter on every match. Correct, but O(n³).

A · Core idea

The most literal reading: enumerate every ordered triple of indices i < j < k and test whether the values form a geometric progression with ratio r.

Why three loops with j > i and k > j. The triplet is ordered by position, so the inner loops must start past the outer index to avoid reusing a position and to avoid counting the same index set in a different order. That guarantees each index triple is examined exactly once.

Why multiplication, not addition, in the test. We compare arr[j] == arr[i]·r. Working with the product (rather than dividing) sidesteps integer-division pitfalls when a value isn't divisible by r.

Why we don't ship it. C(n,3) for n = 10⁵ is ~1.6×10¹⁴ iterations — utterly infeasible. It only demonstrates the definition; the frequency-map version is the real answer.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

arr = [1, 2, 2, 4], r = 2

Array state

i=0,j=1,k=3

1,2,4 form a GP → count

i ↓

[0]

j ↓

[1]

[2]

k ↓

[3]

Current pointerResolved stateNot processed

Final result2

C · Code with teaching comments

Reference implementation previewpublic long countTriplets(List<Long> arr, long r) { int n = arr.size(); long count = 0; for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) {Explore the full code

solution.javaJava

Brute Force — Triple Nested Scan — reference

2 teaching notes

1
public long countTriplets(List<Long> arr, long r) {
2
    int n = arr.size();
3
    // Even the brute force needs long: the count itself can overflow int.
4
    long count = 0;
5
    for (int i = 0; i < n; i++) {
6
        for (int j = i + 1; j < n; j++) {
7
            // Prune early — if the middle isn't arr[i]·r, no k can fix it, so skip the
8
            // inner loop.
9
            if (arr.get(j) != arr.get(i) * r) continue;
10
            for (int k = j + 1; k < n; k++) {
11
                if (arr.get(k) == arr.get(j) * r) {
12
                    count++;
13
                }
14
            }
15
        }
16
    }
17
    return count;
18
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.18 lines

D · Why it works and complexityO(n³) timeO(1) spaceOpen the invariant and proofExplore the proof

The brute force makes the contract explicit: a triplet is an ordered (i, j, k) with two chained ratio equalities. Holding that picture lets you see the next step — the middle index j fully determines what the other two values must be.

ComplexityO(n³) time, O(1) space — Choosing 3 of n ordered indices is C(n,3) ≈ n³/6 triples, each checked in O(1).

E · Edge cases and pitfalls5arr = [1, 1, 1], r = 1 — Single triplet of equal values → 1.Explore edge cases

Edge cases handled

arr = [1, 1, 1], r = 1Single triplet of equal values → 1.
arr = [1, 2, 4], r = 3No value equals its predecessor·3 → 0.

Pitfalls

Using int for count — overflows on large all-equal arrays even though the loop logic is correct.
Dividing instead of multiplying in the ratio test — breaks when a value isn't divisible by r.
Shipping O(n³) on n = 10⁵ — it will time out badly.

03.2

Approach 2 of 2 · Optimal

Two Frequency Maps — Fix the Middle (Optimal)

TimeO(n)SpaceO(n)

The answer they want: linear time by treating each element as the middle term.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

If you fix the middle element of value a, what must the first and third values be? Exactly a/r and a·r.

2Hint 2Explore hint

Keep two maps: left counts of elements already seen, right counts of elements not yet processed. As you advance, move the current element from right to left.

3Hint 3Explore hint

For middle a, the number of triplets centered here is left[a/r] · right[a·r] — every valid left pairs with every valid right.

A · Core idea

The key reframe: stop enumerating triples and instead fix the middle element. If the middle value is a, the geometric progression forces the first value to be a/r and the third to be a·r. Those are uniquely determined, so the only question is how many of each exist on the correct side.

Two maps, left and right. right starts as the frequency of the whole array; left starts empty. As we walk left-to-right and reach element a, we first decrement `right[a]` — a is the middle now, no longer an available right-partner. Then everything still in right is strictly to the right of the current index, and everything in left is strictly to the left. That positional invariant is what enforces i < j < k.

Why we multiply. For middle a, there are c1 = left[a/r] valid first elements and c2 = right[a·r] valid third elements, each completely independent. Combining them is a Cartesian product, so the contribution is c1 · c2, summed over all middles.

The divisibility guard. a/r must be an integer to be a real array value. We only read left[a/r] when a % r == 0; otherwise c1 = 0. Skipping this guard would look up a fractional or truncated key and overcount.

Overflow. The grand total is a sum of products that can reach ~n³/6 (all equal, r = 1). That overflows 32-bit ints, so the accumulator must be long in Java (Python ints are unbounded, but the same care matters when porting).

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

arr = [1, 2, 2, 4], r = 2

Hash-map state

a=2 (index 1)

lookup 4

ValueIndex / state

2→ 1

4→ 1

Match found

c1=left[1]=1, c2=right[4]=1 → +1

Final result2

C · Code with teaching comments

solution.javaJava

Two Frequency Maps — Fix the Middle (Optimal) — optimal

4 teaching notes

1
public long countTriplets(List<Long> arr, long r) {
2
    Map<Long, Long> left = new HashMap<>();
3
    Map<Long, Long> right = new HashMap<>();
4
    for (long a : arr) {
5
        right.merge(a, 1L, Long::sum);
6
    }
7
    long count = 0;
8
    for (long a : arr) {
9
        // Remove the current element from the right side first so it can't be its own
10
        // right partner.
11
        right.merge(a, -1L, Long::sum);
12
        // Only look up a/r when it's an integer; otherwise there is no valid
13
        // predecessor.
14
        long c1 = (a % r == 0) ? left.getOrDefault(a / r, 0L) : 0L;
15
        long c2 = right.getOrDefault(a * r, 0L);
16
        // Cartesian product of valid lefts and rights — and count is long to avoid
17
        // overflow.
18
        count += c1 * c2;
19
        // After processing, a becomes available as a future predecessor.
20
        left.merge(a, 1L, Long::sum);
21
    }
22
    return count;
23
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.23 lines

D · Why it works and complexityO(n) timeO(n) spaceOpen the invariant and proofExplore the proof

Fixing the middle term is the unlock: it converts a search over triples into two independent counting questions answered in O(1) by hash maps. The same 'pivot on the center, multiply the sides' trick appears in counting arithmetic triplets and palindromic/symmetric subsequence counts.

ComplexityO(n) time, O(n) space — One pass; each step does O(1) map operations. Both maps hold at most n distinct keys → O(n) time and space.

E · Edge cases and pitfalls5arr = [1,1,1,1], r = 1 — Every choice of 3 indices counts → C(4,3) = 4. Demonstrates why long is required at scale.Explore edge cases

Edge cases handled

arr = [1,1,1,1], r = 1Every choice of 3 indices counts → C(4,3) = 4. Demonstrates why long is required at scale.
arr = [1, 2, 4], r = 2Single GP → 1, with right correctly emptied as we advance.

Pitfalls

Skipping the `a % r == 0` guard — reads a wrong key and overcounts.
Decrementing right after the lookup — the current element wrongly counts as its own partner.
Using int for the accumulator — overflows on all-equal arrays with r = 1.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Editable code previewpublic long countTriplets(List<Long> arr, long r) { Map<Long, Long> left = new HashMap<>(); Map<Long, Long> right = new HashMap<>(); for (long a : arr) { right.merge(a, 1L, Long::sum);Explore the playground

Try it — Java· run a complete program; method snippets need a driver

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Integer overflow on the count

With arr all equal and r = 1, the answer is C(n,3) ≈ n³/6 which exceeds 2³¹ for n in the thousands. An int silently wraps to a wrong (often negative) value.

Explore the code comparison

Don't write this

int count = 0;
// ... count += c1 * c2;

Write this instead

long count = 0;
// ... count += c1 * c2;

Missing the divisibility guard

If a is not divisible by r, a/r truncates (Java) or is a fraction (math), so left[a/r] points at the wrong key and overcounts.

Explore the code comparison

Don't write this

c1 = left[a // r]
c2 = right[a * r]

Write this instead

c1 = left[a // r] if a % r == 0 else 0
c2 = right[a * r]

Decrement order on the right map

If you read right[a·r] before removing the current a, an element can be counted as its own successor when r = 1.

Explore the code comparison

Don't write this

c2 = right[a * r]
right[a] -= 1

Write this instead

right[a] -= 1
c2 = right[a * r]

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Fix the middle element + two frequency maps (left/right)

Code pattern to memorize

right = freq(arr)        # everything starts on the right
left  = {}
for a in arr:
    right[a] -= 1                       # a leaves the right side
    c1 = left[a // r] if a % r == 0 else 0
    c2 = right[a * r]
    count += c1 * c2                    # use long
    left[a] += 1                        # a joins the left side

Rules to remember

1Iterate with each element as the middle of the GP — then the predecessor is a/r (to the left) and the successor is a·r (to the right).
2Decrement right[a] before the lookup so the current element is never counted as its own left or right partner.
3Guard the predecessor with a % r == 0 — if a isn't divisible by r, no integer a/r exists and left[a/r] is meaningless.
4Use long for the running count: with arr = [1,1,…,1] and r = 1 the answer is C(n,3) ≈ n³/6, which overflows a 32-bit int well before n = 10⁵.
5Multiply the two counts (c1 · c2) — every left predecessor pairs with every right successor, so it's a product, not a sum.

Use this pattern when

Counting triplets/tuples in a fixed multiplicative or additive relation
You can fix the **middle** element and independently count valid left and right partners
Order matters (i < j < k) and you need counts, not the triplets themselves
Values can repeat, so you need frequencies rather than a seen/not-seen set

Choose another pattern when

You must return the actual triplets, not a count → enumeration, not frequency products
The relation is additive over a sorted array (3Sum) → sort + two pointers fits better
No repeated values and tiny n → the O(n²)/O(n³) brute force is fine and simpler
Ratio can be fractional and values aren't integers → division/divisibility guard breaks down

Interview takeaway

When you must count ordered triplets in a relation, fix the middle element and ask two independent questions — 'how many valid lefts?' and 'how many valid rights?' — then multiply. Two frequency maps answer both in O(1), turning O(n³) into O(n).

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Transferable patternFix-the-middle counting with twin frequency maps. When ordered triplets obey a relation that uniquely determines the outer terms from the middle, count valid lefts and rights independently and multiply — O(n) instead of O(n³). Mind the overflow on the count.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Count Pairs with given sum
Same frequency-map idea but for additive pairs instead of multiplicative triplets.
3Sum
Coming soon
Additive triplets over a sorted array — sort then two pointers.
Arithmetic Triplets
Coming soon
Fix the middle and look for value − d and value + d in a set.

Same pattern

←

Count Pairs with given sum

Continue · Next problem

Gridland Metro

mediumArraysFrequently asked

Count Triplets

Arrays & Hashing · 71 of 83 · 9 min

Return the number of such index triplets. Because values can repeat, two triplets are different if any of their indices differ.

In plain English

Examples

Example 1

Input: arr = [1, 2, 2, 4], r = 2
Output: 2
Note: GP 1·2·4. The middle value 2 sits at indices 1 and 2; each pairs the 1 at index 0 with the 4 at index 3 → 2 triplets.

Example 2

Input: arr = [1, 3, 9, 9, 27, 81], r = 3
Output: 6
Note: Three GP shapes (1,3,9), (3,9,27), (9,27,81). The doubled 9 doubles each adjacent shape → 2 + 2 + 2 = 6.

Example 3

Input: arr = [1, 5, 5, 25, 125], r = 5
Output: 4
Note: (1,5,25) with two choices of middle 5 → 2, plus (5,25,125) with two choices of first 5 → 2. Total 4.

Constraints

1 ≤ n ≤ 10⁵
1 ≤ r ≤ 10⁹
1 ≤ arr[i] ≤ 10⁹
The answer can exceed 32-bit range — use 64-bit (long)

Clarifying questions4First question: Do we count index triplets or distinct value triplets?Explore questions

Q1.Do we count index triplets or distinct value triplets?
Index triplets. With arr = [1, 2, 2, 4], r = 2 the answer is 2 because the middle value 2 occurs at two indices, each pairing the same 1 and 4.
Q2.Can the ratio be 1?
Yes. Then every triplet of equal values counts — arr = [1, 1, 1, 1], r = 1 gives C(4,3) = 4. This is exactly the case that overflows int for large n.
Q3.Are values guaranteed positive integers?
Yes, so divisibility (`a % r == 0`) is a valid way to test whether the predecessor `a/r` is an integer.
Q4.Do i < j < k strictly hold?
Yes — strictly increasing indices, which is why we decrement the right map for the current element before looking up partners.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you reframe a triple-nested search as 'fix the middle, count partners on each side', and whether you anticipate integer overflow on the count.

Where candidates slip

Forgetting `a % r == 0` (counting bogus predecessors), counting the current element on both sides because you didn't decrement `right` first, or using `int` and overflowing on all-equal inputs.

How to stand out

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Brute Force — Triple Nested Scan	`O(n³)`	`O(1)`	Say it first to nail down the definition of a valid triplet, then explain why it's too slow for n = 10⁵.	Read
2	Two Frequency Maps — Fix the Middle (Optimal)Optimal	`O(n)`	`O(n)`	The answer they want: linear time by treating each element as the middle term.	Read

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 2

Brute Force — Triple Nested Scan

TimeO(n³)SpaceO(1)

Say it first to nail down the definition of a valid triplet, then explain why it's too slow for n = 10⁵.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

A triplet needs three increasing indices i < j < k. What's the most direct way to examine every such triple?

2Hint 2Explore hint

For each (i, j, k) check the two ratio conditions: arr[j] == arr[i]·r and arr[k] == arr[j]·r.

3Hint 3Explore hint

Three nested loops, increment a counter on every match. Correct, but O(n³).

A · Core idea

The most literal reading: enumerate every ordered triple of indices i < j < k and test whether the values form a geometric progression with ratio r.

Why we don't ship it. C(n,3) for n = 10⁵ is ~1.6×10¹⁴ iterations — utterly infeasible. It only demonstrates the definition; the frequency-map version is the real answer.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

arr = [1, 2, 2, 4], r = 2

Array state

i=0,j=1,k=3

1,2,4 form a GP → count

i ↓

[0]

j ↓

[1]

[2]

k ↓

[3]

Current pointerResolved stateNot processed

Final result2

C · Code with teaching comments

solution.javaJava

Brute Force — Triple Nested Scan — reference

2 teaching notes

1
public long countTriplets(List<Long> arr, long r) {
2
    int n = arr.size();
3
    // Even the brute force needs long: the count itself can overflow int.
4
    long count = 0;
5
    for (int i = 0; i < n; i++) {
6
        for (int j = i + 1; j < n; j++) {
7
            // Prune early — if the middle isn't arr[i]·r, no k can fix it, so skip the
8
            // inner loop.
9
            if (arr.get(j) != arr.get(i) * r) continue;
10
            for (int k = j + 1; k < n; k++) {
11
                if (arr.get(k) == arr.get(j) * r) {
12
                    count++;
13
                }
14
            }
15
        }
16
    }
17
    return count;
18
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.18 lines

D · Why it works and complexityO(n³) timeO(1) spaceOpen the invariant and proofExplore the proof

ComplexityO(n³) time, O(1) space — Choosing 3 of n ordered indices is C(n,3) ≈ n³/6 triples, each checked in O(1).

E · Edge cases and pitfalls5arr = [1, 1, 1], r = 1 — Single triplet of equal values → 1.Explore edge cases

Edge cases handled

arr = [1, 1, 1], r = 1Single triplet of equal values → 1.
arr = [1, 2, 4], r = 3No value equals its predecessor·3 → 0.

Pitfalls

Using int for count — overflows on large all-equal arrays even though the loop logic is correct.
Dividing instead of multiplying in the ratio test — breaks when a value isn't divisible by r.
Shipping O(n³) on n = 10⁵ — it will time out badly.

03.2

Approach 2 of 2 · Optimal

Two Frequency Maps — Fix the Middle (Optimal)

TimeO(n)SpaceO(n)

The answer they want: linear time by treating each element as the middle term.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

If you fix the middle element of value a, what must the first and third values be? Exactly a/r and a·r.

2Hint 2Explore hint

Keep two maps: left counts of elements already seen, right counts of elements not yet processed. As you advance, move the current element from right to left.

3Hint 3Explore hint

For middle a, the number of triplets centered here is left[a/r] · right[a·r] — every valid left pairs with every valid right.

A · Core idea

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

arr = [1, 2, 2, 4], r = 2

Hash-map state

a=2 (index 1)

lookup 4

ValueIndex / state

2→ 1

4→ 1

Match found

c1=left[1]=1, c2=right[4]=1 → +1

Final result2

C · Code with teaching comments

solution.javaJava

Two Frequency Maps — Fix the Middle (Optimal) — optimal

4 teaching notes

1
public long countTriplets(List<Long> arr, long r) {
2
    Map<Long, Long> left = new HashMap<>();
3
    Map<Long, Long> right = new HashMap<>();
4
    for (long a : arr) {
5
        right.merge(a, 1L, Long::sum);
6
    }
7
    long count = 0;
8
    for (long a : arr) {
9
        // Remove the current element from the right side first so it can't be its own
10
        // right partner.
11
        right.merge(a, -1L, Long::sum);
12
        // Only look up a/r when it's an integer; otherwise there is no valid
13
        // predecessor.
14
        long c1 = (a % r == 0) ? left.getOrDefault(a / r, 0L) : 0L;
15
        long c2 = right.getOrDefault(a * r, 0L);
16
        // Cartesian product of valid lefts and rights — and count is long to avoid
17
        // overflow.
18
        count += c1 * c2;
19
        // After processing, a becomes available as a future predecessor.
20
        left.merge(a, 1L, Long::sum);
21
    }
22
    return count;
23
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.23 lines

D · Why it works and complexityO(n) timeO(n) spaceOpen the invariant and proofExplore the proof

ComplexityO(n) time, O(n) space — One pass; each step does O(1) map operations. Both maps hold at most n distinct keys → O(n) time and space.

E · Edge cases and pitfalls5arr = [1,1,1,1], r = 1 — Every choice of 3 indices counts → C(4,3) = 4. Demonstrates why long is required at scale.Explore edge cases

Edge cases handled

arr = [1,1,1,1], r = 1Every choice of 3 indices counts → C(4,3) = 4. Demonstrates why long is required at scale.
arr = [1, 2, 4], r = 2Single GP → 1, with right correctly emptied as we advance.

Pitfalls

Skipping the `a % r == 0` guard — reads a wrong key and overcounts.
Decrementing right after the lookup — the current element wrongly counts as its own partner.
Using int for the accumulator — overflows on all-equal arrays with r = 1.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Try it — Java· run a complete program; method snippets need a driver

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Integer overflow on the count

With arr all equal and r = 1, the answer is C(n,3) ≈ n³/6 which exceeds 2³¹ for n in the thousands. An int silently wraps to a wrong (often negative) value.

Explore the code comparison

Don't write this

int count = 0;
// ... count += c1 * c2;

Write this instead

long count = 0;
// ... count += c1 * c2;

Missing the divisibility guard

If a is not divisible by r, a/r truncates (Java) or is a fraction (math), so left[a/r] points at the wrong key and overcounts.

Explore the code comparison

Don't write this

c1 = left[a // r]
c2 = right[a * r]

Write this instead

c1 = left[a // r] if a % r == 0 else 0
c2 = right[a * r]

Decrement order on the right map

If you read right[a·r] before removing the current a, an element can be counted as its own successor when r = 1.

Explore the code comparison

Don't write this

c2 = right[a * r]
right[a] -= 1

Write this instead

right[a] -= 1
c2 = right[a * r]

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Fix the middle element + two frequency maps (left/right)

Code pattern to memorize

right = freq(arr)        # everything starts on the right
left  = {}
for a in arr:
    right[a] -= 1                       # a leaves the right side
    c1 = left[a // r] if a % r == 0 else 0
    c2 = right[a * r]
    count += c1 * c2                    # use long
    left[a] += 1                        # a joins the left side

Rules to remember

1Iterate with each element as the middle of the GP — then the predecessor is a/r (to the left) and the successor is a·r (to the right).
2Decrement right[a] before the lookup so the current element is never counted as its own left or right partner.
3Guard the predecessor with a % r == 0 — if a isn't divisible by r, no integer a/r exists and left[a/r] is meaningless.
4Use long for the running count: with arr = [1,1,…,1] and r = 1 the answer is C(n,3) ≈ n³/6, which overflows a 32-bit int well before n = 10⁵.
5Multiply the two counts (c1 · c2) — every left predecessor pairs with every right successor, so it's a product, not a sum.

Use this pattern when

Counting triplets/tuples in a fixed multiplicative or additive relation
You can fix the **middle** element and independently count valid left and right partners
Order matters (i < j < k) and you need counts, not the triplets themselves
Values can repeat, so you need frequencies rather than a seen/not-seen set

Choose another pattern when

You must return the actual triplets, not a count → enumeration, not frequency products
The relation is additive over a sorted array (3Sum) → sort + two pointers fits better
No repeated values and tiny n → the O(n²)/O(n³) brute force is fine and simpler
Ratio can be fractional and values aren't integers → division/divisibility guard breaks down

Interview takeaway

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Count Pairs with given sum
Same frequency-map idea but for additive pairs instead of multiplicative triplets.
3Sum
Coming soon
Additive triplets over a sorted array — sort then two pointers.
Arithmetic Triplets
Coming soon
Fix the middle and look for value − d and value + d in a set.

Same pattern

←

Count Pairs with given sum

Continue · Next problem

Gridland Metro