Start learning free

LESSON 269 OF 415 · HASH TABLE

Longest Subarray With At Most K Distinct Integers in Swift

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 at most O(n2) time and use O(n) extra space.


STEP 1 OF 8
    Ctrl + Enter to check

    SWIFT · HASH TABLE

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

    Problem overview

    The method longestSubarray receives an array of integers, nums, and a limit K. It must return the length of the longest subarray, a run of neighbouring elements, that contains at most K different values.

    For nums = [1, 2, 1, 2, 3] and K = 2, the subarray [1, 2, 1, 2] (indices 0 to 3) holds only the values 1 and 2, so its length 4 is valid. Adding the 3 would make three distinct values, so the answer is 4.

    The lesson's budget is O(n²) time and O(n) extra space.

    Approach: try every start, grow until too many values

    A subarray is determined by where it starts, i, and where it ends, j. The plan is to try every start. From each start, extend the end one element at a time while keeping a set of the values inside. The set's size is exactly the number of distinct values.

    Once the set has more than K values, stop extending from this start. Adding more elements can keep the number of distinct values the same or raise it, never lower it, so no longer subarray from this i can be valid. Recomputing the distinct count of each subarray from scratch would cost another pass each time; maintaining the set as j advances makes each step constant time on average. Two nested loops then give O(n²).

    Step by step

    1. Keep the best length. answer is a var starting at 0.
    2. Choose each start with for i in 0..<nums.count.
    3. Create a fresh set. distinctValues is an empty Set<Int>() declared inside the outer loop, so each start begins with nothing. It is a var because inserting changes it.
    4. Choose each end with for j in i..<nums.count. The subarray nums[i...j] grows by one element per iteration.
    5. Add nums[j] to the set. A set ignores values it already has, so its count is the number of distinct values in nums[i...j].
    6. Stop when there are too many. If distinctValues.count > K, break out of the inner loop.
    7. Record the length. Otherwise the subarray is valid, so update answer with max(answer, j - i + 1).
    8. Return answer after the outer loop.

    Tracing the example

    For [1, 2, 1, 2, 3] with K = 2, start i = 0 inserts 1, 2, 1 and 2 in turn. The set stays at size 2 (it holds 1 and 2), so answer climbs to 4. Inserting 3 makes the size 3, which is more than K, so the inner loop breaks. Start i = 1 sees 2, 1, 2 and then 3, giving a valid length of 3 before the break. Later starts have even fewer elements, so the final answer is 4.

    The solution in Swift

    class Solution {
    func longestSubarray(_ nums: [Int], _ K: Int) -> Int {
        var answer = 0
        for i in 0..<nums.count {
            var distinctValues = Set<Int>()
            for j in i..<nums.count {
                distinctValues.insert(nums[j])
                if distinctValues.count > K {
                    break
                }
                answer = max(answer, j - i + 1)
            }
        }
        return answer
    }
}

    Swift details worth a closer look:

    • Insert first, then test. Here the order is the opposite of the "no repeats" version of this idea. The new value must be in the set before its size is compared with K, because the question is how many distinct values the subarray would have.
    • Parameter label. _ nums and _ K mean the arguments are passed without labels: longestSubarray([1, 2, 1, 2, 3], 2).
    • Half-open ranges. 0..<nums.count stops before nums.count. For an empty array the loop doesn't run and the result stays 0.
    • break exits only the inner loop.
    • Sets are values. A var declared inside the outer loop is a brand-new set each time round.

    Complexity

    Time: O(n²). There are n starts and each inner loop runs at most n times, with constant average cost per set operation.

    Space: O(n). The set never holds more than K + 1 values before the loop breaks, and never more than n.

    Neighbouring starts repeat much of each other's work, because the set is rebuilt from nothing every time. A sliding window that keeps one set of counts and moves its left edge only when needed avoids that and reaches O(n). This lesson uses the simpler nested loops.

    Edge cases and common mistakes

    • Empty array. Returns 0, because the outer loop has no starts to try.
    • Distinct is not the same as length. The limit counts different values, not elements, so [1, 1, 1, 1, 2] with K = 2 is valid as a whole and returns 5.
    • K = 0. The first inserted value already makes the count 1, which is more than 0, so every start breaks at once and the result is 0. For [1, 2, 3] with K = 0 the answer is 0.
    • K at least the number of distinct values. The whole array is valid. [1, 2, 3, 4] with K = 10 returns 4.
    • All values equal. [4, 4, 4] with K = 1 returns 3.
    • Updating answer before the check. If the max line ran before the break test, the invalid subarray's length would be counted.
    • Sharing one set across starts. Declare the set inside the outer loop, otherwise values from earlier starts inflate the count.

    Testing

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