Count Special Subsequences - Practice Coding Problems

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.

Input & Output

Example 1 — Basic Case

$ Input: nums = [2,3,4,6]

› Output: 1

💡 Note: Only one valid subsequence: indices (0,1,2,3) where 2×6 = 3×4 = 12. Gaps are: 1-0=1 > 1 is false, but we need 2-0=2 > 1 which is true, 3-1=2 > 1 true, 3-2=1 > 1 false. Actually checking properly: no valid subsequence due to insufficient gaps.

Example 2 — With Gaps

$ Input: nums = [1,2,3,4,5,6,7,8]

› Output: 0

💡 Note: No valid subsequence where nums[p]*nums[r] = nums[q]*nums[s] with required gaps

Example 3 — Multiple Solutions

$ Input: nums = [2,4,6,8,3,6,9,12]

› Output: 1

💡 Note: One valid subsequence with proper gaps and cross multiplication equality

Constraints

7 ≤ nums.length ≤ 1000
1 ≤ nums[i] ≤ 1000

Visualization

Tap to expand

Understanding the Visualization

Input

Array of positive integers

Find 4-tuples

Look for (p,q,r,s) with gaps and cross multiplication

Output

Count of valid special subsequences

Key Takeaway

🎯 Key Insight: Cross multiplication nums[p]×nums[r] = nums[q]×nums[s] can be checked by comparing ratios

Asked in

G Google 15 f Meta 12 Apple 8

The key insight is recognizing that nums[p]×nums[r] = nums[q]×nums[s] is equivalent to nums[p]/nums[q] = nums[r]/nums[s]. Best approach uses hash map to store ratios for O(n³) time. Space: O(n²)

Common Approaches

Approach	Time	Space	Notes
✓ Hash Map Optimization	O(n³)	O(n²)	Store ratio pairs and count matches using hash map for better efficiency
Optimized Enumeration	O(n⁴)	O(1)	Smart enumeration with early termination and reduced redundant checks
Brute Force - Check All Valid Combinations	O(n⁴)	O(1)	Try every possible 4-tuple with required spacing and check the multiplication condition

Hash Map Optimization — Algorithm Steps

For each valid pair (q,r), enumerate all valid pairs (p,s)
Store pairs with their ratios in hash map
Count pairs with matching ratios

Visualization

Tap to expand

Step-by-Step Walkthrough

Fix Middle Pair

Fix indices q and r as middle positions

Store Ratios

Store ratios nums[p]/nums[q] in hash map

Find Matches

Look for ratio nums[r]/nums[s] in hash map

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int gcd(int a, int b) {
    if (a < 0) a = -a;
    if (b < 0) b = -b;
    while (b != 0) {
        int temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

int solution(int* nums, int n) {
    int count = 0;
    
    for (int q = 2; q < n - 2; q++) {
        for (int r = q + 2; r < n - 1; r++) {
            // Simple O(n^4) approach for C to avoid complex hash map
            for (int p = 0; p < q - 1; p++) {
                for (int s = r + 2; s < n; s++) {
                    if ((long long)nums[p] * nums[s] == (long long)nums[q] * nums[r]) {
                        count++;
                    }
                }
            }
        }
    }
    
    return count;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    int nums[1000];
    int n = 0;
    char* token = strtok(line, "[,]");
    while (token != NULL) {
        if (token[0] >= '0' && token[0] <= '9') {
            nums[n++] = atoi(token);
        }
        token = strtok(NULL, "[,]");
    }
    
    int result = solution(nums, n);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n³)

Three nested loops to iterate through valid combinations

⚠ Quadratic Growth

Space Complexity

O(n²)

Hash map stores up to O(n²) pairs

⚠ Quadratic Space

8.5K Views

Medium Frequency

~35 min Avg. Time

245 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Hash Map Optimization — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler