Subsequences with a Unique Middle Mode II - Solution & Explanation

Problem Overview: You are given an array and must count subsequences of length 5 where the third element is the unique mode of the subsequence. The middle value must appear more times than every other value in that subsequence.

Approach 1: Brute Force Enumeration (O(n^5) time, O(1) space)

Generate every subsequence of length five using five nested loops. For each candidate subsequence, compute the frequency of its elements using a small counter and check whether the third element has strictly higher frequency than all others. The logic is straightforward and useful for verifying correctness on small inputs. The approach becomes impractical once n grows because the number of combinations explodes to O(n^5).

Approach 2: Fix Middle + Frequency Counting (O(n^2) time, O(n) space)

Instead of enumerating all subsequences, fix index i as the middle element. You then choose two elements from the left side and two from the right side. Maintain frequency maps for elements on both sides using a hash table. For each middle position, count combinations that make nums[i] the most frequent value. This reduces the search space dramatically because you only explore combinations around the fixed middle.

Approach 3: Prefix-Suffix Combinatorics (Optimal) (O(n) time, O(n) space)

The optimal solution treats the middle index as the anchor and counts valid combinations using combinatorics. Maintain prefix counts for elements before i and suffix counts for elements after i. For the middle value x, compute how many ways it can appear multiple times in the chosen positions so it becomes the unique mode. Use combinatorial formulas like C(k,2) to count pairs on the left or right, while subtracting cases where another value ties the frequency of x. Hash maps track frequencies dynamically as you iterate across the array. This converts explicit enumeration into arithmetic counting and keeps the runtime linear. The technique combines ideas from array scanning, hash table frequency tracking, and combinatorics.

Recommended for interviews: Start by explaining the brute force idea to show understanding of the constraint (unique mode centered at index 2). Then transition to the prefix–suffix combinatorics approach. Interviewers expect you to reduce enumeration using counting formulas and frequency maps, which demonstrates strong combinatorial reasoning and efficient array traversal.