3 Problem 3 (25 points) Consider the following problem, where we are given an array A with some duplicate elements, and want to find the number of distinct elements in each interval of size k. Input: a positive integer k, and an unsorted A with n numbers, some of them repeating. Output: an array B of length n-k+1, where B[i] should contain the number of distinct elements in the interval A[i], A[i+1),..., A[i+k 1). EXAMPLE: if A = 3,2 7,3,5,3,5,7,2 and k = 4 then we are looking at intervals of size k = 4, so B[1] = 3 because the subarray (3,2,7,3] has 3 distinct elements; B[2] = 4 because the subarray (2,7,3,5] has four distinct elements. More generally, the output array B = 3,4,3,2,3,4 The question: Write pseudocode for an algorithm for this problem with expected running time O(n). Note that your expected running time should be O(n) even if k is large. A run-time of O(nk) is too slow, and will receive very little credit. HINT: similar to the algorithm for sorting a k-sorted array, you will want to take advantage of the fact that two consecutive intervals A[i]...A[i+k] and A[i+1]...A[i+k+ 1] only differ by a small number of elements