Count Special Subsequences - Solution & Explanation

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.