Start learning free

LESSON 245 OF 348 · HASH TABLE

Longest Subarray With At Most K Distinct Integers in Kotlin: 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

    KOTLIN · HASH TABLE

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

    Problem overview

    The function longestSubarray receives an IntArray called nums and an integer K. It returns the length of the longest subarray, a run of neighbouring elements, that contains at most K different values. Repeated values are fine: it is the number of distinct values that is limited, not the length.

    In the example, nums = [1, 2, 1, 2, 3] and K = 2. The first four elements, [1, 2, 1, 2], contain only the values 1 and 2, so they qualify. Adding the 3 would make three distinct values, which is too many. The answer is 4.

    The statement allows O(n²) time and asks for O(n) extra space.

    Approach: for every start, grow the end until the limit is broken

    A subarray is determined by its first and last index. The plan is to try every first index i, and for each one extend the last index j one element at a time, tracking the distinct values of nums[i..j] in a HashSet. A set ignores values it already has, so its size is exactly the number of distinct values so far.

    While that size is at most K, the subarray is valid and its length, j - i + 1, is a candidate for the answer. Once the size goes above K, the loop for this i can stop. Extending a subarray never removes a value, so the number of distinct values can only stay the same or grow. Every longer subarray starting at i is therefore invalid too.

    On the example with K = 2: starting at index 0, the sets are {1}, {1, 2}, {1, 2}, {1, 2}, and then {1, 2, 3} breaks the limit. The valid lengths were 1, 2, 3 and 4. Starting at index 1 reaches length 3 at best, and so on, so the overall maximum is 4.

    Two nested loops over n elements make this O(n²). A sliding window can reach O(n), but that is a topic for a later lesson. The set is what keeps the quadratic version from becoming cubic, because counting distinct values by rescanning the subarray would cost another factor of n.

    Step by step

    1. Start the answer at 0. answer is a var, since it grows as better subarrays turn up. It holds the longest valid length found so far.
    2. Choose the start. The outer loop, for (i in nums.indices), tries every index as the first element.
    3. Create a fresh set. distinctValues is a val declared inside that loop, so each start begins with an empty set. The variable is fixed, while the set's contents change.
    4. Choose the end. The inner loop runs j over i until nums.size. The subarray grows by one element per iteration.
    5. Add the new element. distinctValues.add(nums[j]) updates the set. If the value was already there, the set doesn't change.
    6. Break on too many values. If distinctValues.size > K, break leaves the inner loop, because no longer subarray from this start can be valid.
    7. Record the length. Below the check, the subarray is valid, so answer becomes maxOf(answer, j - i + 1).
    8. Return answer after the outer loop.

    The solution in Kotlin

    class Solution {
    fun longestSubarray(nums: IntArray, K: Int): Int {
        var answer = 0
        for (i in nums.indices) {
            val distinctValues = HashSet<Int>()
            for (j in i until nums.size) {
                distinctValues.add(nums[j])
                if (distinctValues.size > K) {
                    break
                }
                answer = maxOf(answer, j - i + 1)
            }
        }
        return answer
    }
}

    Kotlin details:

    • The parameter is named K in capitals. Kotlin allows that, and the name must match exactly, since k would be a different identifier.
    • The order matters: add first, then check the size. The element has to be in the set before you can know whether it pushed the count over K.
    • distinctValues.size is a property, written without parentheses. Don't confuse it with nums.size, which is the array's length.
    • break leaves only the inner loop. The outer loop carries on with the next start.

    Complexity

    Time is O(n²): there are up to n starts, each with an inner loop of up to n steps, and every step does constant-time work on average. Space is O(n), but in this solution the set never holds more than K + 1 values, because the loop breaks as soon as the size passes K. The bound can never exceed n either, since the set holds at most one entry per element.

    Edge cases and common mistakes

    • K = 0. Adding any element makes the size 1, which is above 0, so the loop breaks before recording anything. The answer is 0. For [1, 2, 3] with K = 0 the function returns 0.
    • Empty array. No loop runs and the answer is 0.
    • K at least the number of distinct values. The whole array qualifies, and the answer is nums.size.
    • Checking the size after recording the length. That counts an invalid subarray as valid. The check must come first.
    • Counting elements instead of distinct values. A subarray like [1, 1, 1, 1] has one distinct value, however long it is.
    • Reusing the set across starts. A set declared outside the outer loop would keep values from earlier subarrays.

    Testing

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