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).
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); }}Video 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.