DevExCode

LeetCode 3134: Find the Median of the Uniqueness Array Solution

Master LeetCode problem 3134 (Find the Median of the Uniqueness Array), a hard challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

3134. Find the Median of the Uniqueness Array

Hard
ArrayHash TableBinary SearchSliding Window

Problem Explanation

Explanation

To find the median of the uniqueness array of the given integer array nums, we can follow these steps:

  1. Count the frequency of each element in the array nums.
  2. For each subarray of nums, calculate the number of distinct elements using the frequency counts.
  3. Construct the uniqueness array by collecting the distinct counts for all subarrays.
  4. Sort the uniqueness array and find the median.

Time complexity:

  • Counting the frequency of elements: O(n)
  • Calculating the distinct elements for all subarrays: O(n^2)
  • Constructing the uniqueness array: O(n^2)
  • Sorting the uniqueness array: O(n^2 * log(n)) Overall time complexity: O(n^2 * log(n))

Space complexity:

  • Storing the frequency counts: O(n)
  • Storing the uniqueness array: O(n^2) Overall space complexity: O(n^2)

Solution Code

class Solution {
    public double medianUniq(int[] nums) {
        int n = nums.length;
        List<Integer> uniqueness = new ArrayList<>();
        
        for (int i = 0; i < n; i++) {
            Map<Integer, Integer> freq = new HashMap<>();
            int distinct = 0;
            for (int j = i; j < n; j++) {
                freq.put(nums[j], freq.getOrDefault(nums[j], 0) + 1);
                if (freq.get(nums[j]) == 1) {
                    distinct++;
                } else if (freq.get(nums[j]) == 2) {
                    distinct--;
                }
                uniqueness.add(distinct);
            }
        }
        
        Collections.sort(uniqueness);
        return n % 2 == 0 ? (uniqueness.get(n * (n-1) / 2) + uniqueness.get(n * (n-1) / 2 + 1)) / 2.0 : uniqueness.get(n * (n-1) / 2);
    }
}

Try It Yourself

Loading code editor...

Related LeetCode Problems

Frequently Asked Questions

How to solve LeetCode 3134 (Find the Median of the Uniqueness Array)?

This page provides optimized solutions for LeetCode problem 3134 (Find the Median of the Uniqueness Array) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 3134 (Find the Median of the Uniqueness Array)?

The time complexity for LeetCode 3134 (Find the Median of the Uniqueness Array) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 3134 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 3134 in Java, C++, or Python.

Back to LeetCode Solutions