# Subsequences with a Unique Middle Mode I
**Difficulty:** HARD
[External](https://leetcode.com/problems/subsequences-with-a-unique-middle-mode-i)
Canonical: https://scaleengineer.com/dsa/problems/subsequences-with-a-unique-middle-mode-i
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Combinatorics](https://scaleengineer.com/dsa/patterns/combinatorics)
**Data structures:** Array, Hash Table
---
## Problem
Given an integer array `nums`, find the number of subsequences of size 5 of `nums` with a **unique middle mode**.

Since the answer may be very large, return it **modulo** `109 + 7`.

A **mode** of a sequence of numbers is defined as the element that appears the **maximum** number of times in the sequence.

A sequence of numbers contains a **unique mode** if it has only one mode.

A sequence of numbers `seq` of size 5 contains a **unique middle mode** if the _middle element_ (`seq[2]`) is a **unique mode**.

**Example 1:**

**Input:** nums = \[1,1,1,1,1,1\]

**Output:** 6

**Explanation:**

`[1, 1, 1, 1, 1]` is the only subsequence of size 5 that can be formed, and it has a unique middle mode of 1\. This subsequence can be formed in 6 different ways, so the output is 6\. 

**Example 2:**

**Input:** nums = \[1,2,2,3,3,4\]

**Output:** 4

**Explanation:**

`[1, 2, 2, 3, 4]` and `[1, 2, 3, 3, 4]` each have a unique middle mode because the number at index 2 has the greatest frequency in the subsequence. `[1, 2, 2, 3, 3]` does not have a unique middle mode because 2 and 3 appear twice.

**Example 3:**

**Input:** nums = \[0,1,2,3,4,5,6,7,8\]

**Output:** 0

**Explanation:**

There is no subsequence of length 5 with a unique middle mode.

**Constraints:**

* `5 <= nums.length <= 1000`
* `-109 <= nums[i] <= 109`

# Approaches
## Brute Force Enumeration
The most straightforward approach is to generate all possible subsequences of size 5, and for each one, check if it satisfies the unique middle mode condition. This involves iterating through all combinations of five indices.
**Time:** O(N^5), where N is the length of `nums`. This is due to the five nested loops required to generate all `C(N, 5)` subsequences. · **Space:** O(1), as the space used for the frequency map is constant (at most 5 entries).
**Pros:** Simple to understand and implement.
**Cons:** Extremely inefficient and will time out for the given constraints (`N <= 1000`).
### Explanation
This approach directly follows the problem definition by generating every single subsequence of length 5. We can achieve this by using five nested loops, where each loop variable represents an index in the subsequence, ensuring that the indices are strictly increasing: `i1 < i2 < i3 < i4 < i5`.

For each generated subsequence, we perform a check. The middle element is `nums[i3]`. We need to verify if it's the unique mode. This check involves counting the frequencies of all elements within the 5-element subsequence. A simple way to do this is to use a hash map. After populating the frequency map, we find the frequency of the middle element and compare it with the frequencies of all other elements. If the middle element's frequency is strictly the highest, we've found a valid subsequence and increment our total count. Since the answer can be large, all additions to the count should be done modulo `10^9 + 7`.

```java
class Solution {
    public int countSubsequences(int[] nums) {
        int n = nums.length;
        long count = 0;
        int MOD = 1_000_000_007;

        for (int i1 = 0; i1 < n; i1++) {
            for (int i2 = i1 + 1; i2 < n; i2++) {
                for (int i3 = i2 + 1; i3 < n; i3++) {
                    for (int i4 = i3 + 1; i4 < n; i4++) {
                        for (int i5 = i4 + 1; i5 < n; i5++) {
                            int[] sub = {nums[i1], nums[i2], nums[i3], nums[i4], nums[i5]};
                            if (isUniqueMiddleMode(sub)) {
                                count++;
                            }
                        }
                    }
                }
            }
        }

        return (int) (count % MOD);
    }

    private boolean isUniqueMiddleMode(int[] sub) {
        java.util.Map<Integer, Integer> freq = new java.util.HashMap<>();
        for (int num : sub) {
            freq.put(num, freq.getOrDefault(num, 0) + 1);
        }

        int middleElement = sub[2];
        int middleFreq = freq.get(middleElement);

        if (middleFreq == 0) return false; // Should not happen

        for (java.util.Map.Entry<Integer, Integer> entry : freq.entrySet()) {
            if (entry.getKey() != middleElement) {
                if (entry.getValue() >= middleFreq) {
                    return false;
                }
            }
        }
        return true;
    }
}
```
### Algorithm
*   Initialize `count = 0`.
*   Use five nested loops to iterate through all possible combinations of 5 indices `i1 < i2 < i3 < i4 < i5`.
*   For each combination of indices, form the subsequence `sub = [nums[i1], nums[i2], nums[i3], nums[i4], nums[i5]]`.
*   Check if this subsequence has a unique middle mode:
    *   Let `middle_element = sub[2]`.
    *   Use a frequency map to count occurrences of each number in `sub`.
    *   Find the frequency of `middle_element`, say `freq_middle`.
    *   Find the maximum frequency among all other elements in `sub`, say `max_other_freq`.
    *   If `freq_middle` is strictly greater than `max_other_freq`, the condition is met.
*   If the condition is met, increment `count`.
*   After checking all combinations, return `count` modulo `10^9 + 7`.

## Combinatorial Counting with Dynamic Frequency Maps
A more efficient approach is to iterate through each possible middle element `nums[i]` and, for each, count the number of ways to choose two elements from its left and two from its right to form a valid subsequence. This counting is done by categorizing subsequences based on the frequency of `nums[i]` and using combinatorial formulas. To make this efficient, we maintain and update frequency maps of elements to the left and right of `i` as we iterate.
**Time:** O(N * m), where N is the array length and `m` is the number of unique elements. For each of the N elements, we iterate through up to `m` unique values for calculations. In the worst case, `m` can be up to `N`, leading to O(N^2). Coordinate compression takes O(N log N). · **Space:** O(N + m), where N is for the combinations table and `m` is the number of unique elements for frequency maps. `m <= N`.
**Pros:** Efficient enough to pass within the time limits.; Systematically breaks down a complex counting problem into manageable parts.
**Cons:** The logic, especially for the `freq_x = 2` case, is complex and error-prone to implement.; Requires careful handling of combinations and modulo arithmetic.
### Explanation
The key idea is to fix the middle element of the subsequence and count the valid ways to complete it. We iterate through each index `i` from `2` to `n-3` and treat `nums[i]` as the middle element, let's call it `x`.

For `x` to be the unique middle mode, its frequency in the 5-element subsequence must be strictly greater than any other element's frequency. This leads to two main cases for the frequency of `x`, `freq_x`:
1.  `freq_x >= 3`: In a 5-element sequence, if one element appears 3 or more times, no other element can have an equal or higher frequency. Thus, these subsequences are always valid. We can count them using combinations. For example, to get `freq_x = 3`, we can choose one `x` and one non-`x` from the left part, and one `x` and one non-`x` from the right part. We sum up the ways for `freq_x = 3, 4, 5`.
2.  `freq_x = 2`: For `x` to be the unique mode, the other three elements must be distinct from `x` and also from each other.

To implement this efficiently, we iterate `i` from `0` to `n-1`. We maintain two frequency maps: `left_counts` for elements in `nums[0...i-1]` and `right_counts` for `nums[i+1...n-1]`. As `i` increments, we can update these maps efficiently. For each `i` that can be a middle element, we use these maps to perform the combinatorial counting for the two cases above.

The calculation for `freq_x=2` is the most involved. It requires counting ways to pick three distinct non-`x` elements distributed between the left and right parts. This can be done by iterating through the unique values in the frequency maps and calculating the number of valid combinations, which takes `O(m)` time where `m` is the number of unique elements.

Since the values in `nums` can be large, we first apply coordinate compression to map them to a smaller range.

```java
class Solution {
    long[][] C;
    int MOD = 1_000_000_007;

    public int countSubsequences(int[] nums) {
        int n = nums.length;
        if (n < 5) return 0;

        // Coordinate Compression
        java.util.Set<Integer> set = new java.util.HashSet<>();
        for (int num : nums) set.add(num);
        java.util.List<Integer> sortedUnique = new java.util.ArrayList<>(set);
        java.util.Collections.sort(sortedUnique);
        java.util.Map<Integer, Integer> valToRank = new java.util.HashMap<>();
        for (int i = 0; i < sortedUnique.size(); i++) {
            valToRank.put(sortedUnique.get(i), i);
        }
        int[] compressedNums = new int[n];
        for (int i = 0; i < n; i++) {
            compressedNums[i] = valToRank.get(nums[i]);
        }
        int m = sortedUnique.size();

        // Precompute combinations
        C = new long[n + 1][6];
        for (int i = 0; i <= n; i++) {
            C[i][0] = 1;
            for (int j = 1; j <= Math.min(i, 5); j++) {
                C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % MOD;
            }
        }

        long totalCount = 0;
        int[] rightCounts = new int[m];
        for (int num : compressedNums) rightCounts[num]++;

        int[] leftCounts = new int[m];

        for (int i = 0; i < n; i++) {
            int x = compressedNums[i];
            rightCounts[x]--;

            if (i >= 2 && i <= n - 3) {
                long leftTotal = i;
                long rightTotal = n - 1 - i;
                long leftEqual = leftCounts[x];
                long rightEqual = rightCounts[x];
                long leftOther = leftTotal - leftEqual;
                long rightOther = rightTotal - rightEqual;

                // Case 1: freq_x >= 3
                // freq_x = 3: (1+2+0, 1+1+1, 1+0+2)
                long count3 = (C(leftEqual, 2) * C(rightOther, 2)) % MOD;
                count3 = (count3 + (leftEqual * leftOther % MOD) * (rightEqual * rightOther % MOD)) % MOD;
                count3 = (count3 + C(leftOther, 2) * C(rightEqual, 2)) % MOD;
                // freq_x = 4: (1+3+0, 1+2+1, 1+1+2, 1+0+3)
                long count4 = (C(leftEqual, 2) * rightEqual % MOD * rightOther % MOD) % MOD;
                count4 = (count4 + leftEqual * leftOther % MOD * C(rightEqual, 2) % MOD) % MOD;
                // freq_x = 5
                long count5 = (C(leftEqual, 2) * C(rightEqual, 2)) % MOD;

                totalCount = (totalCount + count3 + count4 + count5) % MOD;

                // Case 2: freq_x = 2
                long leftSumSq = 0, rightSumSq = 0;
                for(int j=0; j<m; ++j) {
                    if (j == x) continue;
                    leftSumSq = (leftSumSq + C(leftCounts[j], 2)) % MOD;
                    rightSumSq = (rightSumSq + C(rightCounts[j], 2)) % MOD;
                }
                long leftDistinctPairs = (C(leftOther, 2) - leftSumSq + MOD) % MOD;
                long rightDistinctPairs = (C(rightOther, 2) - rightSumSq + MOD) % MOD;

                long term1 = 0;
                for(int j=0; j<m; ++j) {
                    if (j == x || leftCounts[j] == 0) continue;
                    long rightOther_no_j = rightOther - rightCounts[j];
                    long rightSumSq_no_j = (rightSumSq - C(rightCounts[j], 2) + MOD) % MOD;
                    long ways_R = (C(rightOther_no_j, 2) - rightSumSq_no_j + MOD) % MOD;
                    term1 = (term1 + leftCounts[j] * ways_R) % MOD;
                }
                totalCount = (totalCount + leftEqual * term1) % MOD;

                long term2 = 0;
                for(int j=0; j<m; ++j) {
                    if (j == x || rightCounts[j] == 0) continue;
                    long leftOther_no_j = leftOther - leftCounts[j];
                    long leftSumSq_no_j = (leftSumSq - C(leftCounts[j], 2) + MOD) % MOD;
                    long ways_L = (C(leftOther_no_j, 2) - leftSumSq_no_j + MOD) % MOD;
                    term2 = (term2 + rightCounts[j] * ways_L) % MOD;
                }
                totalCount = (totalCount + rightEqual * term2) % MOD;
            }
            leftCounts[x]++;
        }

        return (int) totalCount;
    }

    private long C(long n, int k) {
        if (k < 0 || k > n) return 0;
        return C[(int)n][k];
    }
}
```
### Algorithm
*   First, perform coordinate compression on `nums` to handle large integer values, mapping them to a smaller range `0` to `m-1`, where `m` is the number of unique elements.
*   Precompute combinations `C(n, k)` up to `n=N` to quickly calculate ways to choose elements.
*   Iterate through each index `i` from `2` to `n-3`, considering `nums[i]` as the middle element `x`.
*   Maintain two frequency maps: `left_counts` for elements in `nums[0...i-1]` and `right_counts` for `nums[i+1...n-1]`. These are updated in `O(m)` or better as `i` moves.
*   For each `i`, calculate the number of valid subsequences:
    1.  **Case `freq_x >= 3`**: The middle element `x` is guaranteed to be the unique mode. Calculate the number of ways to choose 2 elements from the left and 2 from the right such that the total count of `x` is 3, 4, or 5. This is done using combinatorial formulas on `left_counts` and `right_counts`.
    2.  **Case `freq_x = 2`**: The other three chosen elements must be distinct. This is the complex part. We count ways to choose one `x` from the left/right parts and three distinct non-`x` elements. This can be broken down:
        *   Ways to pick `(x, y1)` from the left and `(y2, y3)` from the right, where `y1, y2, y3` are distinct non-`x` values.
        *   Ways to pick `(y1, y2)` from the left and `(x, y3)` from the right, where `y1, y2, y3` are distinct non-`x` values.
        *   This subproblem can be solved by iterating through the `m` unique values and using the frequency maps to count valid combinations.
*   Sum up the counts for all `i`, taking modulo at each step.