Problem overview
The method longestSubarray receives a vector<int> called nums and an integer K. A subarray is a block of neighbouring elements, such as nums[2..5], and it cannot skip elements. The method returns the length of the longest subarray that contains at most K different values. Repeated values count once: [1, 2, 1, 2] has two distinct values although it has four elements.
For nums = [1, 2, 1, 2, 3] and K = 2 the answer is 4. The subarray nums[0..3] = [1, 2, 1, 2] has two distinct values. Adding the 3 would make three, and any subarray that includes the 3 and has length 4 or more would contain at least three distinct values as well.
The statement allows O(n^2) time and O(n) extra space, which tells you that checking many subarrays is acceptable here, as long as each check is cheap.
Approach: grow a subarray from every start
Every subarray is defined by its start i and its end j. The simplest plan is to try all pairs and count the distinct values in each. Counting from scratch costs up to O(n) per pair, so with O(n^2) pairs that would be O(n^3), too slow for the budget.
The lesson avoids the recounting. For a fixed start i, it extends the end j one element at a time and keeps the values seen so far in an unordered_set. A set ignores duplicates, so after inserting nums[j] its size is exactly the number of distinct values in nums[i..j]. Each extension costs one insertion, which is O(1) on average, and the count is available for free.
There is also a reason to stop early. Extending a subarray never removes values, so the number of distinct values can only stay the same or grow. When the set first becomes larger than K, every longer subarray starting at i is invalid as well, and the inner loop can break.
Tracing the example
For nums = [1, 2, 1, 2, 3] and K = 2:
| Start i | Subarrays tried | Stops because | Longest valid from i |
|---|---|---|---|
| 0 | [1], [1,2], [1,2,1], [1,2,1,2] | adding 3 makes 3 distinct values | 4 |
| 1 | [2], [2,1], [2,1,2] | adding 3 makes 3 distinct values | 3 |
| 2 | [1], [1,2] | adding 3 makes 3 distinct values | 2 |
| 3 | [2], [2,3] | end of the array | 2 |
| 4 | [3] | end of the array | 1 |
The best of these is 4, which is the answer.
This lesson is the quadratic solution. A sliding window that keeps a count of each value inside the window can solve the same problem in O(n) time, and the other lesson on this problem takes that route.
Step by step
- Declare
answeras anintset to 0. It stores the longest valid length found so far. - Loop over every start with an
intindexifrom 0 tonums.size() - 1. - Create a fresh
unordered_set<int>nameddistinctValuesinside the outer loop. Declaring it there gives every start an empty set, and a declared set needs no initializer. - Loop over the end with an
intindexjthat starts ati. Together,iandjmark the subarraynums[i..j]. - Insert
nums[j]into the set. If the value is already there, nothing changes. - Stop when there are too many distinct values. If
distinctValues.size() > K,breakout of the inner loop. - Record the length. When the loop did not break, the subarray is valid, so set
answer = max(answer, j - i + 1). A subarray fromitojcontainsj - i + 1elements. - Return
answerafter the outer loop.
The solution in C++
class Solution {
public:
int longestSubarray(vector<int>& nums, int K) {
int answer = 0;
for (int i = 0; i < nums.size(); i++) {
unordered_set<int> distinctValues;
for (int j = i; j < nums.size(); j++) {
distinctValues.insert(nums[j]);
if (distinctValues.size() > K) {
break;
}
answer = max(answer, j - i + 1);
}
}
return answer;
}
};
The C++ details behind these lines:
inserton a set.unordered_set::insertadds the value if it is new and does nothing otherwise. The set is destroyed at the end of each outer iteration, so the next start begins with an empty one.size()is unsigned.distinctValues.size()has typesize_t, whileKis anint. In the comparison,Kis converted to unsigned, which is harmless forK >= 0. A negativeKwould turn into a huge number, the condition would never be true, and the method would return the length of the whole array. For[1, 2, 1, 2, 3]andK = -1it returns 5.maxcomes from<algorithm>. Both arguments must have the same type, and here both areint.- The same code works for characters. Changing the vector to a
stringand the set tounordered_set<char>solves "longest substring with at most K distinct characters" the same way.
Complexity
Time: O(n^2). For start i the inner loop runs at most n - i times, and each run does one insertion and one comparison, which are constant work on average. Summed over all starts that is about n^2 / 2 steps. The early break does not change the worst case: if K is at least the number of distinct values in the array, no start ever breaks.
Space: O(n) at most. The set holds distinct values of one subarray, and the inner loop stops as soon as it holds K + 1 of them, so it never grows beyond min(n, K + 1) entries.
Edge cases and common mistakes
- Empty vector. The outer loop does not run and the method returns 0.
K = 0. The first insertion makes the set size 1, which is larger than 0, so every inner loop breaks at once and the answer is 0.Kat least the number of distinct values. The whole array is valid. For[1, 2, 1, 2, 3]andK = 3or more, the answer is 5.- All elements equal. For
[4, 4, 4, 4]andK = 1, the answer is 4. - Creating the set outside the outer loop. Then the values of one start would leak into the next, and the counts would be wrong. The set must start empty for every
i. - Updating
answerbefore the check. Placinganswer = max(...)above theifwould count a subarray that already has too many distinct values. - Confusing subarray and subsequence. A subarray is contiguous. In
[1, 2, 1, 2, 3]the elements 1, 1, 3 are not a subarray.
Testing
nums = [1, 2, 1, 2, 3],K = 2gives4.nums = [1, 2, 1, 2, 3],K = 1gives1.nums = [1, 2, 1, 2, 3],K = 0gives0.nums = [1, 2, 1, 2, 3],K = 3gives5.nums = [4, 4, 4, 4],K = 1gives4.nums = [],K = 2gives0.
