Count Special Subsequences solution and explanation
Google
3 more videos on this problem
3404. Count Special Subsequences | HashMap | GCD | Pattern IdentificationAryan Mittal · 22:03 · 4K views
Leetcode 3404 | Count Special Subsequences | Weekly Contest 430Road To FAANG · 13:57 · 671 views
3404. Count Special Subsequences (Leetcode Medium)Programming Live with Larry · 21:24 · 479 views
Weekly Contest 430 | 3402, 3403, 3404 and 3405 | LeetcodeAmit Choraria · 46:57 · 278 views
The 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 > 1ands - 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 = 3nums[q] * nums[s] = nums[2] * nums[6] = 3 * 1 = 3
- This corresponds to elements
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 = 9nums[q] * nums[s] = nums[2] * nums[6] = 3 * 3 = 9
- This corresponds to elements
(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 = 16nums[q] * nums[s] = nums[3] * nums[7] = 4 * 4 = 16
- This corresponds to elements
(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 = 12nums[q] * nums[s] = nums[2] * nums[7] = 3 * 4 = 12
- This corresponds to elements
Constraints:
7 <= nums.length <= 10001 <= nums[i] <= 1000
Approach overview
Problem Overview: Given an array, count subsequences of four indices (i, j, k, l) with i < j < k < l where the multiplicative relation nums[i] * nums[k] == nums[j] * nums[l] holds. The challenge is avoiding the obvious O(n^4) enumeration of all quadruples.
Approach 1: Brute Force Enumeration (O(n^4) time, O(1) space)
Enumerate every ordered quadruple of indices. Use four nested loops ensuring i < j < k < l. For each combination compute nums[i] * nums[k] and nums[j] * nums[l] and increment the count if they match. This approach directly follows the problem definition and helps validate logic on small inputs. However, the time complexity grows to O(n^4), which becomes infeasible even for moderate array sizes.
Approach 2: Ratio Hashing with Pair Enumeration (O(n^2) time, O(n^2) space)
The equation nums[i] * nums[k] == nums[j] * nums[l] can be rearranged into a ratio equality: nums[i] / nums[j] == nums[l] / nums[k]. Instead of checking quadruples directly, treat the left side and right side as independent pairs. For each pair (i, j), compute the reduced fraction nums[i] / nums[j] using gcd normalization so equivalent ratios map to the same key. Store counts of these ratios in a hash table.
Next, enumerate pairs (k, l) with k < l and compute nums[l] / nums[k] using the same normalization. A hash lookup reveals how many earlier (i, j) pairs produce the same ratio. Each match forms a valid quadruple satisfying the multiplicative condition. The heavy lifting becomes constant-time hash lookups instead of repeated product comparisons.
This technique relies on careful ordering so index constraints remain valid. By processing pairs in stages (left pairs before right pairs), the algorithm respects i < j < k < l automatically. The approach combines array traversal, hash table aggregation, and basic math simplification using GCD.
Recommended for interviews: Start by describing the O(n^4) brute force to show you understand the subsequence constraints. Then derive the ratio transformation that converts the multiplicative relation into matching pair signatures. Interviewers typically expect the hash‑based pair enumeration because it reduces the complexity to roughly O(n^2) while demonstrating strong pattern recognition with algebraic manipulation and hash maps.
Solution
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 ansclass 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);
}
}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;
}
};function numberOfSubsequences(nums: number[]): number {
const n = nums.length;
const cnt = new Map<number, number>();
function gcd(a: number, b: number): number {
while (b !== 0) {
[a, b] = [b, a % b];
}
return a;
}
for (let r = 4; r < n - 2; r++) {
const c = nums[r];
for (let s = r + 2; s < n; s++) {
const d = nums[s];
const g = gcd(c, d);
const key = ((d / g) << 12) | (c / g);
cnt.set(key, (cnt.get(key) || 0) + 1);
}
}
let ans = 0;
for (let q = 2; q < n - 4; q++) {
const b = nums[q];
for (let p = 0; p < q - 1; p++) {
const a = nums[p];
const g = gcd(a, b);
const key = ((a / g) << 12) | (b / g);
ans += cnt.get(key) || 0;
}
const c = nums[q + 2];
for (let s = q + 4; s < n; s++) {
const d = nums[s];
const g = gcd(c, d);
const key = ((d / g) << 12) | (c / g);
cnt.set(key, (cnt.get(key) || 0) - 1);
}
}
return ans;
}func numberOfSubsequences(nums []int) (ans int64) {
n := len(nums)
cnt := make(map[int]int)
gcd := func(a, b int) int {
for b != 0 {
a, b = b, a%b
}
return a
}
for r := 4; r < n-2; r++ {
c := nums[r]
for s := r + 2; s < n; s++ {
d := nums[s]
g := gcd(c, d)
key := ((d / g) << 12) | (c / g)
cnt[key]++
}
}
for q := 2; q < n-4; q++ {
b := nums[q]
for p := 0; p < q-1; p++ {
a := nums[p]
g := gcd(a, b)
key := ((a / g) << 12) | (b / g)
ans += int64(cnt[key])
}
c := nums[q+2]
for s := q + 4; s < n; s++ {
d := nums[s]
g := gcd(c, d)
key := ((d / g) << 12) | (c / g)
cnt[key]--
}
}
return
}Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Quadruple Enumeration | O(n^4) | O(1) | Understanding the definition or verifying correctness on very small arrays |
| Hash Map with Ratio Normalization | O(n^2) | O(n^2) | General solution for interviews and competitive programming |
Frequently asked questions
Is Count Special Subsequences easy or hard?
Count Special Subsequences is rated Medium but often feels closer to Medium‑Hard. The challenge comes from recognizing the algebraic transformation that converts a quadruple condition into matching pair ratios and then implementing it efficiently with hash maps.
Count Special Subsequences Python/Java solution
Implement the optimized solution by iterating through pairs, computing normalized fractions using gcd, and storing counts in a hash map. Python uses dictionaries and math.gcd, while Java typically uses HashMap with a string or pair key representing the reduced fraction.
How to solve Count Special Subsequences in O(n^2)?
Enumerate pairs (i, j) and store the reduced ratio nums[i] / nums[j] in a hash map using GCD normalization. Then enumerate later pairs (k, l) and compute nums[l] / nums[k]. Each hash match represents valid indices satisfying nums[i] * nums[k] = nums[j] * nums[l], allowing the algorithm to count subsequences in quadratic time.
What is the best approach for Count Special Subsequences?
The most efficient approach uses a hash map with ratio normalization. Transform the condition nums[i] * nums[k] = nums[j] * nums[l] into nums[i] / nums[j] = nums[l] / nums[k]. Store normalized fractions from earlier pairs in a hash table and match them with later pairs. This reduces the complexity from O(n^4) to about O(n^2).
Is Count Special Subsequences asked at Google/Amazon/Meta?
Problems combining pair enumeration, ratio normalization, and hash maps frequently appear in interviews at large tech companies. Variants of multiplicative equality or ratio matching are commonly discussed in Google and Meta interview preparation sets.
What data structure is used in Count Special Subsequences?
A hash table (dictionary) is the key data structure. It stores normalized ratios representing pair relationships. GCD is used to reduce fractions so mathematically equivalent ratios map to the same hash key.
What is the time complexity of Count Special Subsequences?
The brute force approach runs in O(n^4) because it checks every quadruple of indices. The optimized hash‑based solution reduces the work to pair enumeration and hash lookups, giving roughly O(n^2) time with O(n^2) auxiliary storage.