# Count Special Triplets
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/count-special-triplets)
Canonical: https://scaleengineer.com/dsa/problems/count-special-triplets
**Patterns:** [Counting](https://scaleengineer.com/dsa/patterns/counting)
**Data structures:** Array, Hash Table
---
## Problem
You are given an integer array `nums`.

A **special triplet** is defined as a triplet of indices `(i, j, k)` such that:

* `0 <= i < j < k < n`, where `n = nums.length`
* `nums[i] == nums[j] * 2`
* `nums[k] == nums[j] * 2`

Return the total number of **special triplets** in the array.

Since the answer may be large, return it **modulo** `109 + 7`.

**Example 1:**

**Input:** nums = \[6,3,6\]

**Output:** 1

**Explanation:**

The only special triplet is `(i, j, k) = (0, 1, 2)`, where:

* `nums[0] = 6`, `nums[1] = 3`, `nums[2] = 6`
* `nums[0] = nums[1] * 2 = 3 * 2 = 6`
* `nums[2] = nums[1] * 2 = 3 * 2 = 6`

**Example 2:**

**Input:** nums = \[0,1,0,0\]

**Output:** 1

**Explanation:**

The only special triplet is `(i, j, k) = (0, 2, 3)`, where:

* `nums[0] = 0`, `nums[2] = 0`, `nums[3] = 0`
* `nums[0] = nums[2] * 2 = 0 * 2 = 0`
* `nums[3] = nums[2] * 2 = 0 * 2 = 0`

**Example 3:**

**Input:** nums = \[8,4,2,8,4\]

**Output:** 2

**Explanation:**

There are exactly two special triplets:

* `(i, j, k) = (0, 1, 3)`  
  * `nums[0] = 8`, `nums[1] = 4`, `nums[3] = 8`
  * `nums[0] = nums[1] * 2 = 4 * 2 = 8`
  * `nums[3] = nums[1] * 2 = 4 * 2 = 8`
* `(i, j, k) = (1, 2, 4)`  
  * `nums[1] = 4`, `nums[2] = 2`, `nums[4] = 4`
  * `nums[1] = nums[2] * 2 = 2 * 2 = 4`
  * `nums[4] = nums[2] * 2 = 2 * 2 = 4`

**Constraints:**

* `3 <= n == nums.length <= 105`
* `0 <= nums[i] <= 105`

# Approaches
## Brute-Force Triple Nested Loop
The most straightforward approach is to use three nested loops to check every possible triplet of indices `(i, j, k)` that satisfy `i < j < k`. For each triplet, we verify if it meets the special triplet conditions. This method is easy to conceptualize but computationally very expensive.
**Time:** O(N^3) - Three nested loops iterate through the array, where N is the length of `nums`. This results in a cubic time complexity. · **Space:** O(1) - Constant extra space is used.
**Pros:** Simple to understand and implement.; Requires no extra space.
**Cons:** Extremely inefficient and will lead to a 'Time Limit Exceeded' error for the given constraints.
### Explanation
This method iterates through all combinations of three distinct indices `i`, `j`, and `k` from the array. The loops are structured to ensure that `i < j < k`, which is a requirement for the triplet. For each valid combination of indices, it performs a check to see if `nums[i]` and `nums[k]` are both equal to `nums[j] * 2`. A counter is maintained to keep track of how many such triplets are found.

```java
class Solution {
    public int countSpecialTriplets(int[] nums) {
        int n = nums.length;
        long count = 0;
        int MOD = 1_000_000_007;

        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                for (int k = j + 1; k < n; k++) {
                    // Use long for multiplication to prevent potential overflow, though not strictly necessary with given constraints.
                    if ((long)nums[i] == (long)nums[j] * 2 && (long)nums[k] == (long)nums[j] * 2) {
                        count++;
                    }
                }
            }
        }
        return (int)(count % MOD);
    }
}
```
### Algorithm
- Initialize a counter `count` to 0.
- Use three nested loops to iterate through all possible triplets of indices `(i, j, k)` such that `0 <= i < j < k < n`.
- Inside the innermost loop, check if the conditions `nums[i] == nums[j] * 2` and `nums[k] == nums[j] * 2` are met.
- If the conditions are true, increment the `count`.
- After iterating through all triplets, return `count` modulo `10^9 + 7`.

## Fixing the Middle Element
We can improve upon the brute-force approach by changing our iteration strategy. Instead of iterating through all triplets, we can fix the middle index `j` and then search for the required `i`'s and `k`'s. For each `j`, we need to find how many indices `i < j` have `nums[i] == 2 * nums[j]` and how many indices `k > j` have `nums[k] == 2 * nums[j]`. The product of these two counts gives the number of special triplets for that specific `j`.
**Time:** O(N^2) - For each element `j`, we scan its left and right subarrays. The total operations are proportional to the sum of `j + (n-j)` for all `j`, which simplifies to O(N^2). · **Space:** O(1) - No significant extra space is used besides a few variables for counting.
**Pros:** More efficient than the O(N^3) brute-force approach.; Still relatively simple to reason about.
**Cons:** This approach is still too slow for the given constraints (`N <= 10^5`) and will likely time out.
### Explanation
The core idea is to iterate through each possible middle element `nums[j]`. For a fixed `j`, we need to find a pair of indices `(i, k)` such that `i < j < k` and `nums[i] = nums[k] = 2 * nums[j]`. We can do this by scanning the subarray to the left of `j` to count valid `i`'s and the subarray to the right of `j` to count valid `k`'s. The total number of triplets is the sum of these products over all possible `j`.

```java
class Solution {
    public int countSpecialTriplets(int[] nums) {
        int n = nums.length;
        long totalTriplets = 0;
        int MOD = 1_000_000_007;

        for (int j = 1; j < n - 1; j++) {
            long targetVal = (long)nums[j] * 2;
            long count_i = 0;
            for (int i = 0; i < j; i++) {
                if (nums[i] == targetVal) {
                    count_i++;
                }
            }

            if (count_i == 0) continue;

            long count_k = 0;
            for (int k = j + 1; k < n; k++) {
                if (nums[k] == targetVal) {
                    count_k++;
                }
            }
            
            totalTriplets = (totalTriplets + (count_i * count_k));
        }
        
        return (int)(totalTriplets % MOD);
    }
}
```
### Algorithm
- Initialize a total count `totalTriplets` to 0.
- Iterate through the array with an index `j` from `1` to `n-2`, considering `nums[j]` as the middle element of a potential triplet.
- For each `j`, calculate the `targetVal = nums[j] * 2`.
- Initialize two counters, `count_i = 0` and `count_k = 0`.
- In a nested loop, iterate from `i = 0` to `j-1` to find the number of elements `nums[i]` equal to `targetVal`. Store this in `count_i`.
- In another nested loop, iterate from `k = j+1` to `n-1` to find the number of elements `nums[k]` equal to `targetVal`. Store this in `count_k`.
- The number of triplets for the current `j` is `count_i * count_k`. Add this product to `totalTriplets`.
- After the main loop finishes, return `totalTriplets` modulo `10^9 + 7`.

## Single Pass with Frequency Counting
This is the most efficient approach, achieving a linear time complexity. We can optimize the O(N^2) approach by avoiding the repeated scans for `count_i` and `count_k`. We iterate through the array, considering each element `nums[j]` as the middle element. We maintain two frequency maps (or arrays, given the value constraints): one for counts of numbers to the left of `j` (`leftFreq`) and one for counts to the right (`rightFreq`). As we iterate from left to right, we can update these counts in O(1) time, allowing us to find `count_i` and `count_k` instantly.
**Time:** O(N + M) - We iterate through the array of size N a constant number of times. The complexity is linear in the size of the input array and the range of its values. Since M is fixed by the constraints, this is effectively O(N). · **Space:** O(M) - Where M is the maximum possible value of `nums[j]*2`. Given the constraints, M is approximately `2*10^5`, which is a constant amount of space.
**Pros:** Optimal time complexity, making it very efficient for large inputs.; Passes the given constraints with ease.
**Cons:** Requires extra space proportional to the maximum possible value of `nums[j]*2`, which might be large if the value constraints were different.
### Explanation
The key to this optimization is to process the array in a single pass while maintaining counts of numbers seen so far (left side) and numbers yet to be seen (right side). 

First, we pre-calculate the frequency of all numbers in the array and store them in `rightFreq`. Then, we iterate through `nums`. For each element `nums[j]`, we first 'remove' it from the right side by decrementing its count in `rightFreq`. Then, we can find the number of special triplets with `nums[j]` as the middle element. The number of valid `i`'s is the count of `2 * nums[j]` in `leftFreq`, and the number of valid `k`'s is the count of `2 * nums[j]` in the updated `rightFreq`. After calculating the contribution for `j`, we 'add' `nums[j]` to the left side by incrementing its count in `leftFreq` before moving to the next element.

```java
class Solution {
    public int countSpecialTriplets(int[] nums) {
        int n = nums.length;
        int MOD = 1_000_000_007;
        
        // Constraints: 0 <= nums[i] <= 10^5
        // target_val = nums[j] * 2, so max target_val is 2 * 10^5
        int maxPossibleVal = 200001;

        int[] rightFreq = new int[maxPossibleVal];
        for (int num : nums) {
            rightFreq[num]++;
        }

        int[] leftFreq = new int[maxPossibleVal];
        long totalTriplets = 0;

        for (int val_j : nums) {
            // Move val_j from the right side to the middle
            rightFreq[val_j]--;

            long targetVal = (long)val_j * 2;
            if (targetVal < maxPossibleVal) {
                long count_i = leftFreq[(int)targetVal];
                long count_k = rightFreq[(int)targetVal];
                totalTriplets += count_i * count_k;
            }

            // Move val_j from the middle to the left side
            leftFreq[val_j]++;
        }

        return (int)(totalTriplets % MOD);
    }
}
```
### Algorithm
- Define `MOD = 10^9 + 7`.
- Based on constraints, the maximum value for `nums[j]*2` is `2*10^5`. Create two frequency arrays, `leftFreq` and `rightFreq`, of size `200001`, initialized to zero.
- Populate `rightFreq` by iterating through `nums` once. `rightFreq[x]` will store the total count of number `x` in the array.
- Initialize `totalTriplets = 0` (as a long to prevent overflow).
- Iterate through the input array `nums` with index `j`.
- In each iteration, let `val_j = nums[j]`.
  - First, decrement `rightFreq[val_j]`. This signifies that `nums[j]` is no longer on the 'right' side of the current position.
  - Calculate `targetVal = val_j * 2`.
  - If `targetVal` is within the bounds of the frequency arrays:
    - Get the count of `targetVal` on the left: `count_i = leftFreq[targetVal]`.
    - Get the count of `targetVal` on the right: `count_k = rightFreq[targetVal]`.
    - Add the product `(long)count_i * count_k` to `totalTriplets`.
  - Finally, increment `leftFreq[val_j]`. This moves `nums[j]` to the 'left' side for subsequent iterations.
- After the loop, return `totalTriplets % MOD`.