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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Find the Median of the Uniqueness Array

Difficulty: Hard

Problem Description

You are given an integer array nums. The uniqueness array of nums is the sorted array that contains the number of distinct elements of all the subarrays of nums. In other words, it is a sorted array consisting of distinct(nums[i..j]), for all 0 <= i <= j < nums.length.

Return the median of the uniqueness array of nums.

Note that the median of an array is defined as the middle element of the array when it is sorted in non-decreasing order. If there are two choices for a median, the smaller of the two values is taken.

Key Insights

  • The uniqueness array is formed by calculating the number of distinct elements in all possible subarrays of the input array.
  • Efficiently calculating distinct elements in subarrays can be done using a sliding window technique combined with a hash map or frequency array.
  • The median can be computed from the uniqueness array once it is sorted.

Space and Time Complexity

Time Complexity: O(n^2) in the worst case for generating all subarrays, but can be optimized to O(n log n) with sorting. Space Complexity: O(n) for storing the distinct counts.

Solution

To solve the problem, we use a sliding window approach to count the distinct elements in all subarrays. The frequency of each element is maintained using a hash map. As we iterate through the array, we expand the right boundary of the window and keep track of the counts. When the right boundary moves, we check how many distinct elements are present in the current window and store these counts in a list. Once we have all counts, we sort the list and find the median.

Code Solutions

def findMedian(nums):
    from collections import defaultdict

    n = len(nums)
    uniqueness_counts = []

    for i in range(n):
        count_map = defaultdict(int)
        distinct_count = 0
        
        for j in range(i, n):
            if count_map[nums[j]] == 0:
                distinct_count += 1
            count_map[nums[j]] += 1
            
            uniqueness_counts.append(distinct_count)

    uniqueness_counts.sort()
    length = len(uniqueness_counts)
    
    if length % 2 == 0:
        return uniqueness_counts[length // 2 - 1]
    else:
        return uniqueness_counts[length // 2]

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