Exactly K Distinct Contaminants - Adobe Hackathon 2026

Problem Preview

"The Environmental Protection Agency (EPA) receives daily sensor readings along a river. Each reading is an integer: 1 ... 10^5 represents a specific contaminant type. 0 represents a missing/unreadable measurement. The EPA wants to identify continuous sequences of days containing exactly k distinct contaminants. A 0 reading is a wildcard/missing value and does not count as a distinct contaminant. Given an array of n readings, return the total number of contiguous subarrays containing exactly k distinct non-zero values. Input Format First line: n k Second line: nums[0] nums[1] ... nums[n-1] Constraints 1 ≤ n ≤ 2 × 10^4 0 ≤ nums[i] ≤ 10^5 1 ≤ k ≤ n 0 does not contribute to the distinct-contaminant count. Output Format Print one integer: number of contiguous subarrays containing exactly k distinct non-zero values Test Case 1 6 2 3 0 1 2 1 0 Answer: 9 Some valid windows include: [3,0,1] [3,0,1,2] [0,1,2] [1,2] [1,2,1] [2,1,0] ... All have exactly 2 distinct non-zero values. Test Case 2 5 1 0 4 0 4 0 Every non-empty subarray containing 4 has exactly one distinct contaminant. Number of valid subarrays: 12 Output: 12"