[NEW] Add solution for Distinct Values Subarrays II

[Insha-7]

🎯 Problem Information

• Problem Name: Distinct Values Subarrays II
• CSES Link: https://cses.fi/problemset/task/2428
• Category: 2_sorting_searching
• Estimated Difficulty: Medium

📋 Problem Description

You are given an array of n integers and a number k.
Your task is to count the number of subarrays that contain at most k distinct values.

💡 Proposed Approach

We can use a two-pointer (sliding window) approach with a frequency map:

• Maintain a window [l, r] such that it contains at most k distinct elements.

• Expand r and keep track of frequencies of each element.

• When the window exceeds k distinct values, move l forward until it becomes valid again.

• For each r, the number of valid subarrays ending at r is (r - l + 1).

• Time Complexity: O(n)

• Space Complexity: O(n)

📝 Implementation Notes

Any special considerations or optimizations needed:

• Requires fast I/O
• Needs modular arithmetic
• Large input constraints
• Edge cases to consider:
  • All elements identical
  • All elements distinct
  • k = 1
  • k = n

🏷️ Labels

Please add appropriate labels:

• hacktoberfest
• good first issue
• help wanted

👤 Assignee

• I would like to work on this issue
• I'm available for guidance/review

📎 Additional Context

[Anasahmad83400]

def count_subarrays_with_at_most_k_distinct(arr, k):
from collections import defaultdict
n = len(arr)
freq = defaultdict(int)
l = 0
total = 0
distinct = 0

for r in range(n):
    if freq[arr[r]] == 0:
        distinct += 1
    freq[arr[r]] += 1

    while distinct > k:
        freq[arr[l]] -= 1
        if freq[arr[l]] == 0:
            distinct -= 1
        l += 1

    total += (r - l + 1)
return total

Example usage:

arr = [1, 2, 1, 3, 4]
k = 2
print(count_subarrays_with_at_most_k_distinct(arr, k)) # Output: number of valid subarrays

[ks-iitjmu]

@Insha-7 Assigned