LeetCode Problem 3395

Difficulty: 🔴 Hard
Topics: Array, Hash Table, Math, Combinatorics

Solution

LeetCode 3395 - Subsequences with a Unique Middle Mode I

Problem Understanding

We are given an integer array nums, and we must count how many subsequences of length 5 satisfy a very specific condition:

• The subsequence must have exactly 5 elements.
• The middle element of the subsequence, meaning the third element seq[2], must be the unique mode of the subsequence.

A mode is the value that appears the most times in the sequence. A sequence has a unique mode only if exactly one value has the highest frequency.

Since we are working with subsequences, the relative order of elements must remain the same as in the original array, but the chosen indices do not need to be contiguous.

For every valid subsequence of length 5:

[a, b, c, d, e]

the value c must:

1. Appear more times than every other number.
2. Be the only value with that maximum frequency.

The answer can become very large, so we return it modulo:

10^9 + 7

The constraints are important:

• nums.length <= 1000
• Values can be very large or negative.
• A brute force enumeration of all subsequences would involve choosing 5 indices from up to 1000 elements.

The number of 5-element subsequences is:

$\binom{1000}{5}$

which is far too large to enumerate directly.

The key challenge is that the middle element of the subsequence is fixed by the ordering of chosen indices. If we choose indices:

i < j < k < l < m

then k is automatically the middle element.

Important edge cases include:

• Arrays where all elements are distinct, because no value can become a unique mode.
• Arrays where all elements are identical, because every subsequence is valid.
• Cases where another number ties the middle value's frequency.
• Cases where the middle value appears only once, because then it can never be a unique mode in a length-5 subsequence.

Approaches

Brute Force

The most direct solution is to generate every subsequence of size 5.

For every combination of indices:

i < j < k < l < m

we build the subsequence, count frequencies using a hash map, and check whether the middle element is the unique mode.

This approach is correct because it explicitly checks every possible subsequence and validates the definition exactly.

However, the time complexity is far too large.

The number of subsequences is:

$\binom{n}{5}$

For n = 1000, this is approximately 8 * 10^12, which is completely infeasible.

Optimal Observation

Instead of generating all subsequences, we fix the middle index first.

Suppose index k is the middle element.

Then we must choose:

• exactly 2 elements from the left side,
• exactly 2 elements from the right side.

Let:

x = nums[k]

For x to be the unique mode, we only need to reason about how many times x appears among the other four selected positions.

Since the subsequence length is only 5, the frequency possibilities are very limited.

The middle value already contributes one occurrence. We only need to count valid ways where:

• x appears 2, 3, 4, or 5 times total,
• no other value reaches the same frequency.

This transforms the problem from enumerating subsequences into counting combinations using frequency maps.

We maintain frequency counts on the left and right of the current middle index and count valid configurations combinatorially.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n^5)	O(1)	Enumerates every subsequence
Optimal	O(n^2)	O(n)	Counts valid configurations around each middle

Algorithm Walkthrough

Core Idea

Fix the middle index k.

Let:

x = nums[k]

We must choose:

• 2 indices from [0, k-1]
• 2 indices from [k+1, n-1]

We count how many of those choices make x the unique mode.

Frequency Cases

Because the subsequence length is 5, the frequency of x can only be:

• 5
• 4
• 3
• 2

It cannot be 1 because then some other number would also appear at least once, so there would not be a unique mode.

We count each case separately.

Step 1, Build Right Frequency Map

Initially, all elements except index 0 belong to the right side.

We store frequencies in a hash map:

rightCount[value]

We also maintain:

leftCount[value]

which starts empty.

Step 2, Iterate Over Every Possible Middle

For every middle index k from 2 to n-3:

• remove nums[k] from the right map,
• treat it as the middle value,
• count valid subsequences centered at k.

Step 3, Count Cases Where x Appears 5 Times

We need two additional x values on both sides.

If:

L = number of x on left
R = number of x on right

then the number of ways is:

$\binom{L}{2}\binom{R}{2}$

Step 4, Count Cases Where x Appears 4 Times

We need exactly three additional x values.

Possible splits:

• 2 left, 1 right
• 1 left, 2 right

The remaining chosen element must not create a tie.

The counts are computed combinatorially.

Step 5, Count Cases Where x Appears 3 Times

We need exactly two additional x values.

Possible splits:

• 2 left
• 1 left and 1 right
• 2 right

The remaining two selected elements must not both be equal to the same non-x value, otherwise that value would also appear twice and tie with x.

This is the trickiest part.

We count all possible remaining choices, then subtract invalid tie-producing choices.

Step 6, Count Cases Where x Appears 2 Times

We need exactly one additional x.

Now all three remaining elements must all be distinct from each other and distinct from x, otherwise another value could also appear twice.

We carefully count valid combinations using frequency maps.

Step 7, Move Middle Forward

