Problem Description
Given an integer array nums, find the number of subsequences of size 5 of nums with a unique middle mode. A mode of a sequence 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 size 5 contains a unique middle mode if the middle element is a unique mode. Return the result modulo 10^9 + 7.
Key Insights
- The middle element of the subsequence (index 2) must be the highest frequency element for it to be a unique middle mode.
- The counts of elements can be efficiently stored in a hashmap or frequency array.
- Use combinatorial counting to determine the number of valid subsequences based on the frequency of the middle element and the remaining elements.
Space and Time Complexity
Time Complexity: O(n^2)
Space Complexity: O(n)
Solution
To solve the problem, we utilize a frequency map to track how many times each number appears in the input array. We then iterate through each unique element in the array and treat it as a candidate for the middle mode. For each candidate, we calculate the number of ways to select 2 additional elements less than the middle mode and 2 greater than it, ensuring that no other elements can match the frequency of the middle mode. We sum these counts for all unique candidates and return the total modulo 10^9 + 7.