Geometric Sequence Triplets
Given an integer array nums and an integer ratio, count the
number of index triplets (i, j, k) such that i < j < k and
nums[j] == nums[i] * ratio and nums[k] == nums[j] * ratio (i.e.,
the three values at those indices form a geometric sequence with the
given common ratio, in left-to-right order).
Example 1
Input: nums = [1, 2, 4, 2, 4, 8], ratio = 2
Output: 3
Explanation: Valid triplets (by index): (0,1,2), (0,1,4), (0,3,4)
each satisfy nums[j] = nums[i] * 2 and nums[k] = nums[j] * 2.
Example 2
Input: nums = [1, 1, 1], ratio = 1
Output: 1
Explanation: The only triplet is (0, 1, 2), where every value is 1
and 1 * 1 = 1.
Constraints
1 <= nums.length <= 10^5-10^9 <= nums[i] <= 10^9-10^9 <= ratio <= 10^9
A brute-force triple-nested loop is O(n^3). We can bring this down to
O(n) by processing indices left to right and, for each index j
treated as the middle of the triplet, asking two counting
questions: "how many times has nums[j] / ratio appeared to the
left (as a potential i)?" and "how many times will nums[j] * ratio appear to the right (as a potential k)?"
The trick to answering both in O(1) amortized time is to maintain
two hash maps of value -> count: a left_counts map that we build up
as we go, and a right_counts map that starts containing counts for
the entire array and gets decremented as we move past each index
(so at the moment we process index j, right_counts reflects only
indices > j).
For each j, first remove nums[j] from right_counts (since j
itself can't be its own k), then multiply the number of valid
i's by the number of valid k's and add that product to the
answer, then add nums[j] into left_counts before moving on.
from collections import Counter
def geometric_sequence_triplets(nums: list[int], ratio: int) -> int:
left_counts: Counter[int] = Counter()
right_counts: Counter[int] = Counter(nums)
total = 0
for x in nums:
right_counts[x] -= 1 # x is now the middle element, not a right candidate
if ratio != 0:
if x % ratio == 0:
left_partner = x // ratio
right_partner = x * ratio
total += left_counts[left_partner] * right_counts[right_partner]
else:
# ratio == 0 means every "next" value must be 0
right_partner = 0
left_partner = 0
if x == 0:
total += left_counts[left_partner] * right_counts[right_partner]
left_counts[x] += 1
return total
Complexity: O(n) time, since each index is processed once with
O(1) average-case hash map operations. O(n) space for the two
frequency maps. (Note: the x % ratio == 0 guard avoids
non-integer division artifacts when x is not evenly divisible by
ratio, in which case no valid i could exist anyway.)
Share this question