Count Distinct Elements in Every Window || Program 57 || Competitive Coding || Learning Monkey ||
Count Distinct Elements in Every Window
In this class, We discuss Count Distinct Elements in Every Window.
Readers can prepare an entire competitive coding course to crack product development companies. Click Here.
The reader should have basic coding skills to work with competitive coding. Click here.
Question:
Given an array of N elements and a window size K.
Our task is to find the distinct element count in each window.
Example:
N = 7 and K = 4
A = [1, 2, 1, 3, 4, 2, 3]
Output: [3, 4, 4, 3]
The first window is [1, 2, 1, 3].
The distinct elements in the window are 3.
Similarly, the remaining windows count.
Time complexity: O(N)
Space Complexity: O(N)
Logic:
We use a hash table to maintain the distinct elements.
The step-by-step explanation is provided in the video.
Code:
from collections import defaultdict
class Solution:
def countDistinct(self, A, N, K):
mp = defaultdict(lambda: 0)
lis=[]
dist_count = 0
for i in range(K):
if mp[A[i]] == 0:
dist_count += 1
mp[A[i]] += 1
lis.append(dist_count)
for i in range(K, N):
if mp[A[i - K]] == 1:
dist_count -= 1
mp[A[i - K]] -= 1
if mp[A[i]] == 0:
dist_count += 1
mp[A[i]] += 1
lis.append(dist_count)
return lis
A=[1,2,1,3,4,2,3]
ob=Solution()
z=ob.countDistinct(A,7,4)
Link for playlists:
/ @wisdomerscse
Link for our website: https://learningmonkey.in
Follow us on Facebook @ / learningmonkey
Follow us on Instagram @ / learningmonkey1
Follow us on Twitter @ / _learningmonkey
Mail us @ learningmonkey01@gmail.com
On this page of the site you can watch the video online Count Distinct Elements in Every Window || Program 57 || Competitive Coding || Learning Monkey || with a duration of hours minute second in good quality, which was uploaded by the user Wisdomers - Computer Science and Engineering 25 May 2023, share the link with friends and acquaintances, this video has already been watched 692 times on youtube and it was liked by 10 viewers. Enjoy your viewing!
