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

Count Subarrays With Median K

Number: 2574

Difficulty: Hard

Paid? No

Companies: thoughtspot, Google

Problem Description

Given an array nums containing distinct integers from 1 to n and a positive integer k, determine the number of non-empty contiguous subarrays in nums that have k as their median. The median is defined as the middle element after sorting a subarray in ascending order (if even-length, it is the left middle element). Note that for a subarray to have median k, it must include k.

Key Insights

  • Transform the array by mapping each element to:
    • 0 if it equals k
    • 1 if it is greater than k
    • -1 if it is less than k
  • Find the index (pivot) where nums equals k. All valid subarrays must include this pivot.
  • For subarrays to satisfy the median condition, the cumulative “balance” of 1’s and -1’s must be either 0 or -1 when combining segments to the left and right of the pivot.
  • Use a prefix sum technique on the left segment of the pivot to count balance frequencies.
  • For each element in the right segment (starting at the pivot), accumulate the balance and count complementary prefix frequencies that form a valid subarray.

Space and Time Complexity

Time Complexity: O(n) – We traverse the array twice (once for the left side and once for the right side). Space Complexity: O(n) – In the worst case, the hash table storing prefix sum frequencies could contain O(n) entries.

Solution

The approach involves transforming the array based on comparisons with k, then finding the pivot index where the element equals k. For all indices left of the pivot, accumulate a prefix “balance” by adding -1 when an element is less than k and +1 when greater than k. Store the frequency of these prefix sums in a dictionary. Next, starting at the pivot and moving rightwards, update a running balance using the same transformation. For each new balance, valid subarrays that include k can be found by adding the frequencies of the current balance and (current balance - 1) from the left side dictionary. This works because a valid subarray, after insertion of k, must achieve a balance that conforms with the median requirement (equal numbers of values higher and lower than k or one extra higher value for even lengths with left middle median). Finally, sum these counts to get the answer.

Code Solutions

# Python solution for Count Subarrays With Median K

def countSubarrays(nums, k):
    # Find pivot index where nums[i] == k
    pivot = nums.index(k)
    
    # Dictionary to store frequencies of prefix balances on the left side of pivot
    prefix_balance = {0: 1}
    balance = 0

    # Process left side (elements before pivot)
    for i in range(pivot - 1, -1, -1):
        # Update balance: add -1 if nums[i] < k else +1 if nums[i] > k
        if nums[i] < k:
            balance -= 1
        else:  # nums[i] > k because elements are distinct and k is unique in array
            balance += 1
        # Store the frequency of each balance
        prefix_balance[balance] = prefix_balance.get(balance, 0) + 1

    result = 0
    balance = 0
    # Process from pivot to the end (right side, including pivot)
    for j in range(pivot, len(nums)):
        # Update balance for the right side subarray
        if nums[j] < k:
            balance -= 1
        elif nums[j] > k:
            balance += 1
        # Add count of valid left side prefix balances that 
        # when added to current balance gives overall valid balance
        result += prefix_balance.get(balance, 0) + prefix_balance.get(balance - 1, 0)
    
    return result

# Example usage:
nums = [3, 2, 1, 4, 5]
k = 4
print(countSubarrays(nums, k))  # Expected output: 3
← Back to All Questions