Subsequences with a Unique Middle Mode I - Solution & Explanation

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

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

The most direct idea is to generate every subsequence of length five using nested loops or combinations. For each candidate subsequence, compute the frequency of all five elements and check whether the third element is the unique mode. This requires counting occurrences and verifying that no other value reaches the same maximum frequency. While simple to reason about, the approach quickly becomes infeasible because the number of subsequences grows as C(n,5). It only works for very small arrays and mainly serves as a correctness baseline.

Approach 2: Prefix/Suffix Frequency Counting + Combinatorics (O(n) time, O(n) space)

The optimized solution fixes each index i as the middle of the subsequence and counts valid ways to pick two elements on the left and two on the right. Use frequency maps to maintain counts of values before and after the current index. The key observation: for the middle value x = nums[i] to be the unique mode, the subsequence must contain additional occurrences of x while ensuring no other number ties its frequency.

Maintain prefix and suffix frequency maps while iterating through the array. For each middle index, compute combinations of positions on the left and right using combinatorics such as C(k,2). Count cases where extra x elements appear on either side and subtract invalid configurations where another value could match the frequency of x. Hash lookups make frequency queries constant time, and combinatorial formulas avoid enumerating subsequences explicitly.

This transforms the problem into counting valid distributions of elements around the middle while tracking frequencies efficiently. The approach relies heavily on hash tables for frequency tracking and combinatorics to compute pair selections. The array is processed once, making it scalable even for large inputs. Understanding how prefix/suffix counts interact with subsequence selection is the main challenge.

Recommended for interviews: Interviewers expect the combinatorics + frequency counting approach. Starting with brute force demonstrates understanding of the constraint (fixed subsequence length), but the optimized solution shows skill with counting techniques and data structures from array processing and hash-based frequency tracking.