After processing index k:

• add nums[k] into the left map,
• continue.

Why it works

For every subsequence of size 5, there is exactly one middle index. By fixing that middle index first, every valid subsequence is counted exactly once.

The algorithm exhaustively considers every possible frequency configuration for the middle value. Since these are the only possible ways a unique mode can exist in a length-5 sequence, every valid subsequence is included, and every invalid subsequence is excluded.

The frequency maps guarantee that all counts are computed correctly without enumerating individual subsequences.

Python Solution

from collections import Counter
from math import comb
from typing import List

MOD = 10**9 + 7

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

        left = Counter()
        right = Counter(nums)

        ans = 0

        def c2(x: int) -> int:
            if x < 2:
                return 0
            return x * (x - 1) // 2

        for mid in range(n):
            x = nums[mid]

            right[x] -= 1
            if right[x] == 0:
                del right[x]

            if mid >= 2 and mid <= n - 3:
                left_x = left[x]
                right_x = right[x]

                left_total = mid
                right_total = n - mid - 1

                left_non_x = left_total - left_x
                right_non_x = right_total - right_x

                total = 0

                # x frequency = 5
                total += c2(left_x) * c2(right_x)

                # x frequency = 4
                total += c2(left_x) * right_x * right_non_x
                total += left_x * left_non_x * c2(right_x)

                # x frequency = 3

                # 2 on left
                total += c2(left_x) * c2(right_non_x)

                # 2 on right
                total += c2(right_x) * c2(left_non_x)

                # 1 on each side
                total += (
                    left_x
                    * right_x
                    * left_non_x
                    * right_non_x
                )

                # remove ties for freq=3
                for v in set(left.keys()) | set(right.keys()):
                    if v == x:
                        continue

                    lv = left[v]
                    rv = right[v]

                    # tie when another value appears twice

                    # freq split: 1 left, 1 right
                    total -= left_x * right_x * lv * rv

                    # freq split: 2 left
                    total -= c2(left_x) * c2(rv)

                    # freq split: 2 right
                    total -= c2(right_x) * c2(lv)

                # x frequency = 2

                # one extra x on left
                for a in left:
                    if a == x:
                        continue

                    for b in right:
                        if b == x or b == a:
                            continue

                        remain = (
                            right_non_x
                            - right[b]
                        )

                        total += (
                            left_x
                            * left[a]
                            * right[b]
                            * remain
                        )

                # one extra x on right
                for a in right:
                    if a == x:
                        continue

                    for b in left:
                        if b == x or b == a:
                            continue

                        remain = (
                            left_non_x
                            - left[b]
                        )

                        total += (
                            right_x
                            * right[a]
                            * left[b]
                            * remain
                        )

                ans = (ans + total) % MOD

            left[x] += 1

        return ans % MOD

The implementation maintains two frequency maps:

• left, elements before the middle index
• right, elements after the middle index

For each middle position, the code counts all valid subsequences centered at that index.

The helper function c2(x) computes:

$\binom{x}{2}$

efficiently without using factorials.

The algorithm processes every possible frequency configuration of the middle value and uses combinatorial counting instead of explicit subsequence generation.

The subtraction logic is especially important for the frequency-3 case, because another value appearing twice would destroy uniqueness of the mode.

Go Solution

package main

func subsequencesWithMiddleMode(nums []int) int {
	const MOD int = 1_000_000_007

	n := len(nums)

	left := map[int]int{}
	right := map[int]int{}

	for _, v := range nums {
		right[v]++
	}

	c2 := func(x int) int64 {
		if x < 2 {
			return 0
		}
		return int64(x*(x-1)) / 2
	}

	var ans int64 = 0

	for mid := 0; mid < n; mid++ {
		x := nums[mid]

		right[x]--
		if right[x] == 0 {
			delete(right, x)
		}

		if mid >= 2 && mid <= n-3 {
			leftX := left[x]
			rightX := right[x]

			leftTotal := mid
			rightTotal := n - mid - 1

			leftNonX := leftTotal - leftX
			rightNonX := rightTotal - rightX

			var total int64 = 0

			// freq = 5
			total += c2(leftX) * c2(rightX)

			// freq = 4
			total += c2(leftX) * int64(rightX) * int64(rightNonX)
			total += int64(leftX) * int64(leftNonX) * c2(rightX)

			// freq = 3
			total += c2(leftX) * c2(rightNonX)
			total += c2(rightX) * c2(leftNonX)
			total += int64(leftX*rightX*leftNonX*rightNonX)

			// remove ties
			seen := map[int]bool{}

			for v := range left {
				seen[v] = true
			}

			for v := range right {
				seen[v] = true
			}

			for v := range seen {
				if v == x {
					continue
				}

				lv := left[v]
				rv := right[v]

				total -= int64(leftX*rightX*lv*rv)
				total -= c2(leftX) * c2(rv)
				total -= c2(rightX) * c2(lv)
			}

			// freq = 2

			for a, ca := range left {
				if a == x {
					continue
				}

				for b, cb := range right {
					if b == x || b == a {
						continue
					}

					remain := rightNonX - cb

					total += int64(leftX * ca * cb * remain)
				}
			}

			for a, ca := range right {
				if a == x {
					continue
				}

				for b, cb := range left {
					if b == x || b == a {
						continue
					}

					remain := leftNonX - cb

					total += int64(rightX * ca * cb * remain)
				}
			}

			ans = (ans + total) % MOD
		}

		left[x]++
	}

	return int((ans%MOD + MOD) % MOD)
}

