Day 95 of 100 days dsa coding challenge

Taking on a new challenge: solving GeeksforGeeks POTD daily and sharing my solutions! 💻🔥
The goal: sharpen problem-solving skills, level up coding, and learn something new every day. Follow my journey! 🚀

100DaysOfCode #CodingChallenge #ProblemSolving #GeeksforGeeks #DeveloperJourney

Problem:

https://www.geeksforgeeks.org/problems/count-distinct-elements-in-every-window/1

Count distinct elements in every window

Difficulty: Medium Accuracy: 41.83%

Given an integer array arr[] and a number k. Find the count of distinct elements in every window of size k in the array.

Examples:
Input: arr[] = [1, 2, 1, 3, 4, 2, 3], k = 4
Output: [3, 4, 4, 3]
Explanation:
First window is [1, 2, 1, 3], count of distinct numbers is 3.
Second window is [2, 1, 3, 4] count of distinct numbers is 4.
Third window is [1, 3, 4, 2] count of distinct numbers is 4.
Fourth window is [3, 4, 2, 3] count of distinct numbers is 3.
Input: arr[] = [4, 1, 1], k = 2
Output: [2, 1]
Explanation:
First window is [4, 1], count of distinct numbers is 2.
Second window is [1, 1], count of distinct numbers is 1.
Input: arr[] = [1, 1, 1, 1, 1], k = 3
Output: [1, 1, 1]
Explanation: Every window of size 3 in the array [1, 1, 1, 1, 1], contains only the element 1, so the number of distinct elements in each window is 1.
Constraints:
1 ≤ k ≤ arr.size() ≤ 105
1 ≤ arr[i] ≤ 105

Solution:
class Solution:
def countDistinct(self, arr, k):
from collections import defaultdict
freq = defaultdict(int)
res = []
n = len(arr)
for i in range(k):
freq[arr[i]] += 1
res.append(len(freq))
for i in range(k, n):
freq[arr[i-k]] -= 1
if freq[arr[i-k]] == 0:
del freq[arr[i-k]]
freq[arr[i]] += 1
res.append(len(freq))
return res