Subsequences with a Unique Middle Mode II

Subsequences with a Unique Middle Mode II - 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 10^9 + 7.

Definitions:

A mode of a sequence is the element that appears the maximum number of times in the sequence.
A sequence has a unique mode if it has only one mode (no ties for most frequent).
A subsequence of size 5 has a unique middle mode if the middle element (at index 2) is the unique mode of the subsequence.

Note: A subsequence maintains the relative order of elements from the original array but doesn't need to be contiguous.

Input & Output

Example 1 — Basic Case

$ Input: nums = [1,2,1,3,1]

› Output: 3

💡 Note: Three valid subsequences with unique middle mode: [1,2,1,3,1] at indices (0,1,2,3,4), (0,1,4,3,2), etc. where middle element has highest frequency uniquely.

Example 2 — No Valid Subsequences

$ Input: nums = [1,1,1,1,1]

› Output: 0

💡 Note: All elements are the same, so no subsequence can have a unique mode - there are always ties.

Example 3 — Minimum Size

$ Input: nums = [1,2,3,4,5]

› Output: 0

💡 Note: All elements are distinct, so in any subsequence of size 5, all elements appear once. No unique mode possible since middle element doesn't have higher frequency.

Constraints

5 ≤ nums.length ≤ 2000
1 ≤ nums[i] ≤ 10⁵

Visualization

Tap to expand

Understanding the Visualization

Input Array

Given integer array with potentially duplicate elements

Find Subsequences

Look for size-5 subsequences where middle element appears most frequently

Count Valid

Count subsequences where middle element is unique mode

Key Takeaway

🎯 Key Insight: Fix the middle element and use combinatorics to count valid left/right combinations efficiently

Asked in

G Google 15 f Facebook 12 a Amazon 8

The key insight is to fix each possible middle element and use combinatorial mathematics to count valid subsequences without generating them explicitly. For each middle position, we calculate how many ways we can select elements from left and right parts such that the middle element becomes the unique mode. Best approach uses frequency counting + combinatorics. Time: O(n²), Space: O(n)

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Generate All Subsequences	O(n⁵)	O(1)	Generate all possible subsequences of size 5 and check each one
Optimized - Fix Middle Element	O(n²)	O(n)	For each middle position, count valid subsequences using combinatorics

Brute Force - Generate All Subsequences — Algorithm Steps

Generate all combinations of 5 indices from the array
For each combination, create the subsequence and count element frequencies
Check if middle element has highest frequency with no ties
Count all valid subsequences

Visualization

Tap to expand

Step-by-Step Walkthrough

Generate

Create all possible 5-element subsequences

Check Mode

Count frequencies in each subsequence

Validate

Check if middle element is unique mode

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MOD 1000000007

int solution(int* nums, int n) {
    if (n < 5) return 0;
    
    long long count = 0;
    
    // Generate all combinations of 5 indices
    for (int i = 0; i < n - 4; i++) {
        for (int j = i + 1; j < n - 3; j++) {
            for (int k = j + 1; k < n - 2; k++) {
                for (int l = k + 1; l < n - 1; l++) {
                    for (int m = l + 1; m < n; m++) {
                        int subseq[5] = {nums[i], nums[j], nums[k], nums[l], nums[m]};
                        int middleVal = subseq[2];
                        
                        // Count frequencies (simple array for small subsequence)
                        int freq[5] = {1, 0, 0, 0, 0};
                        int unique[5] = {subseq[0]};
                        int uniqueCount = 1;
                        
                        for (int x = 1; x < 5; x++) {
                            int found = 0;
                            for (int y = 0; y < uniqueCount; y++) {
                                if (unique[y] == subseq[x]) {
                                    freq[y]++;
                                    found = 1;
                                    break;
                                }
                            }
                            if (!found) {
                                unique[uniqueCount] = subseq[x];
                                freq[uniqueCount] = 1;
                                uniqueCount++;
                            }
                        }
                        
                        // Find max frequency and check if middle is unique mode
                        int maxFreq = 0;
                        for (int x = 0; x < uniqueCount; x++) {
                            if (freq[x] > maxFreq) maxFreq = freq[x];
                        }
                        
                        int middleFreq = 0;
                        int maxFreqCount = 0;
                        for (int x = 0; x < uniqueCount; x++) {
                            if (unique[x] == middleVal) middleFreq = freq[x];
                            if (freq[x] == maxFreq) maxFreqCount++;
                        }
                        
                        if (middleFreq == maxFreq && maxFreqCount == 1) {
                            count++;
                        }
                    }
                }
            }
        }
    }
    
    return count % MOD;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    line[strcspn(line, "\n")] = 0;
    
    // Parse JSON array manually
    int nums[1000];
    int n = 0;
    char* token = strtok(line + 1, ",]");
    while (token != NULL) {
        nums[n++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    printf("%d\n", solution(nums, n));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n⁵)

Generate C(n,5) = O(n⁵) subsequences, check each in O(1)

✓ Linear Growth

Space Complexity

O(1)

Only using constant extra space for frequency counting

✓ Linear Space

8.5K Views

Medium Frequency

~35 min Avg. Time

245 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Generate All Subsequences — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler