LESSON 290 OF 348 · SLIDING WINDOW

Longest Subarray Without Repeating in TypeScript: O(n) with a Set

Given an input array of integers, find the length of the longest subarray without reapeating integers.

Example

Input: nums = [2, 5, 6, 2, 3, 1, 5, 6]
Output: 5
Explanation: [5, 6, 2, 3, 1] or [6, 2, 3, 1, 5] are both valid and of maximum length 5

Note:

For this lesson, your algorithm should run in O(n) time and use O(n) extra space

STEP 1 OF 9

Guided

Ctrl + Enter to check

TYPESCRIPT · SLIDING WINDOW

Longest Subarray Without Reapeating in TypeScript, explained

Problem overview

The method longestSubarrayWithoutReapeating receives an array of numbers, nums, and returns the length of the longest subarray in which no value appears twice. A subarray is a run of neighbouring elements, so you can't skip over elements to avoid a repeat.

For nums = [2, 5, 6, 2, 3, 1, 5, 6] the answer is 5. The subarray [5, 6, 2, 3, 1] has five different values, and so does [6, 2, 3, 1, 5]. Any window of six elements would have to contain a repeat. The statement asks for O(n) time and O(n) extra space.

Approach: a window that only moves right

The brute-force idea tries every start index, extends the subarray until a repeat appears and keeps the best length. With a set for the duplicate check that is still O(n²) in the worst case, because every start rescans elements that earlier starts already visited.

The faster idea reuses that work. Suppose the longest repeat-free subarray starting at i ends just before index j. Then the elements from i + 1 to j - 1 are also all different, so the subarray starting at i + 1 can begin with them. The new window doesn't need to restart from scratch. Its end j stays where it is and only moves right.

A Set holds the values currently inside the window. Checking has, adding and deleting are all constant time on average, which keeps each step cheap.

Here is the idea on [2, 5, 6, 2, 3, 1, 5, 6]:

Start i = 0: the window grows over 2, 5, 6 and stops at the second 2. Length 3.
Remove the first 2 and move to i = 1: the window 5, 6 grows over 2, 3, 1 and stops at the second 5. Length 5.
Remove 5 and move to i = 2: the window 6, 2, 3, 1 grows over 5 and stops at the second 6. Length 5.
The later starts can't beat 5, so the result stays 5.

Step by step

Create the set. uniqueNums holds the values of the current window. It is declared const because the variable always refers to the same set, even though the contents change. The annotation Set<number> tells TypeScript what the empty set will hold.
Create result as a let starting at 0. It is also the correct answer for an empty array.
Create j before the loop. It is the index of the next element to try to add. Because the window's end never moves back, declaring j outside the loop is what keeps the whole scan linear.
Loop over the start index i while i < nums.length.
Grow the window in a while loop that runs while j is inside the array and nums[j] is not already in the set. The order of the two conditions matters: && stops at the first false operand, so nums[j] is never looked at once j reaches the end.
Add the element to the set and move j forward.
Record the length. When the growing loop stops, the window is the elements from i up to but not including j. Its length equals the set's size, so Math.max keeps the larger of the old result and that size.
Remove nums[i] from the set before the next start. The window will begin one position later, while j stays put.
Return result after every start has been tried.

The solution in TypeScript

class Solution {
    longestSubarrayWithoutReapeating(nums: number[]): number {
        const uniqueNums: Set<number> = new Set();
        let result: number = 0;
        let j: number = 0;
        for (let i = 0; i < nums.length; ++i) {
            while (j < nums.length && !uniqueNums.has(nums[j])) {
                uniqueNums.add(nums[j]);
                ++j;
            }
            result = Math.max(result, uniqueNums.size);
            uniqueNums.delete(nums[i]);
        }
        return result;
    }
}

The TypeScript details worth a closer look:

Annotations disappear at run time. Set<number>, : number and the other annotations only help the compiler and your editor. The JavaScript that runs has none of them, and a Set will accept any value that actually shows up.
size is a property. A set's size has no parentheses, unlike the methods has and add. Writing uniqueNums.size() is a type error, and the call would fail at run time because size is a number.
A set compares values, not positions. Adding 3 twice leaves one 3 in the set. That is why the window can never hold two equal numbers, and why delete removes the only copy.
const is about the variable. The binding can't be reassigned, but add and delete still change what the set contains.
++j and j++ do the same thing as a standalone statement.

Complexity

Time: O(n). The outer loop runs n times. The inner loop doesn't restart, because j is declared outside and only increases. Across the whole run j moves at most n times, so the inner loop's total work is at most n steps. Each index enters the set once and leaves it at most once, and every set operation is constant time on average, giving O(n) in total.

Space: O(n). In the worst case, when all values are different, the set ends up holding every element.

Edge cases and common mistakes

Empty array. The loop never runs and the method returns 0.
All values equal. [1, 1, 1] gives 1: each window grows by one element, stops at the next equal value, and loses that element when i moves on.
All values different. The first window grows to the end of the array, and the result is nums.length. Later starts only shrink it.
Resetting j inside the loop. Setting j = i for each start is correct but makes the method O(n²) in the worst case, which breaks the lesson's time limit.
Forgetting delete. The set would keep values that left the window, and the next window would stop too early.
Confusing subarray and subsequence. In [2, 5, 6, 2, 3, 1, 5, 6] you could pick 2, 5, 6, 3, 1 by skipping the second 2, but that isn't contiguous.

Testing

[2, 5, 6, 2, 3, 1, 5, 6] gives 5.
[1, 1, 1] gives 1.
[] gives 0.

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

Start learning free