Problem

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.

Examples

Example 1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11


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

1
2
3
4
5
6
7
8
9


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

1
2
3
4
5
6
7
8
9


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 <= 10^5
  • 1 <= nums[i] <= 10^5

Solution

Method 1 – Binary Search on Median Value + Sliding Window

Intuition

The uniqueness array consists of the number of distinct elements in all subarrays. To find the median, we do not need to construct the entire array. Instead, we can use binary search on the possible number of distinct elements, and for each candidate, count how many subarrays have at least that many distinct elements using a sliding window.

Approach

  1. The possible values for the number of distinct elements in a subarray range from 1 to n (length of nums).
  2. Use binary search to find the smallest value x such that the number of subarrays with at least x distinct elements is at least half the total number of subarrays.
  3. For each candidate x, use a sliding window to count the number of subarrays with at least x distinct elements.
  4. The answer is the largest x such that the count of subarrays with at least x distinct elements is at least the median position.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

class Solution {
public:
    int medianOfUniquenessArray(vector<int>& nums) {
        int n = nums.size();
        long long total = (long long)n*(n+1)/2;
        long long median_pos = (total+1)/2;
        auto count = [&](int k) -> long long {
            unordered_map<int,int> freq;
            int l=0, cnt=0;
            long long res=0;
            for(int r=0;r<n;++r) {
                if(++freq[nums[r]]==1) ++cnt;
                while(cnt>k) {
                    if(--freq[nums[l++]]==0) --cnt;
                }
                res += r-l+1;
            }
            return res;
        };
        int lo=1, hi=n, ans=1;
        while(lo<=hi) {
            int mid=(lo+hi)/2;
            if(count(mid)>=median_pos) {
                ans=mid;
                lo=mid+1;
            } else {
                hi=mid-1;
            }
        }
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

func medianOfUniquenessArray(nums []int) int {
    n := len(nums)
    total := n*(n+1)/2
    medianPos := (total+1)/2
    count := func(k int) int {
        freq := map[int]int{}
        l, cnt, res := 0, 0, 0
        for r, v := range nums {
            freq[v]++
            if freq[v] == 1 { cnt++ }
            for cnt > k {
                freq[nums[l]]--
                if freq[nums[l]] == 0 { cnt-- }
                l++
            }
            res += r-l+1
        }
        return res
    }
    lo, hi, ans := 1, n, 1
    for lo <= hi {
        mid := (lo+hi)/2
        if count(mid) >= medianPos {
            ans = mid
            lo = mid+1
        } else {
            hi = mid-1
        }
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

class Solution {
    public int medianOfUniquenessArray(int[] nums) {
        int n = nums.length;
        long total = (long)n*(n+1)/2;
        long medianPos = (total+1)/2;
        int lo=1, hi=n, ans=1;
        while(lo<=hi) {
            int mid=(lo+hi)/2;
            if(count(nums, mid) >= medianPos) {
                ans=mid;
                lo=mid+1;
            } else {
                hi=mid-1;
            }
        }
        return ans;
    }
    private long count(int[] nums, int k) {
        Map<Integer,Integer> freq = new HashMap<>();
        int l=0, cnt=0;
        long res=0;
        for(int r=0;r<nums.length;++r) {
            freq.put(nums[r], freq.getOrDefault(nums[r],0)+1);
            if(freq.get(nums[r])==1) ++cnt;
            while(cnt>k) {
                freq.put(nums[l], freq.get(nums[l])-1);
                if(freq.get(nums[l])==0) --cnt;
                l++;
            }
            res += r-l+1;
        }
        return res;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

class Solution {
    fun medianOfUniquenessArray(nums: IntArray): Int {
        val n = nums.size
        val total = n.toLong()*(n+1)/2
        val medianPos = (total+1)/2
        fun count(k: Int): Long {
            val freq = mutableMapOf<Int,Int>()
            var l=0; var cnt=0L; var res=0L
            for(r in nums.indices) {
                freq[nums[r]] = (freq[nums[r]]?:0)+1
                if(freq[nums[r]]==1) cnt++
                while(cnt>k.toLong()) {
                    freq[nums[l]] = freq[nums[l]]!!-1
                    if(freq[nums[l]]==0) cnt--
                    l++
                }
                res += r-l+1
            }
            return res
        }
        var lo=1; var hi=n; var ans=1
        while(lo<=hi) {
            val mid=(lo+hi)/2
            if(count(mid)>=medianPos) {
                ans=mid
                lo=mid+1
            } else {
                hi=mid-1
            }
        }
        return ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

class Solution:
    def medianOfUniquenessArray(self, nums: list[int]) -> int:
        n = len(nums)
        total = n*(n+1)//2
        median_pos = (total+1)//2
        def count(k: int) -> int:
            freq = {}
            l = cnt = res = 0
            for r, v in enumerate(nums):
                freq[v] = freq.get(v,0)+1
                if freq[v]==1:
                    cnt += 1
                while cnt > k:
                    freq[nums[l]] -= 1
                    if freq[nums[l]]==0:
                        cnt -= 1
                    l += 1
                res += r-l+1
            return res
        lo, hi, ans = 1, n, 1
        while lo <= hi:
            mid = (lo+hi)//2
            if count(mid) >= median_pos:
                ans = mid
                lo = mid+1
            else:
                hi = mid-1
        return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

impl Solution {
    pub fn median_of_uniqueness_array(nums: Vec<i32>) -> i32 {
        let n = nums.len();
        let total = n*(n+1)/2;
        let median_pos = (total+1)/2;
        let count = |k: i32| -> i32 {
            use std::collections::HashMap;
            let mut freq = HashMap::new();
            let (mut l, mut cnt, mut res) = (0, 0, 0);
            for (r, &v) in nums.iter().enumerate() {
                *freq.entry(v).or_insert(0) += 1;
                if freq[&v]==1 { cnt += 1; }
                while cnt > k {
                    let x = nums[l];
                    *freq.get_mut(&x).unwrap() -= 1;
                    if freq[&x]==0 { cnt -= 1; }
                    l += 1;
                }
                res += (r-l+1) as i32;
            }
            res
        };
        let (mut lo, mut hi, mut ans) = (1, n as i32, 1);
        while lo <= hi {
            let mid = (lo+hi)/2;
            if count(mid) >= median_pos as i32 {
                ans = mid;
                lo = mid+1;
            } else {
                hi = mid-1;
            }
        }
        ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

class Solution {
    medianOfUniquenessArray(nums: number[]): number {
        const n = nums.length;
        const total = n*(n+1)>>1;
        const medianPos = (total+1)>>1;
        function count(k: number): number {
            const freq = new Map<number,number>();
            let l=0, cnt=0, res=0;
            for(let r=0;r<n;++r) {
                freq.set(nums[r], (freq.get(nums[r])||0)+1);
                if(freq.get(nums[r])===1) ++cnt;
                while(cnt>k) {
                    freq.set(nums[l], freq.get(nums[l])-1);
                    if(freq.get(nums[l])===0) --cnt;
                    ++l;
                }
                res += r-l+1;
            }
            return res;
        }
        let lo=1, hi=n, ans=1;
        while(lo<=hi) {
            const mid=(lo+hi)>>1;
            if(count(mid)>=medianPos) {
                ans=mid;
                lo=mid+1;
            } else {
                hi=mid-1;
            }
        }
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(n^2 log n), since for each binary search step, we use a sliding window to count subarrays.
  • 🧺 Space complexity: O(n), for the frequency map