Skip to main content
Talentd

Count Special Subsequences - Solution & Explanation

MediumArrayHash TableMathEnumeration8 min readAsked at: Google
Practice this problem

Problem Statement

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.

 

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 = 3
    • nums[q] * nums[s] = nums[2] * nums[6] = 3 * 1 = 3

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 = 9
    • nums[q] * nums[s] = nums[2] * nums[6] = 3 * 3 = 9
  • (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 = 16
    • nums[q] * nums[s] = nums[3] * nums[7] = 4 * 4 = 16
  • (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 = 12
    • nums[q] * nums[s] = nums[2] * nums[7] = 3 * 4 = 12

 

Constraints:

  • 7 <= nums.length <= 1000
  • 1 <= 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

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force Quadruple EnumerationO(n^4)O(1)Understanding the definition or verifying correctness on very small arrays
Hash Map with Ratio NormalizationO(n^2)O(n^2)General solution for interviews and competitive programming

Video Solution

3404. Count Special Subsequences | HashMap | GCD | Pattern Identification • Aryan Mittal • 4,277 views views

Watch 3 more video solutions →

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.

Ready to solve this problem?

Practice Count Special Subsequences with our built-in code editor and test cases.

Practice on FleetCode
Previous

Max Points on a Line