Problem overview
The method longestSubarray receives an array of integers nums and a number K. It must return the length of the longest contiguous subarray that contains at most K different values. Repeats of the same value count once.
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 the length is 4. Adding the 3 would make three distinct values, which is too many. The answer is 4.
Approach: a window with a frequency map
The brute-force way checks every subarray and counts its distinct values, which is slow. A faster way keeps a window over the array, indices first to last, and makes sure the window is always valid.
The key property: if a window has at most K distinct values, then every smaller window inside it also does. So there is no need to restart. For each right end last:
- Add
nums[last]to the window. - If the window now has more than
Kdistinct values, remove elements from the left until it has at mostK. - The window is valid, so its length
last - first + 1is a candidate for the answer.
To know how many distinct values the window holds, keep a Map from each value to how many times it occurs in the window. The map's size is the number of distinct values. A value must leave the map as soon as its count reaches zero. Otherwise the size would still count a value that is no longer in the window.
Take [1, 2, 1, 2, 3] with K = 2. The window grows over 1, 2, 1, 2, and the map holds 1 with count 2 and 2 with count 2. When the 3 arrives, the map has three keys, which is too many. The left end removes 1 (count 1), then 2 (count 1), then the second 1 (count 0, so the key is deleted). The window is now [2, 3] with two distinct values. The best length stays 4.
Step by step
- Create the frequency map
freq. It maps a value in the window to its count, sofreq.sizeis the number of distinct values. - Declare
answerandfirst, both 0: the best length so far and the left end of the window. - Loop over
lastfrom 0 up tonums.length - 1. This index is the window's right end, so every index is tried as the end of a subarray. - Call
insert(freq, nums[last])to add the new element to the window. The lesson writes this helper at the end. - Shrink while invalid: loop while
freq.size > K. The size of a map is a property, not a method, so it takes no parentheses. - Remove from the left: call
remove(freq, nums[first])and then increasefirst. Together they drop the leftmost element. - Update the answer after the shrinking loop:
Math.max(answer, last - first + 1). The window is valid here. - Return
answerafter the loop. - Write
remove. It lowers the count ofvalby one. If the count is now exactly 0, it deletes the key. - Write
insert. It sets the count ofvalto the old count plus one. For a value not yet in the map,getreturnsundefined, so|| 0starts the count at zero.
The solution in TypeScript
class Solution {
insert(freq: Map<number, number>, val: number): void {
freq.set(val, (freq.get(val) || 0) + 1);
}
remove(freq: Map<number, number>, val: number): void {
freq.set(val, freq.get(val)! - 1);
if (freq.get(val) === 0) {
freq.delete(val);
}
}
longestSubarray(nums: number[], K: number): number {
let freq = new Map<number, number>();
let answer = 0, first = 0;
for (let last = 0; last < nums.length; last++) {
this.insert(freq, nums[last]);
while (freq.size > K) {
this.remove(freq, nums[first]);
first++;
}
answer = Math.max(answer, last - first + 1);
}
return answer;
}
}
The TypeScript details worth knowing:
- The type of the map.
Mapis a generic type, so it names its key and value types:Map<number, number>maps numbers to numbers. An emptynew Map()gives the compiler nothing to infer from, so the type arguments are written out. They are erased when TypeScript compiles to JavaScript and have no effect at run time. getcan returnundefined. For a missing key,freq.get(val)isundefined, andundefined + 1isNaN. That is whyinsertuses|| 0. Inremove, the key is always present, so the!(non-null assertion) tells the compiler thatgetwon't beundefined. It checks nothing at run time.- Strict equality.
freq.get(val) === 0is true only for the number 0, so the key is deleted exactly when its count reaches zero. Without the delete,freq.sizewould keep counting values that have left the window. sizeandthis.freq.sizeis a property. The helper methods are called asthis.insert(...)andthis.remove(...), because they belong to the class.- Map keys. A
Mapcompares number keys by value, so every 1 in the array reaches the same entry.
Complexity
Time: O(n). last goes through the array once, and first only moves forward, so each element enters the window once and leaves it at most once. Every map operation takes constant time on average. This is within the O(n²) the statement allows, and a good deal faster than checking every subarray.
Space: O(K), or O(n) in the worst case if K is large. The map holds at most K + 1 keys at its peak, since one extra value is added before the window shrinks, and never more than the number of distinct values in the array.
Edge cases and common mistakes
- An empty array. The loop doesn't run, and the answer is 0.
K = 0. No value is allowed. Each insert is followed by removals until the window is empty, so every candidate length is 0 and the answer is 0.Kat least as large as the number of distinct values. The window never shrinks, and the answer is the array's length.- One repeated value.
[1, 1, 1]withK = 1gives 3, because repeats don't add distinct values. - Not deleting zero counts. If a count drops to 0 but its key stays,
freq.sizeoverstates the distinct values, and the window shrinks too much. - Counting the window's length as
last - first. The window includes both ends, so the length islast - first + 1. - Shrinking with
ifinstead ofwhile. One removal may not be enough. Removing a value that occurs once lowers the distinct count, but removing one that occurs twice may not. - Missing the
|| 0. The first insert of a value would storeNaN, and the counts never recover.
Testing
nums = [1, 2, 1, 2, 3],K = 2gives4.nums = [1, 1, 1],K = 1gives3.nums = [1, 2, 3, 1, 1, 1, 2],K = 2gives4.nums = [1, 2, 3],K = 0gives0.nums = [],K = 2gives0.