LeetCode Problem 3404

Difficulty: 🟡 Medium
Topics: Array, Hash Table, Math, Enumeration

Solution

LeetCode 3404. Count Special Subsequences

Problem Understanding

We are given an array nums of positive integers and need to count how many subsequences of length four satisfy a specific multiplicative relationship.

A valid subsequence consists of indices (p, q, r, s) such that:

• p < q < r < s

• nums[p] * nums[r] == nums[q] * nums[s]

• There is at least one unused element between every consecutive pair of chosen indices:

• q - p > 1

• r - q > 1

• s - r > 1

The task is not to return the subsequences themselves, but to count how many distinct index quadruples satisfy all requirements.

The spacing constraints are important. They mean that once we choose q, the index p must be at most q - 2. Similarly, r must be at least q + 2, and s must be at least r + 2.

The array length is at most 1000, which is too large for an exhaustive search over all quadruples. A naive solution would examine every possible (p, q, r, s) combination, resulting in roughly 1000^4 = 10^12 possibilities, which is completely infeasible.

The values themselves are also bounded:

• 1 <= nums[i] <= 1000

This relatively small value range suggests that ratio-based normalization may be useful.

Several edge cases are worth noting:

• Arrays with the minimum length 7, where only one valid spacing pattern may exist.
• Arrays containing many identical values, which can create a large number of valid subsequences.
• Arrays where no multiplicative equality is possible.
• Situations where the multiplicative equality holds but the spacing constraints invalidate the quadruple.

The key challenge is counting valid quadruples efficiently while respecting the index-gap requirements.

Approaches

Brute Force

The most direct solution is to enumerate every valid quadruple (p, q, r, s).

For each quadruple:

1. Verify the spacing constraints.
2. Compute nums[p] * nums[r].
3. Compute nums[q] * nums[s].
4. Increment the answer if the products are equal.

This approach is clearly correct because it checks every possible candidate and counts exactly those satisfying the definition.

Unfortunately, there can be O(n^4) quadruples. With n = 1000, this is far beyond practical limits.

Key Insight

Starting from

nums[p] * nums[r] = nums[q] * nums[s]

we can rearrange it as

nums[p] / nums[q] = nums[s] / nums[r]

Instead of directly comparing products, we can compare reduced ratios.

Suppose we fix the middle pair (q, r).

Then:

• Left side depends on pairs (p, q)
• Right side depends on pairs (r, s)

If we represent every pair by its reduced fraction, then every matching fraction contributes valid subsequences.

For example:

nums[p] / nums[q] = 2 / 3

matches

nums[s] / nums[r] = 2 / 3

which is equivalent to the original multiplicative equality.

The spacing constraints naturally split the quadruple into:

• Left pair (p, q)
• Right pair (r, s)

We can count matching ratios between these two groups.

The optimal solution slides through possible r values while maintaining a frequency table of valid left-side ratios. Each right-side ratio query can then be answered in constant expected time using a hash map.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n⁴)	O(1)	Enumerates every quadruple
Optimal	O(n²)	O(n²)	Uses reduced ratios and hash map counting

Algorithm Walkthrough

Step 1

Observe that

$$nums[p] \times nums[r] = nums[q] \times nums[s]$$

is equivalent to

$$\frac{nums[p]}{nums[q]} = \frac{nums[s]}{nums[r]}$$

Therefore we only need to count matching ratios.

Step 2

Represent every ratio in reduced form.

For a pair (a, b):

1. Compute g = gcd(a, b).
2. Reduce to (a/g, b/g).

This guarantees that equivalent ratios always produce the same key.

For example:

2/4 -> (1,2)
3/6 -> (1,2)

Both map to the same hash key.

Step 3

Process indices in terms of the middle-right index r.

For a fixed r:

• Valid q indices satisfy q <= r - 2.
• Valid p indices satisfy p <= q - 2.
• Valid s indices satisfy s >= r + 2.

Step 4

Maintain a hash map storing all valid left-side ratios.

