3134. Find the Median of the Uniqueness Array

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.

Here, distinct(nums[i..j]) denotes the number of distinct elements in the subarray that starts at index i and ends at index j.

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.

 

Example 1:

Input: nums = [1,2,3]

Output: 1

Explanation:

The uniqueness array of nums is [distinct(nums[0..0]), distinct(nums[1..1]), distinct(nums[2..2]), distinct(nums[0..1]), distinct(nums[1..2]), distinct(nums[0..2])] which is equal to [1, 1, 1, 2, 2, 3]. The uniqueness array has a median of 1. Therefore, the answer is 1.

Example 2:

Input: nums = [3,4,3,4,5]

Output: 2

Explanation:

The uniqueness array of nums is [1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 3, 3, 3]. The uniqueness array has a median of 2. Therefore, the answer is 2.

Example 3:

Input: nums = [4,3,5,4]

Output: 2

Explanation:

The uniqueness array of nums is [1, 1, 1, 1, 2, 2, 2, 3, 3, 3]. The uniqueness array has a median of 2. Therefore, the answer is 2.

 

Constraints:

• 1 <= nums.length <= 105
• 1 <= nums[i] <= 105

Solutions

Solution 1: Binary Search + Two Pointers

Let the length of the array $\textit{nums}$ be $n$. The length of the uniqueness array is $m = \frac{(1 + n) \times n}{2}$, and the median of the uniqueness array is the $\frac{m + 1}{2}$-th smallest number among these $m$ numbers.

Consider how many numbers in the uniqueness array are less than or equal to $x$. As $x$ increases, there will be more and more numbers less than or equal to $x$. This property is monotonic, so we can use binary search to enumerate $x$ and find the first $x$ such that the number of elements in the uniqueness array less than or equal to $x$ is greater than or equal to $\frac{m + 1}{2}$. This $x$ is the median of the uniqueness array.

We define the left boundary of the binary search as $l = 0$ and the right boundary as $r = n$. Then we perform binary search. For each $\textit{mid}$, we check whether the number of elements in the uniqueness array less than or equal to $\textit{mid}$ is greater than or equal to $\frac{m + 1}{2}$. We achieve this through the function $\text{check}(mx)$.

The implementation idea of the function $\text{check}(mx)$ is as follows:

Since the longer the subarray, the more different elements it contains, we can use two pointers to maintain a sliding window such that the number of different elements in the window does not exceed $mx$. Specifically, we maintain a hash table $\textit{cnt}$, where $\textit{cnt}[x]$ represents the number of occurrences of element $x$ in the window. We use two pointers $l$ and $r$, where $l$ represents the left boundary of the window and $r$ represents the right boundary. Initially, $l = r = 0$.

We enumerate $r$. For each $r$, we add $\textit{nums}[r]$ to the window and update $\textit{cnt}[\textit{nums}[r]]$. If the number of different elements in the window exceeds $mx$, we need to move $l$ to the right until the number of different elements in the window does not exceed $mx$. At this point, the subarrays with the right endpoint $r$ and left endpoints in the range $[l, .., r]$ all meet the condition, and there are $r - l + 1$ such subarrays. We accumulate this count into $k$. If $k$ is greater than or equal to $\frac{m + 1}{2}$, it means that the number of elements in the uniqueness array less than or equal to $\textit{mid}$ is greater than or equal to $\frac{m + 1}{2}$, and we return $\text{true}$; otherwise, we return $\text{false}$.

The time complexity is $O(n \times \log n)$, and the space complexity is $O(n)$. Here, $n$ is the length of the array $\textit{nums}$.

Python3JavaC++GoTypeScript

class Solution:
    def medianOfUniquenessArray(self, nums: List[int]) -> int:
        def check(mx: int) -> bool:
            cnt = defaultdict(int)
            k = l = 0
            for r, x in enumerate(nums):
                cnt[x] += 1
                while len(cnt) > mx:
                    y = nums[l]
                    cnt[y] -= 1
                    if cnt[y] == 0:
                        cnt.pop(y)
                    l += 1
                k += r - l + 1
                if k >= (m + 1) // 2:
                    return True
            return False

        n = len(nums)
        m = (1 + n) * n // 2
        return bisect_left(range(n), True, key=check)

class Solution {
    private long m;
    private int[] nums;

    public int medianOfUniquenessArray(int[] nums) {
        int n = nums.length;
        this.nums = nums;
        m = (1L + n) * n / 2;
        int l = 0, r = n;
        while (l < r) {
            int mid = (l + r) >> 1;
            if (check(mid)) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        return l;
    }

    private boolean check(int mx) {
        Map<Integer, Integer> cnt = new HashMap<>();
        long k = 0;
        for (int l = 0, r = 0; r < nums.length; ++r) {
            int x = nums[r];
            cnt.merge(x, 1, Integer::sum);
            while (cnt.size() > mx) {
                int y = nums[l++];
                if (cnt.merge(y, -1, Integer::sum) == 0) {
                    cnt.remove(y);
                }
            }
            k += r - l + 1;
            if (k >= (m + 1) / 2) {
                return true;
            }
        }
        return false;
    }
}

class Solution {
public:
    int medianOfUniquenessArray(vector<int>& nums) {
        int n = nums.size();
        using ll = long long;
        ll m = (1LL + n) * n / 2;
        int l = 0, r = n;
        auto check = [&](int mx) -> bool {
            unordered_map<int, int> cnt;
            ll k = 0;
            for (int l = 0, r = 0; r < n; ++r) {
                int x = nums[r];
                ++cnt[x];
                while (cnt.size() > mx) {
                    int y = nums[l++];
                    if (--cnt[y] == 0) {
                        cnt.erase(y);
                    }
                }
                k += r - l + 1;
                if (k >= (m + 1) / 2) {
                    return true;
                }
            }
            return false;
        };
        while (l < r) {
            int mid = (l + r) >> 1;
            if (check(mid)) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        return l;
    }
};

func medianOfUniquenessArray(nums []int) int {
    n := len(nums)
    m := (1 + n) * n / 2
    return sort.Search(n, func(mx int) bool {
        cnt := map[int]int{}
        l, k := 0, 0
        for r, x := range nums {
            cnt[x]++
            for len(cnt) > mx {
                y := nums[l]
                cnt[y]--
                if cnt[y] == 0 {
                    delete(cnt, y)
                }
                l++
            }
            k += r - l + 1
            if k >= (m+1)/2 {
                return true
            }
        }
        return false
    })
}

function medianOfUniquenessArray(nums: number[]): number {
    const n = nums.length;
    const m = Math.floor(((1 + n) * n) / 2);
    let [l, r] = [0, n];
    const check = (mx: number): boolean => {
        const cnt = new Map<number, number>();
        let [l, k] = [0, 0];
        for (let r = 0; r < n; ++r) {
            const x = nums[r];
            cnt.set(x, (cnt.get(x) || 0) + 1);
            while (cnt.size > mx) {
                const y = nums[l++];
                cnt.set(y, cnt.get(y)! - 1);
                if (cnt.get(y) === 0) {
                    cnt.delete(y);
                }
            }
            k += r - l + 1;
            if (k >= Math.floor((m + 1) / 2)) {
                return true;
            }
        }
        return false;
    };
    while (l < r) {
        const mid = (l + r) >> 1;
        if (check(mid)) {
            r = mid;
        } else {
            l = mid + 1;
        }
    }
    return l;
}

Comments