Count Special Subsequences

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.

Examples

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

Solution

Method 1 – Hash Map Pair Product Counting

Intuition

We want to count quadruples (p, q, r, s) with p < q < r < s, q - p > 1, r - q > 1, s - r > 1, and nums[p] * nums[r] == nums[q] * nums[s]. For each possible (q, r) pair, we can count the number of valid p < q-1 and s > r+1 such that nums[p] * nums[r] == nums[q] * nums[s] by precomputing products to the left and right using hash maps.

Approach

For each possible (q, r) with r - q > 1:
1. For all p < q-1, count the frequency of nums[p] * nums[r] and store in a hash map left.
2. For all s > r+1, count the frequency of nums[q] * nums[s] and store in a hash map right.
3. For each product in left, if it exists in right, add left[prod] * right[prod] to the answer.
Return the total answer.

Code

C++

class Solution {
public:
    int countSpecialQuadruplets(vector<int>& nums) {
        int n = nums.size(), ans = 0;
        for (int q = 1; q < n-4+2; ++q) {
            for (int r = q+2; r < n-1; ++r) {
                unordered_map<int, int> left, right;
                for (int p = 0; p < q-1; ++p) left[nums[p]*nums[r]]++;
                for (int s = r+2; s < n; ++s) right[nums[q]*nums[s]]++;
                for (auto& [prod, cnt] : left) {
                    if (right.count(prod)) ans += cnt * right[prod];
                }
            }
        }
        return ans;
    }
};

Java

class Solution {
    public int countSpecialQuadruplets(int[] nums) {
        int n = nums.length, ans = 0;
        for (int q = 1; q < n-4+2; q++) {
            for (int r = q+2; r < n-1; r++) {
                Map<Integer, Integer> left = new HashMap<>();
                Map<Integer, Integer> right = new HashMap<>();
                for (int p = 0; p < q-1; p++) left.put(nums[p]*nums[r], left.getOrDefault(nums[p]*nums[r], 0)+1);
                for (int s = r+2; s < n; s++) right.put(nums[q]*nums[s], right.getOrDefault(nums[q]*nums[s], 0)+1);
                for (int prod : left.keySet()) {
                    if (right.containsKey(prod)) ans += left.get(prod) * right.get(prod);
                }
            }
        }
        return ans;
    }
}

Python

class Solution:
    def countSpecialQuadruplets(self, nums: list[int]) -> int:
        n, ans = len(nums), 0
        for q in range(1, n-2):
            for r in range(q+2, n-1):
                left = {}
                right = {}
                for p in range(0, q-1):
                    prod = nums[p] * nums[r]
                    left[prod] = left.get(prod, 0) + 1
                for s in range(r+2, n):
                    prod = nums[q] * nums[s]
                    right[prod] = right.get(prod, 0) + 1
                for prod in left:
                    if prod in right:
                        ans += left[prod] * right[prod]
        return ans

Rust

impl Solution {
    pub fn count_special_quadruplets(nums: Vec<i32>) -> i32 {
        let n = nums.len();
        let mut ans = 0;
        for q in 1..n-2 {
            for r in q+2..n-1 {
                let mut left = std::collections::HashMap::new();
                let mut right = std::collections::HashMap::new();
                for p in 0..q-1 {
                    *left.entry(nums[p]*nums[r]).or_insert(0) += 1;
                }
                for s in r+2..n {
                    *right.entry(nums[q]*nums[s]).or_insert(0) += 1;
                }
                for (prod, &cnt) in &left {
                    if let Some(&rcnt) = right.get(prod) {
                        ans += cnt * rcnt;
                    }
                }
            }
        }
        ans
    }
}

TypeScript

class Solution {
    countSpecialQuadruplets(nums: number[]): number {
        const n = nums.length;
        let ans = 0;
        for (let q = 1; q < n-2; q++) {
            for (let r = q+2; r < n-1; r++) {
                const left: Record<number, number> = {}, right: Record<number, number> = {};
                for (let p = 0; p < q-1; p++) left[nums[p]*nums[r]] = (left[nums[p]*nums[r]]||0)+1;
                for (let s = r+2; s < n; s++) right[nums[q]*nums[s]] = (right[nums[q]*nums[s]]||0)+1;
                for (const prod in left) {
                    if (prod in right) ans += left[prod] * right[prod];
                }
            }
        }
        return ans;
    }
}

Complexity

⏰ Time complexity: O(n^3), since for each (q, r) pair, we scan up to n for p and s.
🧺 Space complexity: O(n), for the hash maps per (q, r) pair.