DSA From Codeforces Blog | Dataford Interview Questions

QuickBooks receives transactions in chronological order, represented by integer category IDs. Given the category sequence and a limit k, find the length of the longest contiguous range containing at most k distinct categories.

A range must contain at least one transaction. Return 0 only when the input sequence is empty or k is zero.

Formal Specification

Implement longest_category_window(categories, k).

Input: categories, an array of integers, and k, a non-negative integer.
Output: An integer representing the maximum length of a contiguous subarray with at most k distinct values.

Constraints

0 <= len(categories) <= 10^5
0 <= k <= len(categories)
-10^9 <= categories[i] <= 10^9
A valid range must be contiguous
The target complexity is O(n) time

Function Signature

def longest_category_window(categories, k):

Your question is DSA From Codeforces Blog. Start with the requirements in the Question tab.

Run and submit as often as you like. When you're ready, talk me through your approach or go straight to the code.

Problem