# Problem Understanding In this problem, we are given a sequence of numbers and a common ratio $r$. Our task is to count all triplets $(i, j, k)$ such that $i < j < k$ and the three numbers form a geometric progression. This means that if the numbers at these indices are $a_i$, $a_j$, and $a_k$, then they must satisfy: $$ a_j = a_i \times r \quad \text{and} \quad a_k = a_j \times r. $$ Essentially, we need to find three numbers in order from the sequence which have a constant multiplicative factor $r$ between consecutive numbers. Special cases include: - When $r = 1$, any triplet of identical numbers qualifies. - When $r = 0$ (if allowed by the problem interpretation), the situation should be handled carefully because multiplying by $0$ gives ambiguity, though typically $r$ is taken as a non-zero value. The challenge is to count these triplets efficiently, given that a brute force approach would have a prohibitively high time complexity when $n$ (the number of elements) is large. # Solution Analysis The key idea is to use a one-pass approach with hash maps (or dictionaries) to keep track of potential pairs and triplets. 1. Two hash maps are maintained: - The first, called `potential_pairs`, records how many times a number can be the first element of a potential triplet (i.e., how many times we have seen an element that could begin a triplet). - The second, called `potential_triplets`, records the number of potential triplets waiting for a valid third element. Essentially, it counts the number of times we have seen a valid pair $(a_i, a_j)$ that can be extended by some future element $a_k$ to complete the progression. 2. As we iterate through the sequence: - For each current element, consider it as a possible third element in a triplet. If the current element appears as a key in `potential_triplets`, then it means there are that many pairs waiting for this element to form a complete geometric progression. We add that count to our result. - Next, treat the current element as a potential second element. Check if it can form a new pair with any previous element (i.e., using `a_i = current / r` if $r$ divides the current element appropriately). If so, update `potential_triplets` accordingly. - Always register the current element in the `potential_pairs` map since it can potentially start a new triplet. 3. The overall approach is to dynamically update counts in these hash maps, ensuring that in one pass through the sequence, we cover all possible triplets without needing nested loops to try every possible combination. # Time and Space Complexity Analysis - **Time Complexity:** The solution iterates over the list of $n$ elements exactly once. For each element, the updates/queries in the hash maps are typically $O(1)$ (amortized). As a result, the overall time complexity is $O(n)$. - **Space Complexity:** The space is determined by the storage used by the hash maps. In the worst case, if all numbers are distinct, the hash maps could collectively store up to $O(n)$ entries. Therefore, the space complexity is also $O(n)$.