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

Find the Median of the Uniqueness Array

Number: 3362

Difficulty: Hard

Paid? No

Companies: Amazon, Microsoft

Problem Description

Given an integer array nums, the uniqueness array is defined as the sorted array of the number of distinct elements for every contiguous subarray of nums. For each subarray nums[i..j], let distinct(nums[i..j]) be the number of unique elements in that subarray. The task is to compute the median of this uniqueness array. When the uniqueness array has an even number of elements, the median is defined as the smaller of the two middle values.

Key Insights

  • Directly generating all subarrays and calculating their distinct count leads to a time complexity that is infeasible for n up to 10^5.
  • Instead of building the uniqueness array explicitly, we can count how many subarrays have exactly k distinct elements.
  • Use the sliding window technique to efficiently compute count_at_most(k): the number of subarrays with at most k distinct elements.
  • The number of subarrays with exactly k distinct elements equals count_at_most(k) minus count_at_most(k-1) (inclusion-exclusion).
  • With these counts, and knowing that the total number of subarrays is n*(n+1)/2, we can iterate over possible k values (from 1 to n) and accumulate frequencies until reaching the median target, which is (total_subarrays + 1) // 2 when considering 1-based indexing.
  • An alternative approach is to use binary search over candidate answers based on the monotonicity properties of count_at_most; however, the cumulative frequency iteration is straightforward given the range of k.

Space and Time Complexity

Time Complexity: O(n log n) overall, where each count_at_most(k) is O(n) but careful cumulative counting (or binary search optimization) helps control the overall complexity. Space Complexity: O(n) due to frequency maps and additional variables.

Solution

The solution uses a helper function count_at_most(nums, k) which implements a sliding window approach using two pointers and a frequency map to count the subarrays having at most k distinct numbers. Then, the difference count_at_most(k) - count_at_most(k-1) gives the number of subarrays with exactly k distinct elements. By iterating over all possible k values and maintaining a cumulative sum of these exact counts, we determine the smallest k for which the cumulative frequency reaches or exceeds the median index in the sorted uniqueness array.

Code Solutions

def count_at_most(nums, k):
    # Returns the count of subarrays with at most k distinct numbers.
    n = len(nums)
    total = 0
    left = 0
    freq = {}
    for right in range(n):
        freq[nums[right]] = freq.get(nums[right], 0) + 1
        # If distinct count exceeds k, move left pointer to reduce it.
        while len(freq) > k:
            freq[nums[left]] -= 1
            if freq[nums[left]] == 0:
                del freq[nums[left]]
            left += 1
        total += (right - left + 1)
    return total

def findMedianUniqueness(nums):
    n = len(nums)
    total_subarrays = n * (n + 1) // 2
    # Median target index (1-indexed)
    median_target = (total_subarrays + 1) // 2
    cumulative = 0
    prev_at_most = 0
    for k in range(1, n + 1):
        current_at_most = count_at_most(nums, k)
        exact = current_at_most - prev_at_most  # count of subarrays with exactly k distinct
        cumulative += exact
        if cumulative >= median_target:
            return k
        prev_at_most = current_at_most
    return -1  # fallback; should never reach here

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