Count Special Subsequences
MedPrompt
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
Approaches
3 approaches with complexity analysis and trade-offs.
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.
Algorithm
- Initialize a counter
countto 0. - Use four nested loops to iterate through all possible combinations of indices
(p, q, r, s). - To satisfy the gap conditions
q-p > 1,r-q > 1,s-r > 1directly, the loops can be set up as follows:pfrom0ton-7qfromp+2ton-5rfromq+2ton-3sfromr+2ton-1
- Inside the innermost loop, check if the product condition
nums[p] * nums[r] == nums[q] * nums[s]is met. - If the condition is true, increment the
count. - After the loops complete, return
count.
Walkthrough
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.
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; }}Complexity
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.
Trade-offs
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).
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.
Algorithm
- Precompute prefix counts: Create a 2D array
prefixCounts[i][v]to store the number of occurrences of valuevinnums[0...i-1]. - Initialize
totalCountto 0. - Iterate through
qfrom2ton-3. - Inside, iterate through
rfromq+2ton-1. - Inside, iterate through
sfromr+2ton-1. - For each triplet
(q, r, s), calculate the required value fornums[p]:target_p_val = (long)nums[q] * nums[s] / nums[r]. - Check if the division is exact and
target_p_valis within the valid range[1, 1000]. - If it is, find the number of valid
p's using the precomputedprefixCounts. The number ofp's such thatp < q-1andnums[p] == target_p_valisprefixCounts[q-1][target_p_val]. - Add this count to
totalCount. - Return
totalCount.
Walkthrough
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.
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; }}Complexity
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`.
Trade-offs
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.
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.
Algorithm
- Precompute two count tables:
prefixCounts[i][v](count ofvinnums[0...i-1]) andsuffixCounts[i][v](count ofvinnums[i...n-1]). - Initialize
totalCountto 0. - Iterate through the middle two indices,
qandr:qfrom2ton-3.rfromq+2ton-1.
- For each pair
(q, r), we need to count pairs(p, s)that satisfy the conditions. Instead of iterating throughpands, we iterate through all possible valuesv_pthatnums[p]can take (1to1000). - 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 fornums[s]:v_s = (long)v_p * nums[r] / nums[q]. - Check for divisibility and if
v_sis 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_sto a running sum for the current(q, r)pair.
- Find the number of valid
- Add the sum for
(q, r)tototalCount. - Return
totalCount.
Walkthrough
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.
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; }}Complexity
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.
Trade-offs
Pros
Most efficient among the presented polynomial time solutions.
Reduces the complexity by avoiding iteration over indices
pandsinside 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.
Solutions
Solution
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); }}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; }};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 ansVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.