LESSON 197 OF 348 · NESTED LOOPS & BRUTE FORCE

Longest Subarray Without Reapeating in TypeScript: O(n^3) Brute Force

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

STEP 1 OF 6

Guided

Ctrl + Enter to check

TYPESCRIPT · NESTED LOOPS & BRUTE FORCE

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 [5, 6, 2] is a subarray of [2, 5, 6, 2, 3] but [2, 6] is not.

For nums = [2, 5, 6, 2, 3, 1, 5, 6] the answer is 5. Both [5, 6, 2, 3, 1] and [6, 2, 3, 1, 5] have five different values, and no longer run avoids a repeat. The statement's budget is O(n^3) time and O(1) extra space, so this lesson is about getting a correct brute-force answer first. (The method name keeps the spelling "Reapeating" exactly as written.)

Approach: try every start, extend until a repeat

A subarray is fixed by where it starts and where it ends. The brute-force plan is to take each start i, then grow the subarray one element at a time by moving the end j to the right. Each time a new element nums[j] is added, check whether it already occurs in the part before it. If it does not, the subarray from i to j is valid, and its length j - i + 1 is a candidate for the answer.

The moment nums[j] is a repeat, you can stop growing from this i. Every longer subarray starting at i contains the same repeat, so none of them can be valid. That is the break. Skipping to the next start saves time, but the worst case is still cubic: there are about n^2 / 2 start-and-end pairs, and the duplicate check scans up to n elements for each.

Step by step

Declare result as 0 with let. It holds the best length found so far and changes later. An empty array has answer 0, and any real subarray replaces it.
Loop over the starts. i runs from 0 while i < nums.length, using < so it stops at the last valid index.
Loop over the ends. Inside it, j starts at i and runs while j < nums.length. Starting at i makes the first candidate the one-element subarray [nums[i]].
Check for a repeat. Take nums.slice(i, j), the subarray before the new element, and ask whether it includes(nums[j]). The slice stops before index j, so it doesn't contain the new element itself. On a repeat, break leaves the inner loop.
Record the length. If there was no repeat, the elements from i to j are all different and form j - i + 1 elements. Update result with Math.max. No else is needed: after a break this line never runs.
Return result after both loops.

The solution in TypeScript

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

Details worth knowing:

slice(start, end) copies a range. It returns a new array containing the elements from start up to but not including end, and leaves nums alone. When start equals end the result is an empty array, which is what happens on the first pass for each i, so includes is false and the one-element subarray counts.
The copy is the hidden cost. Each slice allocates a new array of up to n elements, and includes then scans it. That work is the third factor of n in the running time.
++i and i++ do the same thing as the third part of a for header, because the value of the expression isn't used.
result has type number. TypeScript infers it from the 0, so no annotation is needed.
Math.max(a, b) returns the larger of its arguments, so result never goes down.

Complexity

Time: O(n^3). There are up to n starts and up to n ends for each, and every end performs a slice and an includes that each cost up to n steps. The early break speeds up inputs with many repeats, but an array of all different values never breaks, so the worst case stays cubic.

Space: O(n) for the temporary slice. The statement asks for O(1) extra space, and a loop that compared elements by index would achieve that. This version creates a copy for each check, though only one copy is alive at a time, so the memory used at any moment is at most n elements.

Edge cases and common mistakes

Empty array. Neither loop runs and the method returns 0.
All values equal. [7, 7, 7] gives 1: each start gets one valid element, then the repeat triggers the break.
No repeats at all. [1, 2, 3] gives 3, the length of the whole array.
A repeat that is not at the edge. [1, 2, 1, 3] gives 3, from [2, 1, 3], which a start at index 0 would never find.
Off-by-one in the slice. nums.slice(i, j + 1) contains nums[j] itself, so the check would find a "repeat" every time and the answer would be 0.
Subsequence against subarray. Elements must be neighbours. Skipping elements would give longer but invalid answers.

Testing

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