Best k-window with all-distinct elements

Question

Given an array nums and a length k, find the maximum sum over all windows of exactly k consecutive elements whose elements are all distinct. If no such window exists, return 0. Aim for O(n).

Accepted Answer

Slide a fixed-size window while maintaining two things incrementally: the running sum, and a frequency map of the elements currently inside. The window's elements are all distinct exactly when the map holds k different keys. On each slide, add the entering element and drop the leaving one from both the sum and the map (deleting a key when its count hits zero), then check the size condition. Trace k = 3: [1,5,4] sum 10 distinct, [5,4,2] sum 11 distinct, [4,2,9] sum 15 distinct, then [2,9,9] and [9,9,9] have repeats and are skipped. Answer 15. Time O(n) (each element enters and leaves the map o…

Best k-window with all-distinct elements

Your answer

More Coding questions