Start learning free

LESSON 244 OF 347 · HASH TABLE

Longest Subarray With At Most K Distinct Integers in C#

Practice O(n2) Read the full explanation

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 8
    Ctrl + Enter to check

    C# · HASH TABLE

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

    Problem overview

    The method LongestSubarray receives an int[] nums and an integer K. It returns the length of the longest subarray, a block of consecutive elements, that contains at most K different values. Repeated values inside the block count once.

    For nums = [1, 2, 1, 2, 3] and K = 2 the answer is 4. The block [1, 2, 1, 2], which is nums[0..3], has two distinct values, 1 and 2. Adding the 3 would make three, so the length cannot reach 5.

    The lesson allows O(n²) time and O(n) extra space. A sliding-window solution can do better, but this lesson uses the straightforward double loop.

    Approach: for each start, extend while the set stays small

    Pick a start index i. Extend the subarray to the right one element at a time, with end index j, and track which distinct values it contains. As long as the number of distinct values is at most K, the subarray is valid and its length j - i + 1 may be the best so far. As soon as the count exceeds K, stop: adding more elements can only keep the count the same or raise it, so no longer subarray from this start can be valid.

    A HashSet<int> tracks the distinct values. Adding a value that is already in the set changes nothing, so the set's Count is exactly the number of distinct values in nums[i..j]. Each pair (i, j) costs one set operation, and there are about n²/2 pairs, hence O(n²).

    This also resembles the "no repeating integers" problem. That one requires every value in the subarray to be different; here up to K different values are allowed, each as often as it likes. The break rule is the same: once a subarray is invalid, extending it never repairs it.

    Step by step

    1. Create answer, an int starting at 0. It holds the longest valid length found so far.
    2. Loop i from 0 while i < nums.Length. Each index is tried as the start of a subarray.
    3. Create distinctValues, an empty HashSet<int>, inside that loop. A new set per start means each start begins with no values.
    4. Loop j from i while j < nums.Length. The index j is the end of the subarray, which grows by one element per iteration.
    5. Add nums[j] to the set. Duplicates are ignored, so the set now describes nums[i..j].
    6. If distinctValues.Count > K, break. The subarray has too many distinct values, and so would every longer one from this start.
    7. Update the answer. Reaching this line means the subarray is valid, so answer = Math.Max(answer, j - i + 1).
    8. Return answer after the outer loop.

    The solution in C#

    class Solution {
    public int LongestSubarray(int[] nums, int K) {
        int answer = 0;
        for (int i = 0; i < nums.Length; i++) {
            HashSet<int> distinctValues = new HashSet<int>();
            for (int j = i; j < nums.Length; j++) {
                distinctValues.Add(nums[j]);
                if (distinctValues.Count > K) {
                    break;
                }
                answer = Math.Max(answer, j - i + 1);
            }
        }
        return answer;
    }
}

    Tracing the example with K = 2: starting at i = 0, the set grows to {1}, {1, 2} and stays {1, 2} for the next two elements, so the length reaches 4. The element 3 makes the set size 3, which is more than K, so the inner loop breaks before the length is recorded. Starting at i = 1 gives [2, 1, 2] with length 3, and the later starts are shorter still.

    C# details:

    • The order of the lines matters. The element is added before the size is checked, and the answer is updated only after the check passes. If the update came first, an invalid subarray could be counted.
    • Count, not Length. A HashSet<T> reports its size with the Count property. Length belongs to arrays and strings.
    • The parameter name. The lesson's parameter is the capital K. C# is case-sensitive, so a lowercase k would be a different, undeclared name.
    • Usings. HashSet<T> needs System.Collections.Generic, and Math.Max lives in System.

    Complexity

    Time: O(n²). In the worst case, for example when K is at least the number of distinct values in the array, no inner loop breaks, and the loops run roughly n(n+1)/2 times in total. Each iteration does constant-time work on average.

    Space: O(n). The set holds at most the distinct values of one subarray, so at most n values. Only one set is alive at a time.

    Edge cases and common mistakes

    • Empty array. The loops never run, so the result is 0.
    • K = 0. Every single element already makes the set size 1, which is more than 0, so the inner loop breaks at once and the answer is 0.
    • K at least as large as the number of distinct values. The whole array is valid, and the answer is nums.Length.
    • One value repeated. [4, 4, 4] with K = 1 gives 3, because repeats do not add to the distinct count.
    • Counting elements instead of distinct values. The limit is on how many different values are in the subarray, not on its length.
    • Reusing one set across starts. Declared outside the outer loop, the set would keep values from earlier starts and the counts would be wrong.

    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.
    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