# Count Special Subsequences
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/count-special-subsequences)
Canonical: https://scaleengineer.com/dsa/problems/count-special-subsequences
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Enumeration](https://scaleengineer.com/dsa/patterns/enumeration)
**Data structures:** Array, Hash Table
---
## Problem
You are given an array `nums` consisting of positive integers.

A **special subsequence** is defined as a subsequence of length 4, represented by indices `(p, q, r, s)`, where `p < q < r < s`. This subsequence **must** satisfy the following conditions:

* `nums[p] * nums[r] == nums[q] * nums[s]`
* There must be _at least_ **one** element between each pair of indices. In other words, `q - p > 1`, `r - q > 1` and `s - r > 1`.

Return the _number_ of different **special** **subsequences** in `nums`.

**Example 1:**

**Input:** nums = \[1,2,3,4,3,6,1\]

**Output:** 1

**Explanation:**

There is one special subsequence in `nums`.

* `(p, q, r, s) = (0, 2, 4, 6)`:  
  * This corresponds to elements `(1, 3, 3, 1)`.
  * `nums[p] * nums[r] = nums[0] * nums[4] = 1 * 3 = 3`
  * `nums[q] * nums[s] = nums[2] * nums[6] = 3 * 1 = 3`

**Example 2:**

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

**Output:** 3

**Explanation:**

There are three special subsequences in `nums`.

* `(p, q, r, s) = (0, 2, 4, 6)`:  
  * This corresponds to elements `(3, 3, 3, 3)`.
  * `nums[p] * nums[r] = nums[0] * nums[4] = 3 * 3 = 9`
  * `nums[q] * nums[s] = nums[2] * nums[6] = 3 * 3 = 9`
* `(p, q, r, s) = (1, 3, 5, 7)`:  
  * This corresponds to elements `(4, 4, 4, 4)`.
  * `nums[p] * nums[r] = nums[1] * nums[5] = 4 * 4 = 16`
  * `nums[q] * nums[s] = nums[3] * nums[7] = 4 * 4 = 16`
* `(p, q, r, s) = (0, 2, 5, 7)`:  
  * This corresponds to elements `(3, 3, 4, 4)`.
  * `nums[p] * nums[r] = nums[0] * nums[5] = 3 * 4 = 12`
  * `nums[q] * nums[s] = nums[2] * nums[7] = 3 * 4 = 12`

**Constraints:**

* `7 <= nums.length <= 1000`
* `1 <= nums[i] <= 1000`

# Approaches
## Brute Force
The most straightforward approach is to check every possible quadruplet of indices `(p, q, r, s)` to see if it forms a special subsequence. We can use four nested loops to generate all valid index combinations that satisfy `p < q < r < s` and the gap conditions `q-p > 1`, `r-q > 1`, `s-r > 1`. For each valid combination, we then check if the product equality `nums[p] * nums[r] == nums[q] * nums[s]` holds. If it does, we increment a counter.
**Time:** O(N^4) - Four nested loops iterate through the array, where N is the length of `nums`. This is too slow for N=1000. · **Space:** O(1) - We only use a few variables to store indices and the count.
**Pros:** Simple to understand and implement.
**Cons:** Extremely inefficient due to four nested loops.; Will time out for the given constraints (N up to 1000).
### Explanation
This method systematically explores all potential special subsequences. The four nested loops ensure that we consider every combination of four distinct indices `(p, q, r, s)` in increasing order. The loop bounds are carefully chosen to enforce the gap conditions. For example, `q` starts from `p+2` to ensure `q-p > 1`. Similarly, `r` starts from `q+2` and `s` from `r+2`. Inside the loops, we perform a simple multiplication and comparison. While simple to understand and implement, its performance is poor for larger inputs.

```java
class Solution {
    public long countSpecialSubsequences(int[] nums) {
        int n = nums.length;
        long count = 0;
        for (int p = 0; p < n; p++) {
            for (int q = p + 2; q < n; q++) {
                for (int r = q + 2; r < n; r++) {
                    for (int s = r + 2; s < n; s++) {
                        if ((long) nums[p] * nums[r] == (long) nums[q] * nums[s]) {
                            count++;
                        }
                    }
                }
            }
        }
        return count;
    }
}
```
### Algorithm
1. Initialize a counter `count` to 0.
2. Use four nested loops to iterate through all possible combinations of indices `(p, q, r, s)`.
3. To satisfy the gap conditions `q-p > 1`, `r-q > 1`, `s-r > 1` directly, the loops can be set up as follows:
   - `p` from `0` to `n-7`
   - `q` from `p+2` to `n-5`
   - `r` from `q+2` to `n-3`
   - `s` from `r+2` to `n-1`
4. Inside the innermost loop, check if the product condition `nums[p] * nums[r] == nums[q] * nums[s]` is met.
5. If the condition is true, increment the `count`.
6. After the loops complete, return `count`.

## Optimized Brute Force with Precomputation
We can improve upon the brute-force approach by reducing one of the nested loops. The core idea is to fix three indices, say `q`, `r`, and `s`, and then efficiently count the number of valid indices `p`. The equation `nums[p] * nums[r] == nums[q] * nums[s]` can be rearranged to find the required value of `nums[p]`: `nums[p] = (nums[q] * nums[s]) / nums[r]`. To quickly find how many times this value appears at an index `p < q-1`, we can precompute the counts of each number up to every index.
**Time:** O(N^3 + N * max_val) - The precomputation takes `O(N * max_val)`. The main calculation involves three nested loops, resulting in `O(N^3)`. For the given constraints, this is approximately `O(N^3)`. · **Space:** O(N * max_val) - For the `prefixCounts` table, where N is array length and `max_val` is the maximum possible value in `nums`.
**Pros:** More efficient than the naive O(N^4) approach.; Reduces one level of nested loops from the calculation phase.
**Cons:** Still too slow for the given constraints, as it has three nested loops.; Requires significant space for the prefix counts table.
### Explanation
First, we pre-process the input array to create a prefix count table, `prefixCounts`. `prefixCounts[i][v]` will store the frequency of the value `v` in the subarray `nums[0...i-1]`. This table can be built in `O(N * max_val)` time.

With this table, we can iterate through all possible triplets of indices `(q, r, s)` that satisfy the ordering and gap conditions. For each triplet, we calculate the value that `nums[p]` must have. Then, we use our `prefixCounts` table to find in `O(1)` time how many indices `p` exist before `q-1` with the required value. Summing these counts up for all valid `(q, r, s)` triplets gives the final answer.

```java
class Solution {
    public long countSpecialSubsequences(int[] nums) {
        int n = nums.length;
        long totalCount = 0;
        int maxVal = 1000;

        // Precompute prefix counts
        int[][] prefixCounts = new int[n + 1][maxVal + 1];
        for (int i = 0; i < n; i++) {
            for (int v = 1; v <= maxVal; v++) {
                prefixCounts[i + 1][v] = prefixCounts[i][v];
            }
            prefixCounts[i + 1][nums[i]]++;
        }

        for (int q = 2; q < n; q++) {
            for (int r = q + 2; r < n; r++) {
                for (int s = r + 2; s < n; s++) {
                    long product = (long) nums[q] * nums[s];
                    if (product % nums[r] == 0) {
                        long target_p_val = product / nums[r];
                        if (target_p_val >= 1 && target_p_val <= maxVal) {
                            // Count p's such that p <= q - 2
                            if (q - 2 >= 0) {
                                totalCount += prefixCounts[q - 1][(int)target_p_val];
                            }
                        }
                    }
                }
            }
        }
        return totalCount;
    }
}
```
### Algorithm
1. Precompute prefix counts: Create a 2D array `prefixCounts[i][v]` to store the number of occurrences of value `v` in `nums[0...i-1]`.
2. Initialize `totalCount` to 0.
3. Iterate through `q` from `2` to `n-3`.
4. Inside, iterate through `r` from `q+2` to `n-1`.
5. Inside, iterate through `s` from `r+2` to `n-1`.
6. For each triplet `(q, r, s)`, calculate the required value for `nums[p]`: `target_p_val = (long)nums[q] * nums[s] / nums[r]`.
7. Check if the division is exact and `target_p_val` is within the valid range `[1, 1000]`.
8. If it is, find the number of valid `p`'s using the precomputed `prefixCounts`. The number of `p`'s such that `p < q-1` and `nums[p] == target_p_val` is `prefixCounts[q-1][target_p_val]`.
9. Add this count to `totalCount`.
10. Return `totalCount`.

## Value-Based Counting with Precomputation
This approach further optimizes the counting process by fixing the middle two indices, `q` and `r`, and then using precomputed counts for both the left part (for index `p`) and the right part (for index `s`). Instead of iterating through indices `p` and `s`, we can iterate through their possible values, which allows us to count all valid `(p, s)` pairs for a fixed `(q, r)` more efficiently.
**Time:** O(N^2 * max_val + N * max_val) - Precomputation is `O(N * max_val)`. The main calculation has two nested loops for `q` and `r` (`O(N^2)`) and an inner loop for values (`O(max_val)`), leading to `O(N^2 * max_val)`. This is the most optimal approach among the ones that are straightforward to derive, but it may still be too slow if N and max_val are both large. · **Space:** O(N * max_val) - For the two count tables.
**Pros:** Most efficient among the presented polynomial time solutions.; Reduces the complexity by avoiding iteration over indices `p` and `s` inside the main loops.
**Cons:** The time complexity is still high and might not pass all test cases under strict time limits.; Requires significant memory for two count tables.
### Explanation
The main idea is to iterate through all valid pairs of the middle indices `(q, r)`. For each such pair, we need to find the number of pairs of outer indices `(p, s)` that satisfy the conditions. The number of valid `(p, s)` pairs for a fixed `(q, r)` can be calculated as:
`sum over all values v_p from 1 to 1000: (count of p's where p < q-1 and nums[p] = v_p) * (count of s's where s > r+1 and nums[s] = (v_p * nums[r]) / nums[q])`

To get these counts efficiently, we precompute both prefix and suffix frequency maps. `prefixCounts[i][v]` stores the frequency of `v` in `nums[0...i-1]`, and `suffixCounts[i][v]` stores the frequency of `v` in `nums[i...n-1]`. Both can be computed in `O(N * max_val)`.

Then, we loop through `q` and `r`. For each pair, we loop through all possible values `v_p` (from 1 to `max_val`). We get the count of `p`'s with this value from `prefixCounts`. We calculate the target `v_s`, and get the count of `s`'s with that value from `suffixCounts`. The product of these counts gives the number of special subsequences for that specific `v_p` and `(q, r)`. Summing these products up gives the total count.

```java
class Solution {
    public long countSpecialSubsequences(int[] nums) {
        int n = nums.length;
        long totalCount = 0;
        int maxVal = 1000;

        int[][] prefixCounts = new int[n + 1][maxVal + 1];
        for (int i = 0; i < n; i++) {
            for (int v = 1; v <= maxVal; v++) {
                prefixCounts[i + 1][v] = prefixCounts[i][v];
            }
            prefixCounts[i + 1][nums[i]]++;
        }

        int[][] suffixCounts = new int[n + 1][maxVal + 1];
        for (int i = n - 1; i >= 0; i--) {
            for (int v = 1; v <= maxVal; v++) {
                suffixCounts[i][v] = suffixCounts[i + 1][v];
            }
            suffixCounts[i][nums[i]]++;
        }

        for (int q = 2; q < n - 2; q++) {
            for (int r = q + 2; r < n; r++) {
                long current_qr_count = 0;
                for (int v_p = 1; v_p <= maxVal; v_p++) {
                    long count_p = (q - 2 >= 0) ? prefixCounts[q - 1][v_p] : 0;
                    if (count_p == 0) continue;

                    long product = (long) v_p * nums[r];
                    if (product % nums[q] == 0) {
                        long v_s = product / nums[q];
                        if (v_s >= 1 && v_s <= maxVal) {
                            long count_s = (r + 2 < n) ? suffixCounts[r + 2][(int)v_s] : 0;
                            current_qr_count += count_p * count_s;
                        }
                    }
                }
                totalCount += current_qr_count;
            }
        }

        return totalCount;
    }
}
```
### Algorithm
1. Precompute two count tables: `prefixCounts[i][v]` (count of `v` in `nums[0...i-1]`) and `suffixCounts[i][v]` (count of `v` in `nums[i...n-1]`).
2. Initialize `totalCount` to 0.
3. Iterate through the middle two indices, `q` and `r`:
   - `q` from `2` to `n-3`.
   - `r` from `q+2` to `n-1`.
4. For each pair `(q, r)`, we need to count pairs `(p, s)` that satisfy the conditions. Instead of iterating through `p` and `s`, we iterate through all possible values `v_p` that `nums[p]` can take (`1` to `1000`).
5. For each `v_p`:
   - Find the number of valid `p`'s, `count_p = prefixCounts[q-1][v_p]`.
   - If `count_p > 0`, calculate the required value for `nums[s]`: `v_s = (long)v_p * nums[r] / nums[q]`.
   - Check for divisibility and if `v_s` is in the valid range.
   - If valid, find the number of valid `s`'s, `count_s = suffixCounts[r+2][v_s]`.
   - Add the product `count_p * count_s` to a running sum for the current `(q, r)` pair.
6. Add the sum for `(q, r)` to `totalCount`.
7. Return `totalCount`.

# Solutions
### Java

```java
class Solution {
public
  long numberOfSubsequences(int[] nums) {
    int n = nums.length;
    Map<Integer, Integer> cnt = new HashMap<>();
    for (int r = 4; r < n - 2; ++r) {
      int c = nums[r];
      for (int s = r + 2; s < n; ++s) {
        int d = nums[s];
        int g = gcd(c, d);
        cnt.merge(((d / g) << 12) | (c / g), 1, Integer : : sum);
      }
    }
    long ans = 0;
    for (int q = 2; q < n - 4; ++q) {
      int b = nums[q];
      for (int p = 0; p < q - 1; ++p) {
        int a = nums[p];
        int g = gcd(a, b);
        ans += cnt.getOrDefault(((a / g) << 12) | (b / g), 0);
      }
      int c = nums[q + 2];
      for (int s = q + 4; s < n; ++s) {
        int d = nums[s];
        int g = gcd(c, d);
        cnt.merge(((d / g) << 12) | (c / g), -1, Integer : : sum);
      }
    }
    return ans;
  }
private
  int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); }
}

```

### CPP

```cpp
class Solution {
public:
  long long numberOfSubsequences(vector<int> &nums) {
    int n = nums.size();
    unordered_map<int, int> cnt;
    for (int r = 4; r < n - 2; ++r) {
      int c = nums[r];
      for (int s = r + 2; s < n; ++s) {
        int d = nums[s];
        int g = gcd(c, d);
        cnt[((d / g) << 12) | (c / g)]++;
      }
    }
    long long ans = 0;
    for (int q = 2; q < n - 4; ++q) {
      int b = nums[q];
      for (int p = 0; p < q - 1; ++p) {
        int a = nums[p];
        int g = gcd(a, b);
        ans += cnt[((a / g) << 12) | (b / g)];
      }
      int c = nums[q + 2];
      for (int s = q + 4; s < n; ++s) {
        int d = nums[s];
        int g = gcd(c, d);
        cnt[((d / g) << 12) | (c / g)]--;
      }
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def numberOfSubsequences(self, nums: List[int]) -> int: n = len(nums) cnt = defaultdict(int) for r in range(4, n - 2): c = nums[r] for s in range(r + 2, n): d = nums[s] g = gcd(c, d) cnt[(d // g, c // g)] += 1 ans = 0 for q in range(2, n - 4): b = nums[q] for p in range(q - 1): a = nums[p] g = gcd(a, b) ans += cnt[(a // g, b // g)] c = nums[q + 2] for s in range(q + 4, n): d = nums[s] g = gcd(c, d) cnt[(d // g, c // g)] -= 1 return ans

```