LESSON 244 OF 348 · HASH TABLE

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

Practice O(n²) Read the full explanation

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^2) time and use O(n) extra space.
(There exist faster solutions which we will discuss in future lessons)

STEP 1 OF 8

Guided

Ctrl + Enter to check

TYPESCRIPT · HASH TABLE

Longest Subarray Without Reapeating in TypeScript, explained

Problem overview

The method longestSubarrayWithoutReapeating receives an array of integers, nums, and returns the length of the longest subarray in which no value appears twice. A subarray is a run of neighbouring elements, so [5, 6, 2, 3, 1] is a subarray of [2, 5, 6, 2, 3, 1, 5, 6], while [2, 6] is not.

In the example, the answer is 5. Both [5, 6, 2, 3, 1] and [6, 2, 3, 1, 5] have five different values, and no run of six elements avoids a repeat. The method name keeps the lesson's spelling, "Reapeating", and so does this article.

Approach: try every start, extend until a repeat

For this lesson the statement allows O(n²) time and O(n) extra space. Faster solutions exist, but this one is the natural starting point.

The simplest idea checks every subarray from scratch. There are about n² subarrays, and checking each for repeats takes up to n more steps, so that would be O(n³). The improvement comes from reusing work. Fix the first element i, then grow the subarray one element at a time by moving the end j to the right. Keep a set of the values in the current subarray. When the next element is already in the set, the subarray cannot grow: every longer one starting at i would contain the same repeated value, so stop and try the next start.

With the set, the repeat check costs O(1) on average instead of scanning the subarray. Two nested loops give the O(n²) total.

On the example, starting at index 1 the subarray grows through 5, 5, 6, 5, 6, 2, 5, 6, 2, 3 and 5, 6, 2, 3, 1. The next element, 5, is in the set, so the loop breaks with the best length for this start equal to 5.

Step by step

Start the answer at 0. result is declared with let because it changes. An empty array has answer 0, and any real subarray will beat it.
Loop over the start index i. Use i < nums.length, so i stops at the last valid index.
Create an empty set for each start. uniqueNums is a new Set<number>(), made inside the loop so each start begins with no values. The type argument is needed because an empty set gives the compiler nothing to infer from.
Loop over the end index j, beginning at i. The one-element subarray is checked first.
Stop at a repeat. If uniqueNums.has(nums[j]), break out of the inner loop. At that moment the set holds exactly the values of nums[i..j-1].
Record the length. The subarray nums[i..j] is valid and has length j - i + 1. Math.max keeps the larger of that and the best so far. No else is needed, since the break skips this line.
Add nums[j] to the set, after the check. Adding it first would make every value look like a repeat of itself.
Return result after both loops finish.

The solution in TypeScript

class Solution {
    longestSubarrayWithoutReapeating(nums: number[]): number {
        let result = 0;
        for (let i = 0; i < nums.length; ++i) {
            let uniqueNums = new Set<number>();
            for (let j = i; j < nums.length; ++j) {
                if (uniqueNums.has(nums[j])) {
                    break;
                }
                result = Math.max(result, j - i + 1);
                uniqueNums.add(nums[j]);
            }
        }
        return result;
    }
}

++i and i++. In a for loop's update clause they behave the same; the result of the expression is discarded.
break leaves only the inner loop. The outer loop moves on to the next i.
let and const. uniqueNums is never reassigned, so const would also work; the set's contents change, but the variable still refers to the same set.
Type inference. result is inferred as number from 0, so it needs no annotation. The type argument on the set is erased when compiled.
Blocks and scope. A new set is created on every pass of the outer loop, and the one from the previous pass is discarded.

Complexity

Time: O(n²). For each of the n starts, the inner loop runs at most n - i times. Each iteration does one has, one Math.max and one add, which are constant time on average. For an array with no repeats at all, the inner loop never breaks and the total is about n² / 2 iterations.

Space: O(n). The set holds at most n values at once.

Edge cases and common mistakes

Empty array. The outer loop never runs and the method returns 0.
All values equal. [7, 7, 7] gives 1: each start accepts one element, then meets a repeat.
No repeats. [1, 2, 3] gives 3, the whole array.
Adding before checking. The result would stay at 0, since the first element would already be "in" the set.
Declaring the set outside the outer loop. Values from earlier starts would stay in it and cut subarrays short.
Confusing subarray and subsequence. Elements must be neighbours. Skipping elements would give a larger, wrong answer on the example.
Length off by one. The length of nums[i..j] with both ends included is j - i + 1, not j - i.

Testing

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