LESSON 289 OF 348 · SLIDING WINDOW

Longest Subarray with at Most K Distinct Integers in Kotlin: O(n) 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

KOTLIN · SLIDING WINDOW

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

Problem overview

The function longestSubarray receives an IntArray, nums, and an integer K. It must return the length of the longest contiguous subarray that contains at most K different values.

For nums = [1, 2, 1, 2, 3] and K = 2, the answer is 4. The subarray nums[0..3] is [1, 2, 1, 2], which holds only the values 1 and 2. Extending it to include the 3 would make three distinct values.

Approach: grow on the right, shrink on the left

The brute force checks every subarray and counts its distinct values, which is slow. A better observation is that validity is easy to keep up to date as a window moves. If a subarray has at most K distinct values, then every smaller subarray inside it does too. So you can slide a window along the array:

Extend the right end by one element, nums[last].
If the window now has more than K distinct values, drop elements from the left, one at a time, until it is valid again.
The window is now the longest valid subarray ending at last, so compare its length with the best so far.

To know how many distinct values the window holds, and to know when a value has left it completely, you keep a map from each value to the number of times it occurs in the window. The number of keys is the number of distinct values. Both ends of the window only move forward, so each index enters once and leaves at most once, which makes the work linear.

The statement mentions O(n²) time, but this approach does better, at O(n).

Step by step

Create the map, val freq = HashMap<Int, Int>(), mapping each value in the window to its count. val only stops the variable from being reassigned. The map's contents still change.
Declare answer and first with var, both 0. answer is the best length so far and first is where the window starts.
Loop with last over nums.indices. It is the right end of the window.
Add the new element with the helper insert(freq, nums[last]).
Shrink while invalid: a while loop that runs while freq.size > K.
Remove the leftmost element with remove(freq, nums[first]), then do first++.
Update the answer with maxOf(answer, last - first + 1). The window nums[first..last] is valid at this point.
Return answer.
Write remove. It takes the map and a value. It subtracts 1 from the value's count, and if the count reaches 0, it deletes the key. Without the deletion, freq.size would still count a value that has left the window.
Write insert. It sets the value's count to its old count plus 1. A value that isn't in the map reads as null, so the lookup is wrapped in parentheses with ?: 0 to start from 0.

The solution in Kotlin

class Solution {
    fun insert(freq: HashMap<Int, Int>, value: Int) {
        freq[value] = (freq[value] ?: 0) + 1
    }
    fun remove(freq: HashMap<Int, Int>, value: Int) {
        freq[value] = freq[value]!! - 1
        if (freq[value] == 0) {
            freq.remove(value)
        }
    }
    fun longestSubarray(nums: IntArray, K: Int): Int {
        val freq = HashMap<Int, Int>()
        var answer = 0
        var first = 0
        for (last in nums.indices) {
            insert(freq, nums[last])
            while (freq.size > K) {
                remove(freq, nums[first])
                first++
            }
            answer = maxOf(answer, last - first + 1)
        }
        return answer
    }
}

The Kotlin details worth knowing:

A missing key gives null. freq[value] has the type Int?. In insert, the Elvis operator ?: supplies 0 when the key is absent. Without the parentheses, freq[value] ?: 0 + 1 would parse as freq[value] ?: (0 + 1), and an existing count would never be incremented.
!! in remove. It asserts that the value is in the map. That holds because remove is only called on values that insert added. Calling remove for an absent value would throw a NullPointerException.
freq[value] == 0. Comparing an Int? with 0 is allowed in Kotlin: == calls equals and handles null. It is true only for a present count of 0.
Index assignment. freq[value] = x calls the map's set, which inserts or replaces.
freq.remove(value) removes the key and its count. For a HashMap<Int, Int> it removes by key, not by position.
HashMap<Int, Int> is Kotlin's name for Java's HashMap with boxed Integer keys and values.

Complexity

Time: O(n). last advances once per element, and first advances at most n times in total, since it never moves back. Each step performs a constant number of map operations, which take constant time on average.

Space: O(K), and at most O(n). The map holds at most K + 1 keys at any moment: right after an insertion it may briefly hold one extra, before the shrinking loop trims it. It can never hold more keys than the array has elements, so the O(n) bound from the statement holds too.

Edge cases and common mistakes

Empty array. The loop doesn't run, and the answer is 0.
K = 0. Every inserted value makes the size 1, which is above 0, so the window shrinks until it is empty. The answer is 0.
K at least the number of distinct values. The window never shrinks, and the answer is nums.size. For [1, 2, 3, 4] with K = 10 it is 4.
One repeated value. [4, 4, 4] with K = 1 gives 3: the count of 4 grows to 3, but the size stays at 1.
Not deleting zero counts. Leaving a key with count 0 in the map inflates freq.size, so the window shrinks too much.
Checking validity only once. Removing one element doesn't always reduce the distinct count. If that value still occurs inside the window, the size doesn't change, which is why the shrink step is a while loop and not an if.
Measuring before shrinking. Compute the length only after the loop, when the window is valid.

Testing

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

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

Start learning free