LESSON 197 OF 338 · NESTED LOOPS & BRUTE FORCE

Longest Subarray Without Repeating in Go: 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

GO · NESTED LOOPS & BRUTE FORCE

Longest Subarray Without Reapeating in Go, explained

Problem overview

The function longestSubarrayWithoutRepeating(nums []int) int receives a slice of integers and returns the length of the longest subarray in which no value appears twice. A subarray is a run of consecutive elements.

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 distinct values, and no run of six elements is free of repeats.

This lesson accepts O(n^3) time and O(1) extra space, so it is the plain brute force. Faster approaches exist and come in later lessons.

Approach: try every subarray, check it for repeats

Every subarray is identified by a first index i and a last index j with i <= j. The brute force visits all of them, checks whether each is free of repeats, and keeps the longest valid length.

Checking one subarray from scratch costs O(n), and there are O(n^2) subarrays, which would give O(n^3). The solution uses two observations to avoid doing more work than needed:

For a fixed i, j grows one step at a time. The subarray nums[i..j] is the previous subarray nums[i..j-1] with nums[j] added. If the previous one had no repeats, the new one has a repeat only if nums[j] already occurs among nums[i..j-1]. So each step needs one scan, not a full check.
Once a repeat appears, every longer subarray starting at the same i contains that same repeat. The j loop can stop and move on to the next i.

The loops are still three levels deep, so the worst case is O(n^3), for example when all values are distinct and no loop stops early.

Tracing the example

Take [2, 5, 6, 2, 3, 1, 5, 6]. For i = 0, the loop extends through 2, 5 and 6, reaching length 3. At j = 3 the value 2 is already present, so the scan finds a duplicate and the j loop ends. For i = 1, the values 5, 6, 2, 3 and 1 are all new, so the length reaches 5, and at j = 6 the value 5 repeats and the loop stops. The remaining starting points reach lengths of at most 5, so result ends at 5.

Step by step

Declare result with := and the value 0. It holds the best length so far. An empty slice has answer 0, and any real subarray replaces this value.
Loop over the first index i from 0 while i < len(nums).
Loop over the last index j from i while j < len(nums). Starting at i means the one-element subarray is considered first.
Look for a duplicate of nums[j] in the previous subarray, nums[i..j-1]. Go has no membership operator for slices, so the code searches by hand: set found := false, loop k from i while k < j, and when nums[k] == nums[j] set found to true and break.
Stop the j loop on a duplicate. The break in the previous step only leaves the k loop, so a second check, if found { break }, leaves the j loop as well. That is why the flag exists.
Update the answer. If the new element was not a duplicate, nums[i..j] is valid and has length j - i + 1. When that is more than result, store it.
Return result after the loops.

The solution in Go

func longestSubarrayWithoutRepeating(nums []int) int {
    result := 0
    for i := 0; i < len(nums); i++ {
        for j := i; j < len(nums); j++ {
            found := false
            for k := i; k < j; k++ {
                if nums[k] == nums[j] {
                    found = true
                    break
                }
            }
            if found {
                break
            }
            if j-i+1 > result {
                result = j - i + 1
            }
        }
    }
    return result
}

Go details:

Breaking out of two loops. In Go, break leaves only the innermost for. A flag, as here, is one way to leave the next loop out; a labeled break is another.
found is declared inside the j loop, so it starts as false for every new j. Declaring it outside would carry an old true into later steps.
No else needed. When a duplicate is found, the break skips the update lines, so they run only for valid subarrays.
Half-open range. The inner loop covers k from i up to but not including j, which is exactly the elements before nums[j]. Including j would always find nums[j] equal to itself.
The scan by hand. Since Go 1.21 the standard library's slices.Contains performs the same linear search on a slice, such as nums[i:j]. Writing the loop shows what the search costs.

Complexity

Time: O(n^3). There are about n^2 / 2 pairs (i, j), and each does a scan of up to j - i elements. When all values are distinct, nothing stops early, and the total number of comparisons grows like n^3 / 6.

Space: O(1). The code keeps result, found and three loop counters.

Edge cases and common mistakes

Empty slice. The loops never run and the result stays 0.
Single element. [7] gives 1.
All equal. [4, 4, 4] gives 1: at each i, the second element is a duplicate and ends the scan.
All distinct. [1, 2, 3] gives 3, the whole slice.
A repeat that is not adjacent. [1, 2, 1, 3] gives 3, from [2, 1, 3]. Only checking neighbours would miss the repeated 1.
Forgetting the second break. Without it, the code would keep extending past a duplicate and could count a subarray that contains one.
Length arithmetic. The length of nums[i..j] inclusive is j - i + 1, not j - i.

Testing

[2, 5, 6, 2, 3, 1, 5, 6] gives 5.
[1, 2, 1, 3] gives 3.
[4, 4, 4] gives 1.
[1, 2, 3] gives 3.
An empty slice gives 0.

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

Start learning free