LESSON 245 OF 348 · HASH TABLE

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

Practice O(n²) 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

Guided

Ctrl + Enter to check

TYPESCRIPT · HASH TABLE

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

Problem overview

The method longestSubarray receives an array of integers, nums, and a limit K. It returns the length of the longest subarray, a run of neighbouring elements, that contains at most K different values. Repeated values inside the run are fine: only the number of different values is limited.

In the example, nums = [1, 2, 1, 2, 3] and K = 2. The first four elements, [1, 2, 1, 2], contain two distinct values, 1 and 2. Adding the final 3 would make it three, so the answer is 4.

Approach: try every start, grow until too many distinct values

The statement allows O(n²) time and O(n) extra space. Fix the start i of the subarray, then move the end j to the right one element at a time. A set records the values seen from i to j, and its size is the number of distinct values in the subarray.

The useful fact is that a longer subarray can never have fewer distinct values than a shorter one that it contains. So once size exceeds K, extending further is pointless for this start, and the inner loop can stop. The next start then begins with a fresh, empty set.

Checking every subarray from scratch would cost O(n³), since there are about n² of them and counting each one's distinct values takes up to n steps. Growing a single subarray and keeping the set updated removes that last factor.

The example, start by start

With K = 2 on [1, 2, 1, 2, 3]:

From i = 0 the set stays at size 2 through index 3, so the lengths 1, 2, 3 and 4 are recorded. At index 4 the value 3 makes the size 3, and the loop breaks. The best so far is 4.
From i = 1 the subarray [2, 1, 2] is valid with length 3, and then the 3 breaks the loop.
From i = 2 and i = 3 the best lengths are 2 and 2.
From i = 4 the single element [3] gives length 1.

The answer stays at 4. Most of the later starts repeat work already done, which is what the faster approaches for this problem avoid.

Step by step

Start the answer at 0. answer is declared with let.
Loop over the start i from 0 while i < nums.length.
Create an empty set for this start. distinctValues is a new Set<number>(). The type argument tells the compiler what the set will hold, because an empty set gives it nothing to infer.
Loop over the end j from i. Each pass extends the subarray by one element.
Add nums[j] to the set. Duplicates are ignored, so the size counts distinct values.
Stop when the set is too big. If distinctValues.size > K, break. Nothing longer from this start can be valid.
Record the length. The subarray nums[i..j] is valid, with length j - i + 1, so answer becomes the larger of the two.
Return answer after the outer loop.

Notice the order: the element is added first and the size is tested afterwards, because the test needs the new element counted. A check that only asks whether a value repeats would go the other way round.

The solution in TypeScript

class Solution {
    longestSubarray(nums: number[], K: number): number {
        let answer = 0;
        for (let i = 0; i < nums.length; i++) {
            let distinctValues = new Set<number>();
            for (let j = i; j < nums.length; j++) {
                distinctValues.add(nums[j]);
                if (distinctValues.size > K) {
                    break;
                }
                answer = Math.max(answer, j - i + 1);
            }
        }
        return answer;
    }
}

size, not length. A Set reports its number of values with the property size. Writing distinctValues.length gives undefined, and the compiler reports an error.
The parameter is a capital K. Names are case-sensitive, so k would be a different, undeclared name.
Sets ignore repeats. Adding a value that is already present does nothing, which is why a subarray like [1, 2, 1, 2] has a set of size 2.
The set is rebuilt for each start. It is declared inside the outer loop on purpose.

Complexity

Time: O(n²). There are n starts, and each inner loop runs at most n times with constant average cost per step. The break usually ends it sooner, but in the worst case, when the whole array has at most K distinct values, it never fires.

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

Edge cases and common mistakes

Empty array. The loops never run and the method returns 0.
K is 0. The first element already makes the size 1, which is more than 0, so every start breaks at once and the answer is 0.
K at least the number of distinct values. The whole array qualifies and the answer is nums.length. For [1, 2, 3] with K = 5, that is 3.
Using >= in the test. That would reject subarrays with exactly K distinct values. The limit is "at most", so only > breaks.
Updating the answer before the test. The invalid subarray would be counted, giving 5 instead of 4 on the example.
Sharing one set across starts. Leftover values from earlier starts would inflate the size.

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.
nums = [], K = 3 gives 0.
nums = [1, 2, 3], K = 5 gives 3.

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

Start learning free