Problem overview
LongestSubarrayWithoutReapeating(nums) receives an array of integers and returns the length of the longest contiguous subarray in which no value appears twice. The method name keeps the spelling used in the lesson, so use it exactly as written.
In the example, nums = [2, 5, 6, 2, 3, 1, 5, 6]. The subarrays [5, 6, 2, 3, 1] and [6, 2, 3, 1, 5] both have five distinct values and are as long as possible, so the answer is 5. Adding any neighbour to either of them would repeat a value. The note asks for O(n) time and O(n) extra space.
Approach: a window that grows until it meets a repeat
The brute-force way checks every subarray for duplicates, which is cubic if done naively. A better way fixes each start and extends the end until a repeat appears, which is quadratic. This lesson's version is linear and relies on one fact: if a window has no repeats, then any smaller window inside it has none either.
So the window's right end never needs to move back. Keep a window of distinct values in a HashSet<int>, which answers "is this value in the window?" in constant time. For each start i, extend the end j as far as the next value is not in the set. When it stops, the window nums[i..j-1] is the longest repeat-free subarray starting at i. Record its length, remove nums[i] from the set, and move to the next start. The end j stays where it is, because the values from i + 1 to j - 1 are still distinct.
In this lesson j is the index of the next element to try, one past the window's right end, so the window's length is j - i. That is also the number of values in the set, which makes uniqueNums.Count the length.
Other lessons on the same problem take different routes, for example tracking the last position of each value. This one uses a set.
Step by step
- Create the set.
uniqueNumsis aHashSet<int>holding the values of the current window. It lives inSystem.Collections.Generic. - Start the best length at 0.
resultis anint. An empty array has answer 0, and any real window replaces it. - Declare
jbefore the loop. It is the next index to try, starting at 0. It must be declared outside the loop overibecause the window's end never moves back, and that is what makes the scan linear. Each index enters the window once, whenjpasses it, and leaves once, whenipasses it. - Loop over start positions.
iruns from 0 whilei < nums.Length, with a strict comparison so it stops at the last valid index. - Grow the window. The inner loop runs while
j < nums.Lengthand!uniqueNums.Contains(nums[j]). The&&stops at the first false operand, sonums[j]is never read oncejreaches the end. - Take the new value in. Add
nums[j]to the set, then incrementjwith++j. - Record the length. When the loop stops, the window runs from
iup to but not includingj, because the loop ended either at the end of the array or at a value already in the window. Its length equalsuniqueNums.Count, soresult = Math.Max(result, uniqueNums.Count).Countis a property, so there are no parentheses. - Remove the start. Before moving to
i + 1, removenums[i]from the set withRemove. The element is always in the set at this point: if the window was empty, the inner loop added at leastnums[i]. - Return
resultafter every start has been tried.
The solution in C#
class Solution {
public int LongestSubarrayWithoutReapeating(int[] nums) {
HashSet<int> uniqueNums = new HashSet<int>();
int result = 0;
int j = 0;
for (int i = 0; i < nums.Length; ++i) {
while (j < nums.Length && !uniqueNums.Contains(nums[j])) {
uniqueNums.Add(nums[j]);
++j;
}
result = Math.Max(result, uniqueNums.Count);
uniqueNums.Remove(nums[i]);
}
return result;
}
}
Some C# details are worth a closer look:
- Set methods.
HashSet<T>offersAdd,ContainsandRemove, each constant time on average.AddandRemovealso return abooltelling whether the set changed. The code ignores those results, which C# allows. ++jandj++are equivalent here. The result of the expression is not used, so the prefix and postfix forms behave the same. The same goes for++iin theforheader.Count, notLength. A set reports its size withCount. Arrays useLength.- Short-circuit evaluation. Putting
!uniqueNums.Contains(nums[j])first would readnums[j]whenj == nums.Lengthand throw anIndexOutOfRangeException. The bounds check has to come first. - Value equality for
int. The set compares integers by value, so two different array elements holding 6 count as the same value.
Tracing the example
For [2, 5, 6, 2, 3, 1, 5, 6], the window for i = 0 grows over 2, 5 and 6 and stops at the second 2, so j = 3 and the length is 3. Removing the first 2 lets the window continue: for i = 1 it takes in 2, 3 and 1 and stops at the 5 at index 6, giving the window [5, 6, 2, 3, 1] and the length 5. For i = 2 the window drops the 5, takes the 5 at index 6 and stops at the 6 at index 7, so the length is 5 again. Later starts give shorter windows, and the answer is 5.
Complexity
Time: O(n). The inner loop doesn't restart for each i. Since j never decreases, it moves forward at most n times in total, and i moves n times. Each set operation is constant time on average.
Extra space: O(n). In the worst case, when all values are distinct, the set holds the whole array.
Edge cases and common mistakes
- Empty array. The loop never runs, and the method returns 0.
- All values equal.
[7, 7, 7]gives 1: the window can only ever hold a single 7. - All values distinct.
[1, 2, 3]gives 3, the whole array. - Resetting
jfor each start. Declaringjinside theforloop makes the scan quadratic. - Skipping the removal. If
nums[i]stays in the set, the window can never take that value in again, and the window's contents no longer match the indices. - Measuring with
j - i + 1. Becausejis one past the end, the correct length isj - i, or equivalentlyuniqueNums.Count. - Confusing subarrays and subsequences. A subarray is contiguous. For
[1, 2, 1, 3], the answer 3 comes from[2, 1, 3], not from skipping the second 1.
Testing
nums = [2, 5, 6, 2, 3, 1, 5, 6]gives 5.nums = []gives 0.nums = [7, 7, 7]gives 1.nums = [1, 2, 3]gives 3.nums = [1, 2, 1, 3]gives 3.