LESSON 288 OF 347 · SLIDING WINDOW

Longest Subarray With At Most K Distinct Integers in C#: Sliding Window

Given an array of integers, find the longest subarray that contains at most K distinct integers and return its length.

Example

Input: nums = [1, 2, 1, 2, 3], k = 2
Output: 4
Explanation:the subarray nums[0...3] contains 2 distinct values: [1, 2] and is the longest subarray

Note:

Your algorithm should run in O(n^2) time and use O(n) extra space.

STEP 1 OF 13

Guided

Ctrl + Enter to check

C# · SLIDING WINDOW

Longest Subarray With At Most K Distinct Integers in C#, explained

Problem overview

LongestSubarray(nums, K) receives an array of integers and a number K. It must return the length of the longest contiguous subarray that contains at most K different values. Repeats of a value count once: [1, 2, 1, 2] has two distinct values although it has four elements.

In the example, nums = [1, 2, 1, 2, 3] and K = 2. The subarray nums[0..3], that is [1, 2, 1, 2], has two distinct values and length 4. Adding the 3 would make three, so the answer is 4.

The note allows O(n²) time and O(n) extra space. The solution here does better on time: it runs in O(n).

Approach: grow on the right, shrink on the left

A straightforward solution tries every start and extends it to the right until a (K+1)-th distinct value appears. That is the quadratic budget the note allows. The sliding window avoids the repeated work.

Keep a window nums[first..last]. For each new last, add nums[last] to the window. If the window now holds more than K distinct values, remove elements from the left until it is valid again. Then the window is the longest valid subarray ending at last, and its length is a candidate for the answer.

The question "how many distinct values are in the window?" needs a data structure that can add and remove single elements. A Dictionary<int, int> mapping each value to its count in the window does that. A value is distinct while its count is above zero, so the number of keys equals the number of distinct values. The one rule to remember: when a count drops to 0, delete the key, or the dictionary's size would count a value that is no longer in the window.

Step by step

Create the count map. freq maps each value in the current window to its number of occurrences.
Declare answer and first. Both are ints starting at 0: the best length so far and the window's left edge.
Loop over last from 0 to nums.Length - 1. It is the right edge, so this tries every index as the end of a subarray.
Add the new element with an Insert(freq, nums[last]) helper that is written at the end.
Repair the window. While freq.Count > K the window has too many distinct values. For a dictionary, the size is the Count property.
Drop the leftmost element. Inside that while loop, call Remove(freq, nums[first]) and then increment first. Several removals may be needed before a value disappears completely, which is why this is a loop and not an if.
Record the length. The window is valid now, so answer = Math.Max(answer, last - first + 1).
Return answer after the loop. Each index enters the window once and leaves at most once, so the whole loop is linear.
Write Remove. It takes the dictionary and a value, and returns void. A dictionary is a reference type, so the changes are visible to the caller.
Decrement the count with freq[val]--. The indexer throws for a missing key, but Remove is only called for values that are in the window.
Delete the key at zero with the dictionary's own freq.Remove(val), so freq.Count stays equal to the number of distinct values.
Write Insert. A value not in the dictionary yet has no key, so read its count with freq.GetValueOrDefault(val, 0), add 1, and store it through the indexer. Assigning through the indexer adds the key if it is missing and overwrites it otherwise.

The solution in C#

class Solution {
    public void Insert(Dictionary<int, int> freq, int val) {
        freq[val] = freq.GetValueOrDefault(val, 0) + 1;
    }

    public void Remove(Dictionary<int, int> freq, int val) {
        freq[val]--;
        if (freq[val] == 0) {
            freq.Remove(val);
        }
    }

    public int LongestSubarray(int[] nums, int K) {
        Dictionary<int, int> freq = new Dictionary<int, int>();
        int answer = 0, first = 0;
        for (int last = 0; last < nums.Length; last++) {
            Insert(freq, nums[last]);
            while (freq.Count > K) {
                Remove(freq, nums[first]);
                first++;
            }
            answer = Math.Max(answer, last - first + 1);
        }
        return answer;
    }
}

Some C# details are worth a closer look:

Two different Remove methods. The lesson's own Remove(freq, val) lowers a count. Inside it, freq.Remove(val) is the dictionary's built-in method that deletes a key. They have the same name but belong to different types, so they don't conflict.
Reading a missing key throws. freq[val] on a key that isn't there raises a KeyNotFoundException. That is why Insert uses GetValueOrDefault, which returns the fallback value 0 for a missing key and never throws.
freq[val]-- is a read and a write. It reads the count, subtracts one and stores the result back under the same key.
Count, not Length. A Dictionary reports its number of keys through Count. Length belongs to arrays.
Namespace. Dictionary is in System.Collections.Generic, and Math is in System.

Tracing the example

With [1, 2, 1, 2, 3] and K = 2, the window grows over 1, 2, 1 and 2 with counts {1: 2, 2: 2} and two distinct values at every step, so the answer reaches 4. When last reaches the 3, the map has three keys. The loop removes the first 1 (count 2 to 1), then the first 2 (count 2 to 1), and then the second 1, whose count reaches 0 and whose key is deleted. Now the map has the keys 2 and 3, the window is [2, 3] with length 2, and the answer stays at 4.

Complexity

Time: O(n). The inner while loop looks like a second loop over the array, but first never moves backward. Over the whole run, last moves n times and first moves at most n times. Each dictionary operation takes constant time on average. This is better than the O(n²) the note allows.

Space: O(n). In the worst case, the window holds up to min(n, K + 1) distinct keys at once, so the dictionary stays that small. When K is a constant, the extra space is effectively O(1), but the note's O(n) bound covers any K.

Edge cases and common mistakes

Empty array. The loop never runs and the answer is 0.
K = 0. No value is allowed, so every window is repaired down to empty and the answer is 0. For [1, 2, 3] with K = 0 the result is 0.
K at least as large as the number of distinct values. The inner loop never runs, and the answer is nums.Length. With [1, 2, 3, 4] and K = 10 the answer is 4.
All values equal. [4, 4, 4] with K = 1 gives 3. The dictionary keeps one key whose count grows.
Not deleting zero-count keys. If Remove leaves a key with count 0, freq.Count overstates the distinct values and the window shrinks too much.
Using if instead of while for the repair. Removing one element may not remove any distinct value, because the same value can appear again inside the window.
Reading the length before repairing. The length is recorded only after the window is valid again.
Using freq[val]++ in Insert. It throws for a value that has no key yet.

Testing

nums = [1, 2, 1, 2, 3], K = 2 gives 4.
nums = [1, 2, 3], K = 0 gives 0.
nums = [4, 4, 4], K = 1 gives 3.
nums = [1, 2, 3, 4], K = 10 gives 4.
nums = [], K = 2 gives 0.

Keep going with C#About 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.

Start learning free