Start learning free

LESSON 241 OF 338 · HASH TABLE

Longest Subarray With At Most K Distinct Integers in Go: O(n²)

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

    GO · HASH TABLE

    Longest Subarray With At Most K Distinct Integers in Go, explained

    Problem overview

    The function longestSubarray receives a slice of integers, nums, and a limit k. It returns the length of the longest contiguous piece of nums that contains at most k different values. Repeats don't count twice: [1, 2, 1, 2] has only two distinct values even though it has four elements.

    For nums = [1, 2, 1, 2, 3] and k = 2, the piece nums[0..3] = [1, 2, 1, 2] has two distinct values and length 4. Adding the 3 would make three distinct values, so the answer is 4.

    The statement allows O(n²) time and O(n) extra space, which is enough for a direct approach with no clever window tricks.

    Approach: try every start, extend until the limit is broken

    Every subarray is determined by where it starts and where it ends. The lesson fixes the start i and then moves the end j to the right one element at a time, keeping the set of distinct values seen in nums[i..j].

    The key observation is that growing a subarray can never reduce its number of distinct values. As soon as the set grows beyond k elements, every longer subarray with the same start is also invalid, so the inner loop can stop. Then the next start begins from scratch with an empty set.

    That is two nested loops over at most n positions each, hence O(n²). Faster solutions exist that slide a window and never restart, but this lesson keeps the logic simple: for each start, find the longest valid end.

    Take nums = [1, 2, 1, 2, 3] and k = 2. Starting at index 0, the set grows to {1}, {1, 2}, stays {1, 2} twice, and reaches three values at index 4, so the best length from this start is 4. Starting at index 1 gives [2, 1, 2], length 3. Starting at index 2 gives [1, 2], length 2, and so on. The maximum is 4.

    Step by step

    1. Create answer. It starts at 0, which is also the right result for an empty slice.
    2. Loop over every start index i. Each index is tried as the left end of a subarray.
    3. Create a fresh set for this start. Declaring it inside the outer loop gives every start an empty one. Go has no set type, so the lesson uses a map[int]struct{}: only the keys matter.
    4. Loop over the end index j, beginning at i, so the subarray starts with a single element and grows.
    5. Add nums[j] to the set. Storing a key that is already present changes nothing, so len of the map is always the number of distinct values.
    6. Stop when the set is too large. If len(distinctValues) > k, break leaves only the inner loop; the outer loop moves on to the next start.
    7. Record the length. Reaching this line means nums[i..j] is valid, and its length is j - i + 1. Keep the larger of that and answer.
    8. Return answer after both loops are done.

    The solution in Go

    func longestSubarray(nums []int, k int) int {
    answer := 0
    for i := 0; i < len(nums); i++ {
        distinctValues := make(map[int]struct{})
        for j := i; j < len(nums); j++ {
            distinctValues[nums[j]] = struct{}{}
            if len(distinctValues) > k {
                break
            }
            answer = max(answer, j-i+1)
        }
    }
    return answer
}

    Go details in this code

    • map[int]struct{} as a set. The empty struct struct{} occupies no memory, and struct{}{} is its only value. Because the value carries no information, the map answers one question: is this key present?
    • Assigning an existing key is harmless. It overwrites the same empty value, so duplicates never inflate len.
    • max is a built-in. Since Go 1.21 you don't need to write your own helper or import anything for max and min on ordered types.
    • break only leaves the innermost for. That is exactly what the lesson wants here.
    • No while. Both loops are the three-part for form.

    Complexity

    Time: O(n²). For each of the n starts, the inner loop runs at most n - i times, and each map insertion and len call takes constant time on average. The total number of steps is at most about n²/2.

    Space: O(n). The map holds at most k + 1 distinct values before the break, and never more than n. A new map is created for every start, but the old one becomes garbage, so only one is alive at a time.

    Edge cases and common mistakes

    • Empty slice. Neither loop runs and the function returns 0.
    • k = 0. The first inserted value already makes the set size 1, which is more than 0, so every inner loop breaks immediately and the answer is 0. With nums = [5, 5, 5] and k = 0 the result is 0.
    • All values equal. The set never grows beyond one value, so for any k >= 1 the answer is len(nums).
    • Reusing one map for all starts. If the map is declared before the outer loop, values from earlier starts stay in it and the counts come out too high. The map must be created inside the outer loop.
    • Updating answer before the check. The length is recorded only after the if; otherwise an invalid subarray could be counted.
    • Counting elements instead of distinct values. Comparing the subarray length to k is wrong: [1, 2, 1, 2] has length 4 but only two distinct values.

    Testing

    • nums = [1, 2, 1, 2, 3], k = 2 gives 4.
    • nums = [1, 2, 3], k = 1 gives 1.
    • nums = [], k = 2 gives 0.
    Keep going with GoAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free