Subsequences with a Unique Middle Mode I

Hard

#3016Time: 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).

Patterns

Math Combinatorics

Data structures

Array Hash Table

Prompt

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 10⁹ + 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
-10⁹ <= nums[i] <= 10⁹

Approaches

2 approaches with complexity analysis and trade-offs.

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.

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.

Walkthrough

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.

1class Solution {2    public int countSubsequences(int[] nums) {3        int n = nums.length;4        long count = 0;5        int MOD = 1_000_000_007;6 7        for (int i1 = 0; i1 < n; i1++) {8            for (int i2 = i1 + 1; i2 < n; i2++) {9                for (int i3 = i2 + 1; i3 < n; i3++) {10                    for (int i4 = i3 + 1; i4 < n; i4++) {11                        for (int i5 = i4 + 1; i5 < n; i5++) {12                            int[] sub = {nums[i1], nums[i2], nums[i3], nums[i4], nums[i5]};13                            if (isUniqueMiddleMode(sub)) {14                                count++;15                            }16                        }17                    }18                }19            }20        }21 22        return (int) (count % MOD);23    }24 25    private boolean isUniqueMiddleMode(int[] sub) {26        java.util.Map<Integer, Integer> freq = new java.util.HashMap<>();27        for (int num : sub) {28            freq.put(num, freq.getOrDefault(num, 0) + 1);29        }30 31        int middleElement = sub[2];32        int middleFreq = freq.get(middleElement);33 34        if (middleFreq == 0) return false; // Should not happen35 36        for (java.util.Map.Entry<Integer, Integer> entry : freq.entrySet()) {37            if (entry.getKey() != middleElement) {38                if (entry.getValue() >= middleFreq) {39                    return false;40                }41            }42        }43        return true;44    }45}

Complexity

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).

Trade-offs

Pros

Simple to understand and implement.

Cons

Extremely inefficient and will time out for the given constraints (N <= 1000).

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.

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.

Walkthrough

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:

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.
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.

1class Solution {2    long[][] C;3    int MOD = 1_000_000_007;4 5    public int countSubsequences(int[] nums) {6        int n = nums.length;7        if (n < 5) return 0;8 9        // Coordinate Compression10        java.util.Set<Integer> set = new java.util.HashSet<>();11        for (int num : nums) set.add(num);12        java.util.List<Integer> sortedUnique = new java.util.ArrayList<>(set);13        java.util.Collections.sort(sortedUnique);14        java.util.Map<Integer, Integer> valToRank = new java.util.HashMap<>();15        for (int i = 0; i < sortedUnique.size(); i++) {16            valToRank.put(sortedUnique.get(i), i);17        }18        int[] compressedNums = new int[n];19        for (int i = 0; i < n; i++) {20            compressedNums[i] = valToRank.get(nums[i]);21        }22        int m = sortedUnique.size();23 24        // Precompute combinations25        C = new long[n + 1][6];26        for (int i = 0; i <= n; i++) {27            C[i][0] = 1;28            for (int j = 1; j <= Math.min(i, 5); j++) {29                C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % MOD;30            }31        }32 33        long totalCount = 0;34        int[] rightCounts = new int[m];35        for (int num : compressedNums) rightCounts[num]++;36 37        int[] leftCounts = new int[m];38 39        for (int i = 0; i < n; i++) {40            int x = compressedNums[i];41            rightCounts[x]--;42 43            if (i >= 2 && i <= n - 3) {44                long leftTotal = i;45                long rightTotal = n - 1 - i;46                long leftEqual = leftCounts[x];47                long rightEqual = rightCounts[x];48                long leftOther = leftTotal - leftEqual;49                long rightOther = rightTotal - rightEqual;50 51                // Case 1: freq_x >= 352                // freq_x = 3: (1+2+0, 1+1+1, 1+0+2)53                long count3 = (C(leftEqual, 2) * C(rightOther, 2)) % MOD;54                count3 = (count3 + (leftEqual * leftOther % MOD) * (rightEqual * rightOther % MOD)) % MOD;55                count3 = (count3 + C(leftOther, 2) * C(rightEqual, 2)) % MOD;56                // freq_x = 4: (1+3+0, 1+2+1, 1+1+2, 1+0+3)57                long count4 = (C(leftEqual, 2) * rightEqual % MOD * rightOther % MOD) % MOD;58                count4 = (count4 + leftEqual * leftOther % MOD * C(rightEqual, 2) % MOD) % MOD;59                // freq_x = 560                long count5 = (C(leftEqual, 2) * C(rightEqual, 2)) % MOD;61 62                totalCount = (totalCount + count3 + count4 + count5) % MOD;63 64                // Case 2: freq_x = 265                long leftSumSq = 0, rightSumSq = 0;66                for(int j=0; j<m; ++j) {67                    if (j == x) continue;68                    leftSumSq = (leftSumSq + C(leftCounts[j], 2)) % MOD;69                    rightSumSq = (rightSumSq + C(rightCounts[j], 2)) % MOD;70                }71                long leftDistinctPairs = (C(leftOther, 2) - leftSumSq + MOD) % MOD;72                long rightDistinctPairs = (C(rightOther, 2) - rightSumSq + MOD) % MOD;73 74                long term1 = 0;75                for(int j=0; j<m; ++j) {76                    if (j == x || leftCounts[j] == 0) continue;77                    long rightOther_no_j = rightOther - rightCounts[j];78                    long rightSumSq_no_j = (rightSumSq - C(rightCounts[j], 2) + MOD) % MOD;79                    long ways_R = (C(rightOther_no_j, 2) - rightSumSq_no_j + MOD) % MOD;80                    term1 = (term1 + leftCounts[j] * ways_R) % MOD;81                }82                totalCount = (totalCount + leftEqual * term1) % MOD;83 84                long term2 = 0;85                for(int j=0; j<m; ++j) {86                    if (j == x || rightCounts[j] == 0) continue;87                    long leftOther_no_j = leftOther - leftCounts[j];88                    long leftSumSq_no_j = (leftSumSq - C(leftCounts[j], 2) + MOD) % MOD;89                    long ways_L = (C(leftOther_no_j, 2) - leftSumSq_no_j + MOD) % MOD;90                    term2 = (term2 + rightCounts[j] * ways_L) % MOD;91                }92                totalCount = (totalCount + rightEqual * term2) % MOD;93            }94            leftCounts[x]++;95        }96 97        return (int) totalCount;98    }99 100    private long C(long n, int k) {101        if (k < 0 || k > n) return 0;102        return C[(int)n][k];103    }104}

Complexity

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`.

Trade-offs

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.

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem