Sliding Window or Multi-Pointer Optimization

MediumPython00:00

Practice interviewer

In session

5 left

00:00

Your question is Sliding Window or Multi-Pointer Optimization. Start with the requirements on the right.

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

You need to log in / sign up to run or submit.

Problem

Meta IT receives a chronological stream of support event categories from its internal service tooling. Given the category for each event, find the length of the longest contiguous window containing at most k distinct categories.

Use a sliding window or multi-pointer approach that runs in O(n) time.

Formal Specification

Implement longest_support_window(events, k).

Input: events, a list of integers where each integer identifies an event category, and k, a non-negative integer.
Output: An integer representing the maximum length of a contiguous subarray containing at most k distinct values.
If k is 0, return 0.

Constraints

0 <= events.length <= 100000
0 <= k <= events.length
0 <= events[i] <= 10^9
The returned window must be contiguous
The input order must not be changed

Function Signature

def longest_support_window(events, k):

Your solutionPython 3

You need to log in / sign up to run or submit.

Run your code to see test output