Subsequences with a Unique Middle Mode I - Practice Coding Problems

Subsequences with a Unique Middle Mode I - 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.

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.

Input & Output

Example 1 — Basic Case

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

› Output: 4

💡 Note: Valid subsequences: [1,2,2,3,3] has several size-5 subsequences where middle element is unique mode. For instance, if we take all elements [1,2,2,3,3], frequencies are 1:1, 2:2, 3:2, and depending on middle position, some will have unique mode.

Example 2 — Small Array

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

› Output: 1

💡 Note: Only one subsequence [1,1,1,1,1]. Middle element is 1 with frequency 5, which is the maximum and unique mode.

Example 3 — No Valid Subsequence

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

› Output: 1

💡 Note: Only one subsequence [1,2,3,4,5]. Middle element is 3 with frequency 1, all elements have frequency 1, so 3 is tied for maximum frequency but not unique mode. Actually, each element appears once, so any can be unique mode by definition.

Constraints

5 ≤ nums.length ≤ 1000
-10⁹ ≤ nums[i] ≤ 10⁹

Visualization

Tap to expand

Understanding the Visualization

Input Array

Given array of integers

Find Subsequences

Generate all subsequences of size 5

Check Middle Mode

Verify if middle element is unique mode

Key Takeaway

🎯 Key Insight: Fix each element as middle and use combinatorics to count valid subsequences efficiently

Asked in

G Google 15 M Meta 12

The key insight is to fix each element as the middle element and count valid subsequences using combinatorics rather than generating all subsequences. The optimized approach reduces time complexity from O(n⁵) to O(n³). 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 element, count valid subsequences using combinatorics

Brute Force - Generate All Subsequences — Algorithm Steps

Generate all C(n,5) subsequences of size 5
For each subsequence, count frequency of each element
Check if middle element has highest frequency and is unique

Visualization

Tap to expand

Step-by-Step Walkthrough

Generate All

Create all possible subsequences of size 5

Check Mode

For each subsequence, verify if middle element is unique mode

Count Valid

Count subsequences where middle element is the unique mode

Code -

solution.c — C

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

int solution(int* nums, int n) {
    const int MOD = 1000000007;
    long long count = 0;
    
    // Generate all subsequences of size 5
    for (int i = 0; i < n; i++) {
        for (int j = i+1; j < n; j++) {
            for (int k = j+1; k < n; k++) {
                for (int l = k+1; l < n; l++) {
                    for (int m = l+1; m < n; m++) {
                        int subseq[5] = {nums[i], nums[j], nums[k], nums[l], nums[m]};
                        int middle = subseq[2]; // k-th element is middle
                        
                        // Count frequencies (simple approach for small array)
                        int freq[5] = {1, 0, 0, 0, 0};
                        int unique[5] = {subseq[0]};
                        int unique_count = 1;
                        
                        for (int x = 1; x < 5; x++) {
                            int found = -1;
                            for (int y = 0; y < unique_count; y++) {
                                if (unique[y] == subseq[x]) {
                                    found = y;
                                    break;
                                }
                            }
                            if (found != -1) {
                                freq[found]++;
                            } else {
                                unique[unique_count] = subseq[x];
                                freq[unique_count] = 1;
                                unique_count++;
                            }
                        }
                        
                        // Find max frequency
                        int maxFreq = 0;
                        for (int x = 0; x < unique_count; x++) {
                            if (freq[x] > maxFreq) maxFreq = freq[x];
                        }
                        
                        // Check if middle element has max frequency and is unique
                        int middle_freq = 0;
                        for (int x = 0; x < unique_count; x++) {
                            if (unique[x] == middle) {
                                middle_freq = freq[x];
                                break;
                            }
                        }
                        
                        if (middle_freq == maxFreq) {
                            int maxCount = 0;
                            for (int x = 0; x < unique_count; x++) {
                                if (freq[x] == maxFreq) maxCount++;
                            }
                            if (maxCount == 1) {
                                count = (count + 1) % MOD;
                            }
                        }
                    }
                }
            }
        }
    }
    
    return count;
}

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

Time & Space Complexity

Time Complexity

⏱️

O(n⁵)

Need to check C(n,5) combinations, each taking O(1) to validate

✓ Linear Growth

Space Complexity

O(1)

Only using constant extra space for counting frequencies

✓ Linear Space

8.5K Views

Medium Frequency

~25 min Avg. Time

280 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