#108

Geometric Sequence Triplets

medium

arrayhash-table

Given an array of integers nums and an integer r, count the index triplets (i, j, k) with i < j < k that form a geometric progression with common ratio r — that is, nums[j] === nums[i] * r and nums[k] === nums[j] * r.

Triplets are counted per index combination, so equal values at different positions produce distinct triplets. Return the total count.

Example

Input: nums = [2,1,2,4,8,8], r = 2

Output: 5

With middle value 4 (index 3): left has two 2s (indices 0, 2) and right has two 8s (indices 4, 5) → 2×2 = 4 triplets. With middle value 2 (index 2): left has one 1 (index 1) and right has one 4 (index 3) → 1 triplet. Total 5.

Constraints

1 <= nums.length <= 10^5
1 <= nums[i] <= 10^9
1 <= r <= 10^9

Intuition

A first pass checks every index triple (i, j, k) with i < j < k and counts the ones that step up by the ratio r — nums[j] === nums[i] * r and nums[k] === nums[j] * r.

function geometricTriplets(nums, r) {
  let count = 0;
  // Check every distinct triple of indexes in order.
  for (let i = 0; i < nums.length; i++) {
    for (let j = i + 1; j < nums.length; j++) {
      for (let k = j + 1; k < nums.length; k++) {
        // A geometric step needs the middle to be i × r and the last to be the middle × r.
        if (nums[j] === nums[i] * r && nums[k] === nums[j] * r) {
          count++; // each qualifying index combination is its own triplet
        }
      }
    }
  }
  return count;
}

Brute force — every ordered triple, count the geometric ones: O(n³).

This is O(n³) — far more work than necessary. Can we do better?

Notice that a triplet is pinned down by its middle element. If we fix nums[j] as the middle, a valid triplet just needs a left partner equal to nums[j] / r somewhere before j, and a right partner equal to nums[j] * r somewhere after j. The number of triplets centred on j is then simply (# of nums[j]/r on the left) × (# of nums[j]*r on the right) — every left partner can pair with every right partner.

Counting how many of a given value sit on each side is what a frequency map does in O(1), so this is a Hash map problem. Keep two maps: left (values strictly before j) and right (values strictly after j). Seed right with the whole array, then sweep j left to right — before counting, move nums[j] out of right; after counting, add it into left. Because the left partner must be the exact integer nums[j] / r, guard the division with nums[j] % r === 0. (The stored solution iterates the middle directly and names it mid rather than indexing nums[j].)

Walking it through:

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

j↓

1 % 2 ≠ 0 → skip

right = {2:2, 4:1}, left = {}. Middle 1 would need a left partner of 1/2 — not an integer, so the guard rejects it. Contributes 0.

j↓

left[1] × right[4] = 1 × 1 = 1

left = {1:1}, right = {2:1, 4:1}. Middle 2 needs 2/2 = 1 on the left (one) and 2×2 = 4 on the right (one). count = 1.

j↓

left[1] × right[4] = 1 × 1 = 1

left = {1:1, 2:1}, right = {4:1}. The second 2 is its own middle — same partners (the 1 and the 4), counted again by index. count = 2.

j↓

left[2] × right[8] = 2 × 0 = 0

left = {1:1, 2:2}, right = {}. Middle 4 has two left partners (the 2s) but needs a 4×2 = 8 after it — none exist. Contributes 0.

total = 2

Sweep done: triplets (0,1,3) and (0,2,3), one per choice of middle 2. Answer: 2.

Optimization

Two frequency maps (middle pivot)

Fix nums[j] as the middle of the triplet. A valid triplet needs a left element equal to nums[j] / r somewhere before j, and a right element equal to nums[j] * r somewhere after j. The count of triplets centered on j is therefore (# of nums[j]/r on the left) × (# of nums[j]*r on the right).

Maintain two frequency maps: left (values strictly before j) and right (values strictly after j). Initialize right with every value, then sweep j left to right — before counting, remove nums[j] from right; after counting, add it to left. Because values can exceed r's multiples, only the integer-exact nums[j] / r matters, so guard with nums[j] % r === 0.

O(n) time, O(n) space.

function geometricTriplets(nums, r) {
  // left counts values already passed; right counts values still ahead of the middle.
  const left = new Map();
  const right = new Map();
  // Seed right with the whole array, so before the sweep every value is "ahead".
  for (const value of nums) right.set(value, (right.get(value) || 0) + 1);

  let count = 0;
  // Treat each element as the middle of a triplet, sweeping left to right.
  for (const mid of nums) {
    // mid is the current middle element: drop it from the "after" side first.
    right.set(mid, right.get(mid) - 1);
    // The left partner must be the exact integer mid / r, else no partner can match.
    if (mid % r === 0) {
      // How many valid left partners (mid / r) and right partners (mid * r) exist.
      const leftCount = left.get(mid / r) || 0;
      const rightCount = right.get(mid * r) || 0;
      // Every left partner pairs with every right partner — that's the product.
      count += leftCount * rightCount;
    }
    // Done with mid as a middle: it now becomes a candidate left partner.
    left.set(mid, (left.get(mid) || 0) + 1);
  }
  return count;
}

Complexity analysis

Time complexity: O(n). Here's why:

One pass seeds the right frequency map with every value — O(n).
The main sweep visits each index once; per index it does a constant number of map operations (one removal from right, two lookups, one insertion into left), each O(1) on average.

There is no nested loop — the brute force's inner two loops are replaced by two constant-time map probes — so the whole thing is O(n), where n is the length of nums.

Space complexity: O(n). Here's why:

The right map starts with one entry per distinct value, up to O(n) of them.
As the sweep proceeds, values shift into the left map, which together with right holds at most O(n) entries.

Both maps together are bounded by the number of distinct values, so the auxiliary space is O(n). The running count is a single integer and isn't counted.

Test cases

Beyond the example above, these are worth thinking through before you submit.

Input	Expected output	Description
nums = [9,3], r = 3	0	Only two elements — a triplet needs three indices.
nums = [2,6,10], r = 3	0	No-solution case: 2×3 = 6, but 6×3 = 18 ≠ 10.
nums = [1,10,100], r = 10	1	Smallest exact chain with r > 1 — one triplet.
nums = [4,4,4,4,4,4], r = 1	20	All equal with r = 1 — every i < j < k qualifies: C(6, 3) = 20.
nums = [2,4,4,8,8], r = 2	4	Overlapping repeats: each of the two 4s pairs with one 2 on the left and two 8s on the right → 2 + 2.

Try it yourself

Write your solution against the real judge before checking the reference.

Open in editor