When moving from one r to the next, exactly one new q becomes eligible:

q = r - 2

For this newly eligible q, enumerate all valid p:

0 <= p <= q - 2

Insert the ratio

nums[p] / nums[q]

into the frequency map.

After this update, the map contains every valid (p,q) pair that can participate with the current or future r.

Step 5

Count matching right-side pairs.

For the current r, enumerate all valid s:

s >= r + 2

Compute

nums[s] / nums[r]

in reduced form.

If that ratio already exists in the frequency map, every stored occurrence corresponds to a valid (p,q) pair.

Add the frequency to the answer.

Step 6

Continue for all possible r.

The accumulated total is the number of valid special subsequences.

Why it works

The hash map always contains exactly the ratios generated by valid (p,q) pairs satisfying q < r and q - p > 1. For a fixed r, every valid s generates a ratio corresponding to (r,s). Whenever the reduced ratios match, we have

$$\frac{nums[p]}{nums[q]}=\frac{nums[s]}{nums[r]}$$

which is algebraically equivalent to

$$nums[p] \times nums[r] = nums[q] \times nums[s]$$

Thus every counted pair corresponds to a valid special subsequence, and every valid special subsequence is counted exactly once.

Python Solution

from typing import List
from collections import defaultdict
from math import gcd

class Solution:
    def numberOfSubsequences(self, nums: List[int]) -> int:
        n = len(nums)

        ratio_count = defaultdict(int)
        answer = 0

        for r in range(4, n - 2):
            q = r - 2

            for p in range(q - 1):
                g = gcd(nums[p], nums[q])
                key = (nums[p] // g, nums[q] // g)
                ratio_count[key] += 1

            for s in range(r + 2, n):
                g = gcd(nums[s], nums[r])
                key = (nums[s] // g, nums[r] // g)
                answer += ratio_count.get(key, 0)

        return answer

The implementation follows the algorithm directly.

The hash map ratio_count stores frequencies of reduced ratios corresponding to valid (p,q) pairs. As r increases, only one new q = r - 2 becomes eligible, so we incrementally add its contributions rather than rebuilding the entire structure.

For each valid (r,s) pair, we compute the reduced ratio nums[s] / nums[r]. The frequency stored in ratio_count tells us exactly how many valid left-side pairs produce the same ratio, so that value can be added directly to the answer.

Using reduced fractions via gcd guarantees that equivalent ratios are represented identically.

Go Solution

package main

import "math"

func gcd(a, b int) int {
	for b != 0 {
		a, b = b, a%b
	}
	return a
}

func numberOfSubsequences(nums []int) int64 {
	n := len(nums)

	ratioCount := make(map[[2]int]int64)
	var answer int64 = 0

	for r := 4; r <= n-3; r++ {
		q := r - 2

		for p := 0; p <= q-2; p++ {
			g := gcd(nums[p], nums[q])

			key := [2]int{
				nums[p] / g,
				nums[q] / g,
			}

			ratioCount[key]++
		}

		for s := r + 2; s < n; s++ {
			g := gcd(nums[s], nums[r])

			key := [2]int{
				nums[s] / g,
				nums[r] / g,
			}

			answer += ratioCount[key]
		}
	}

	return answer
}

func abs(x int) int {
	return int(math.Abs(float64(x)))
}

The Go implementation mirrors the Python version closely. A fixed-size array [2]int is used as the hash-map key because arrays are comparable and therefore can be used directly as map keys. The answer is stored in int64 because the number of valid subsequences can exceed the range of a 32-bit integer.

Worked Examples

Example 1

nums = [1,2,3,4,3,6,1]

Only:

r = 4
q = 2

becomes eligible.

Build left ratios

p	Ratio	Reduced
0	1/3	(1,3)

Hash map:

Ratio	Count
(1,3)	1

Query right ratios

Valid:

s = 6

Ratio:

1/3 -> (1,3)

Lookup:

Ratio	Count
(1,3)	1

Answer becomes:

1

Final answer:

1

Example 2

nums = [3,4,3,4,3,4,3,4]

r = 4

Eligible:

q = 2

Add:

p	Ratio
0	3/3 = (1,1)

Map:

Ratio	Count
(1,1)	1

Query:

s	Ratio
6	3/3 = (1,1)
7	4/3 = (4,3)

Contribution:

1 + 0 = 1

r = 5

Eligible:

q = 3

Add:

p	Ratio
0	3/4
1	4/4=(1,1)

Map now:

Ratio	Count
(1,1)	2
(3,4)	1

Query:

s = 7

Ratio:

4/4=(1,1)

Contribution:

+2

Total:

3

Final answer:

3

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n²)	Each valid pair is processed once
Space	O(n²)	Hash map may store O(n²) distinct pair ratios

For every newly activated q, we enumerate all valid p values exactly once across the entire algorithm. Similarly, every valid (r,s) pair is queried exactly once. Therefore the total amount of work is proportional to the number of pairs, which is O(n²). The ratio-frequency map may contain up to O(n²) different reduced ratios in the worst case.

Test Cases

from typing import List

s = Solution()

assert s.numberOfSubsequences([1,2,3,4,3,6,1]) == 1  # example 1

assert s.numberOfSubsequences([3,4,3,4,3,4,3,4]) == 3  # example 2

assert s.numberOfSubsequences([1,2,3,4,5,6,7]) == 0  # minimum size, no match

assert s.numberOfSubsequences([1,1,1,1,1,1,1]) == 1  # only possible quadruple

assert s.numberOfSubsequences([2,2,2,2,2,2,2,2]) == 5  # many matching ratios

assert s.numberOfSubsequences([1,2,1,2,1,2,1,2]) == 3  # repeated pattern

assert s.numberOfSubsequences([1000,1,1000,1,1000,1,1000]) == 1  # large values

assert s.numberOfSubsequences([5,7,5,7,5,7,5,7,5]) >= 0  # stress repeated values

assert s.numberOfSubsequences([1,3,2,6,4,12,8]) == 0  # multiplicative relation absent

assert s.numberOfSubsequences([1,5,1,5,1,5,1,5,1]) > 0  # multiple valid matches

Test Summary

Test	Why
[1,2,3,4,3,6,1]	Official example 1
[3,4,3,4,3,4,3,4]	Official example 2
[1,2,3,4,5,6,7]	No valid subsequence
[1,1,1,1,1,1,1]	Minimum-length all-equal array
[2,2,2,2,2,2,2,2]	Large number of matching ratios
[1,2,1,2,1,2,1,2]	Repeated alternating pattern
[1000,1,1000,1,1000,1,1000]	Maximum value boundary
[5,7,5,7,5,7,5,7,5]	Many repeated ratio matches
[1,3,2,6,4,12,8]	No multiplicative equality
[1,5,1,5,1,5,1,5,1]	Multiple valid subsequences

Edge Cases

One important edge case is the minimum allowed array length of seven. Because the spacing constraints require at least one unused element between every consecutive selected index, length seven is the smallest array that can possibly contain a valid subsequence. In this situation there is very little flexibility in the indices. The implementation handles this naturally because the loops begin at the first valid r and only process legal index ranges.

Another important edge case occurs when many values are identical. For example, an array consisting entirely of ones causes every valid ratio to reduce to (1,1). A naive implementation might accidentally double count or generate excessive duplicate work. The hash-map approach handles this efficiently by storing only frequencies and adding counts directly during lookups.

A third edge case involves ratios that are mathematically equal but represented by different numbers. For example, 2/4 and 3/6 should be considered identical because they represent the same fraction. If ratios were stored without normalization, valid subsequences would be missed. Reducing every ratio using gcd guarantees that all equivalent fractions map to the same key.

A final edge case involves large products. Directly comparing nums[p] * nums[r] and nums[q] * nums[s] is safe under these constraints, but ratio normalization avoids relying on multiplication entirely. This keeps the logic clean and makes the equality comparison independent of product magnitude.