We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Subsequences with a Unique Middle Mode I

Number: 3700

Difficulty: Hard

Paid? No

Companies: N/A

Problem Description

Given an integer array nums, count how many subsequences of length 5 have a “unique middle mode”. In a sequence of five elements (selected in their original order) the middle element (index 2 in 0‐indexed order) must be the unique mode – that is, its value must appear more times than any other value in the 5–element subsequence. Since the answer can be huge, return the result modulo 10^9+7.

For example, in nums = [1,2,2,3,3,4] the subsequences [1,2,2,3,4] and [1,2,3,3,4] are valid, whereas [1,2,2,3,3] is not (because both 2 and 3 appear twice).

Key Insights

  • The subsequence must consist of 5 indices chosen in increasing order. The element at the third (middle) position is “special.”
  • For the middle element’s value (say X) to be the unique mode, X must appear at least twice (in fact, the valid total counts are 2, 3, 4, or 5 in the subsequence); moreover, every other number in the selection must appear at most once.
  • It is natural to “fix” the candidate middle index and treat the remaining two indices before and after it independently. In the left block (indices before the middle) and the right block (indices after the middle) we have to choose two positions each.
  • For each side, we must count separately the ways to choose indices that contribute a given number of occurrences of the candidate value and, when selecting non–candidate indices, ensure that we pick distinct values (so that no other number can “tie” or exceed the frequency of X).
  • By iterating through possible middle indices and “merging” the counts from both sides (with the constraint that the total extra occurrences of X is at least one), we can sum up the valid combinations.

Space and Time Complexity

Time Complexity: O(n · D^2) in the worst case, where n is the length of nums and D is the number of distinct non–candidate values on a side (typically much smaller than n). Since n ≤ 1000 the solution is acceptable. Space Complexity: O(n) for counters and auxiliary storage.

Solution

The main idea is to iterate over every possible index to serve as the middle of a subsequence. For each middle index, consider:

  1. Let candidate = nums[middle]. The left side consists of indices strictly less than middle and the right side consists of indices greater than middle.
  2. For each side (left and right) we need to select exactly 2 indices. In doing so we count separately:
    • How many ways to choose 0 occurrences of candidate (i.e. pick 2 non–candidate indices with distinct values);
    • How many ways to choose 1 occurrence of candidate (i.e. choose 1 candidate index multiplied by a choice of one non–candidate index);
    • How many ways to choose 2 occurrences of candidate (only from indices equal to candidate).
  3. Only those selections where the total extra candidate count (from left and right) is at least 1 are valid (since the chosen middle already contributes one, and a unique mode requires candidate frequency > frequency of any other value).
  4. For each side, the calculation for non–candidate selections involves enumerating distinct values – if we need one non–candidate index, simply sum counts; if we need two, sum over distinct pairs (v, w) where v ≠ w.
  5. By multiplying valid left and right selections (summing for appropriate candidate counts on left and right with at least one occurrence in total) and then summing these for every possible middle index, we obtain the answer.
  6. Modular arithmetic is applied throughout to handle large numbers.

The key “gotcha” is correctly counting ways to choose non–candidate positions without repetition of values because if a non–candidate appears twice then it would tie with candidate frequency when candidate count is 2.

Code Solutions

# Python solution with line-by-line comments
MOD = 10**9 + 7

def choose_two_from_counter(counter):
    # Given a dictionary 'counter' of frequencies, count ways to choose 2 items from distinct keys.
    keys = list(counter.keys())
    ways = 0
    for i in range(len(keys)):
        for j in range(i+1, len(keys)):
            ways = (ways + counter[keys[i]] * counter[keys[j]]) % MOD
    return ways

def compute_side(counter, candidate):
    # This function computes ways to choose 2 indices from one side (either left or right),
    # categorizing the selections by the count of candidate under consideration.
    cand_count = counter.get(candidate, 0)
    # Create a counter for non-candidate values on this side.
    non_cand_counter = {}
    for key, value in counter.items():
        if key != candidate:
            non_cand_counter[key] = value
    ways = {0: 0, 1: 0, 2: 0}
    # Case 0: choose 2 non-candidate indices.
    # For this, we require chosen non-candidate values to be distinct.
    ways[0] = choose_two_from_counter(non_cand_counter)
    # Case 1: choose 1 candidate index and 1 non-candidate index.
    if cand_count >= 1:
        total_non = sum(non_cand_counter.values()) % MOD
        ways[1] = (cand_count * total_non) % MOD
    # Case 2: choose 2 candidate indices.
    if cand_count >= 2:
        ways[2] = (cand_count * (cand_count - 1) // 2) % MOD
    return ways

def countSubsequences(nums):
    n = len(nums)
    ans = 0
    # Counters for indices left and right of mid.
    left_counter = {}
    right_counter = {}
    # Initially, right_counter contains all indices.
    for num in nums:
        right_counter[num] = right_counter.get(num, 0) + 1
    
    # Iterate over each possible middle index.
    for mid in range(n):
        candidate = nums[mid]
        # Remove nums[mid] from right, as it becomes the fixed mid element.
        right_counter[candidate] -= 1
        if right_counter[candidate] == 0:
            del right_counter[candidate]
        
        # Only consider mid if there are at least 2 elements on the left and right.
        if mid >= 2 and (n - mid - 1) >= 2:
            left_ways = compute_side(left_counter, candidate)
            right_ways = compute_side(right_counter, candidate)
            # We need total extra candidate count (from left and right) to be at least 1.
            for left_cand in range(3):  # can be 0,1,2 from left side.
                for right_cand in range(3):  # 0,1,2 from right side.
                    if left_cand + right_cand >= 1:
                        ways = (left_ways[left_cand] * right_ways[right_cand]) % MOD
                        ans = (ans + ways) % MOD
        # Add the current mid element into the left_counter as we move forward.
        left_counter[candidate] = left_counter.get(candidate, 0) + 1
    return ans

# Example usage:
if __name__ == "__main__":
    print(countSubsequences([1,1,1,1,1,1]))  # Expected output: 6
    print(countSubsequences([1,2,2,3,3,4]))  # Expected output: 4
← Back to All Questions