The Go implementation mirrors the Python logic closely.

A few important Go-specific details:

• int64 is used for intermediate calculations to avoid overflow.
• Go maps return zero automatically for missing keys, which simplifies frequency handling.
• Since Go does not provide a built-in Counter, ordinary maps are used instead.
• Negative modulo values are normalized at the end.

Worked Examples

Example 1

nums = [1,1,1,1,1,1]

Every subsequence of length 5 is:

[1,1,1,1,1]

The number of ways to choose 5 indices from 6 is:

$\binom{6}{5}=6$

All are valid because 1 is clearly the unique mode.

Output:

6

Example 2

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

Consider middle index 2:

[1,2,2,3,4]

Frequencies:

Value	Count
1	1
2	2
3	1
4	1

2 is the unique mode.

Another valid subsequence:

[1,2,3,3,4]

with middle value 3.

However:

[1,2,2,3,3]

is invalid because both 2 and 3 appear twice.

Final answer:

4

Example 3

nums = [0,1,2,3,4,5,6,7,8]

All values are distinct.

Every subsequence of length 5 contains five distinct values, so every frequency is 1.

There is no unique mode.

Output:

0

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n²)	Each middle index processes frequency maps
Space	O(n)	Frequency hash maps store counts

The number of distinct values can be at most n, so iterating through the frequency maps for each middle index leads to quadratic complexity.

This is efficient enough for n <= 1000.

Test Cases

sol = Solution()

# Provided examples
assert sol.subsequencesWithMiddleMode([1,1,1,1,1,1]) == 6
assert sol.subsequencesWithMiddleMode([1,2,2,3,3,4]) == 4
assert sol.subsequencesWithMiddleMode([0,1,2,3,4,5,6,7,8]) == 0

# Minimum length
assert sol.subsequencesWithMiddleMode([1,1,1,1,1]) == 1  # single valid subsequence

# All distinct
assert sol.subsequencesWithMiddleMode([1,2,3,4,5]) == 0  # no mode exists

# Exactly one valid subsequence
assert sol.subsequencesWithMiddleMode([1,2,2,2,3]) == 1  # middle value unique mode

# Tie for mode
assert sol.subsequencesWithMiddleMode([1,1,2,2,3]) == 0  # two values appear twice

# Negative numbers
assert sol.subsequencesWithMiddleMode([-1,-1,-1,2,3,4]) == 3

# Large repeated block
assert sol.subsequencesWithMiddleMode([5] * 10) == 252

# Mixed frequencies
assert sol.subsequencesWithMiddleMode([1,2,1,2,1,3,3]) > 0

# Sparse duplicates
assert sol.subsequencesWithMiddleMode([1,2,3,1,4,5,1]) > 0

Test Summary

Test	Why
[1,1,1,1,1,1]	All subsequences valid
[1,2,2,3,3,4]	Standard mixed-frequency case
Distinct values	No unique mode possible
Length exactly 5	Smallest allowed input
Tie cases	Ensures uniqueness logic works
Negative values	Confirms hash map handling
Large duplicates	Stress combinatorial counting
Mixed distributions	Validates general correctness

Edge Cases

All Elements Distinct

If every value appears only once, then every subsequence of length 5 also contains five distinct values.

This means every frequency equals 1, so there is no unique mode.

A naive implementation might incorrectly accept the middle element simply because it appears in the sequence. The algorithm correctly rejects these cases because the middle value never exceeds the frequency of other values.

All Elements Equal

When all elements are identical, every subsequence of length 5 is valid.

This case heavily stresses combinatorial counting because the answer becomes:

$\binom{n}{5}$

The implementation handles this efficiently using combination formulas instead of enumerating subsequences.

Tied Frequencies

A very common source of bugs is forgetting that the mode must be unique.

For example:

[1,2,2,3,3]

contains two modes.

The algorithm explicitly subtracts configurations where another value reaches the same frequency as the middle value.

Middle Value Appears Only Once

If the middle value appears only once in the subsequence, then it cannot be the unique mode because every other chosen value appears at least once as well.

The implementation never counts such configurations because it only considers cases where the middle value frequency is at least 2.